2362N/A * Copyright (c) 1999, 2007, Oracle and/or its affiliates. All rights reserved. 0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 0N/A * This code is free software; you can redistribute it and/or modify it 0N/A * under the terms of the GNU General Public License version 2 only, as 2362N/A * published by the Free Software Foundation. Oracle designates this 0N/A * particular file as subject to the "Classpath" exception as provided 2362N/A * by Oracle in the LICENSE file that accompanied this code. 0N/A * This code is distributed in the hope that it will be useful, but WITHOUT 0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 0N/A * version 2 for more details (a copy is included in the LICENSE file that 0N/A * accompanied this code). 0N/A * You should have received a copy of the GNU General Public License version 0N/A * 2 along with this work; if not, write to the Free Software Foundation, 0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2362N/A * or visit www.oracle.com if you need additional information or have any 0N/A * A class used to represent multiprecision integers that makes efficient 0N/A * use of allocated space by allowing a number to occupy only part of 0N/A * an array so that the arrays do not have to be reallocated as often. 0N/A * When performing an operation with many iterations the array used to 0N/A * hold a number is only reallocated when necessary and does not have to 0N/A * be the same size as the number it represents. A mutable number allows 0N/A * calculations to occur on the same number without having to create 0N/A * a new number for every step of the calculation as occurs with 0N/A * @author Michael McCloskey 0N/A * Holds the magnitude of this MutableBigInteger in big endian order. 0N/A * The magnitude may start at an offset into the value array, and it may 0N/A * end before the length of the value array. 0N/A * The number of ints of the value array that are currently used 0N/A * to hold the magnitude of this MutableBigInteger. The magnitude starts 0N/A * at an offset and offset + intLen may be less than value.length. 0N/A * The offset into the value array where the magnitude of this 0N/A * MutableBigInteger begins. 1246N/A * MutableBigInteger with one element value array with the value 1. Used by 1246N/A * BigDecimal divideAndRound to increment the quotient. Use this constant 1246N/A * only when the method is not going to modify this object. 0N/A * The default constructor. An empty MutableBigInteger is created with 0N/A * a one word capacity. 0N/A * Construct a new MutableBigInteger with a magnitude specified by 0N/A * Construct a new MutableBigInteger with the specified value array 0N/A * up to the length of the array supplied. 0N/A * Construct a new MutableBigInteger with a magnitude equal to the 0N/A * specified BigInteger. 0N/A * Construct a new MutableBigInteger with a magnitude equal to the 0N/A * specified MutableBigInteger. 1246N/A * Internal helper method to return the magnitude array. The caller is not 1246N/A * supposed to modify the returned array. 1246N/A * Convert this MutableBigInteger to a long value. The caller has to make 1246N/A * sure this MutableBigInteger can be fit into long. 1246N/A assert (
intLen <=
2) :
"this MutableBigInteger exceeds the range of long";
1246N/A * Convert this MutableBigInteger to a BigInteger object. 1246N/A * Convert this MutableBigInteger to BigDecimal object with the specified sign 1246N/A // If this MutableBigInteger can't be fit into long, we need to 1246N/A // make a BigInteger object for the resultant BigDecimal object. 0N/A * Clear out a MutableBigInteger for reuse. 0N/A * Set a MutableBigInteger to zero, removing its offset. 0N/A * Compare the magnitude of two MutableBigIntegers. Returns -1, 0 or 1 0N/A * as this MutableBigInteger is numerically less than, equal to, or 1246N/A // Add Integer.MIN_VALUE to make the comparison act as unsigned integer 1246N/A * Compare this against half of a MutableBigInteger object (Needed for 1246N/A * Assumes no leading unnecessary zeros, which holds for results 1246N/A // Only 2 cases left:len == blen or len == blen - 1 1246N/A // compare values with right-shifted values of b, 1246N/A // carrying shifted-out bits across words 1246N/A carry = (
bv &
1) <<
31;
// carray will be either 0x80000000 or 0 0N/A * Return the index of the lowest set bit in this MutableBigInteger. If the 0N/A * magnitude of this MutableBigInteger is zero, -1 is returned. 0N/A * Return the int in use in this MutableBigInteger at the specified 0N/A * index. This method is not used because it is not inlined on all 0N/A * Return a long which is equal to the unsigned value of the int in 0N/A * use in this MutableBigInteger at the specified index. This method is 0N/A * not used because it is not inlined on all platforms. 0N/A * Ensure that the MutableBigInteger is in normal form, specifically 0N/A * making sure that there are no leading zeros, and that if the 0N/A * magnitude is zero, then intLen is zero. 0N/A * If this MutableBigInteger cannot hold len words, increase the size 0N/A * of the value array to len words. 0N/A * Convert this MutableBigInteger into an int array with no leading 0N/A * zeros, of a length that is equal to this MutableBigInteger's intLen. 0N/A * Sets the int at index+offset in this MutableBigInteger to val. 0N/A * This does not get inlined on all platforms so it is not used 0N/A * as often as originally intended. 0N/A * Sets this MutableBigInteger's value array to the specified array. 0N/A * The intLen is set to the specified length. 0N/A * Sets this MutableBigInteger's value array to a copy of the specified 0N/A * array. The intLen is set to the length of the new array. 0N/A * Sets this MutableBigInteger's value array to a copy of the specified 0N/A * array. The intLen is set to the length of the specified array. 0N/A * Returns true iff this MutableBigInteger has a value of one. 0N/A * Returns true iff this MutableBigInteger has a value of zero. 0N/A * Returns true iff this MutableBigInteger is even. 0N/A * Returns true iff this MutableBigInteger is odd. 0N/A * Returns true iff this MutableBigInteger is in normal form. A 0N/A * MutableBigInteger is in normal form if it has no leading zeros 0N/A * after the offset, and intLen + offset <= value.length. 0N/A * Returns a String representation of this MutableBigInteger in radix 10. 0N/A * Right shift this MutableBigInteger n bits. The MutableBigInteger is left 0N/A * Left shift this MutableBigInteger n bits. 0N/A * If there is enough storage space in this MutableBigInteger already 0N/A * the available space will be used. Space to the right of the used 0N/A * ints in the value array is faster to utilize, so the extra space 0N/A * will be taken from the right if possible. 0N/A // If shift can be done without moving words, do so 0N/A // The array must grow 0N/A // Use space on right 0N/A // Must use space on left 0N/A * A primitive used for division. This method adds in one multiple of the 0N/A * divisor a back to the dividend result at a specified offset. It is used 0N/A * when qhat was estimated too large, and must be adjusted. 0N/A * This method is used for division. It multiplies an n word input a by one 0N/A * word input x, and subtracts the n word product from q. This is needed 0N/A * when subtracting qhat*divisor from dividend. 0N/A for (
int j=
len-
1; j >=
0; j--) {
0N/A * Right shift this MutableBigInteger n bits, where n is 0N/A * Assumes that intLen > 0, n > 0 for speed 0N/A * Left shift this MutableBigInteger n bits, where n is 0N/A * Assumes that intLen > 0, n > 0 for speed 0N/A * Adds the contents of two MutableBigInteger objects.The result 0N/A * is placed within this MutableBigInteger. 0N/A * The contents of the addend are not changed. 0N/A // Add common parts of both numbers 0N/A // Add remainder of the longer number 1246N/A // Result one word longer from carry-out; copy low-order 0N/A * Subtracts the smaller of this and b from the larger and places the 0N/A * result into this MutableBigInteger. 0N/A // Subtract common parts of both numbers 0N/A // Subtract remainder of longer number 0N/A * Subtracts the smaller of a and b from the larger and places the result 0N/A * into the larger. Returns 1 if the answer is in a, -1 if in b, 0 if no 0N/A * operation was performed. 0N/A // Subtract common parts of both numbers 0N/A // Subtract remainder of longer number 0N/A * Multiply the contents of two MutableBigInteger objects. The result is 0N/A * placed into MutableBigInteger z. The contents of y are not changed. 0N/A // Put z into an appropriate state to receive product 0N/A // The first iteration is hoisted out of the loop to avoid extra add 0N/A // Perform the multiplication word by word 0N/A for (
int i =
xLen-
2; i >=
0; i--) {
0N/A // Remove leading zeros from product 0N/A * Multiply the contents of this MutableBigInteger by the word y. The 0N/A * result is placed into z. 0N/A // Perform the multiplication word by word 0N/A * This method is used for division of an n word dividend by a one word 0N/A * divisor. The quotient is placed into quotient. The one word divisor is 1246N/A * @return the remainder of the division is returned. 0N/A // Special case of one word dividend 0N/A // Normalize the divisor 1246N/A * Calculates the quotient of this div b and places the quotient in the 1246N/A * provided MutableBigInteger objects and the remainder object is returned. 0N/A * Uses Algorithm D in Knuth section 4.3.1. 0N/A * Many optimizations to that algorithm have been adapted from the Colin 1246N/A * It special cases one word divisors for speed. The content of b is not 0N/A // Dividend less than divisor 0N/A // Dividend equal to divisor 0N/A // Special case one word divisor 0N/A // Copy divisor value to protect divisor 1246N/A * Internally used to calculate the quotient of this div v and places the 1246N/A * quotient in the provided MutableBigInteger object and the remainder is 1246N/A * @return the remainder of the division will be returned. 1246N/A // Special case on word divisor 1246N/A * Divide this MutableBigInteger by the divisor represented by its magnitude 1246N/A * array. The quotient will be placed into the provided quotient object & 1246N/A * the remainder object is returned. 0N/A // Remainder starts as dividend with space for a leading zero 0N/A // Set the quotient size 0N/A // D1 normalize the divisor 0N/A // First shift will not grow array 0N/A // But this one might 0N/A // Must insert leading 0 in rem if its length did not change 0N/A // D3 Calculate qhat 0N/A // D4 Multiply and subtract 0N/A // D5 Test remainder 0N/A // Store the quotient digit 0N/A * Compare two longs as if they were unsigned. 0N/A * Returns true iff one is bigger than two. 0N/A * This method divides a long quantity by an int to estimate 0N/A * qhat for two multi precision numbers. It is used when 0N/A * the signed value of n is less than zero. 0N/A // Approximate the quotient and remainder 0N/A // Correct the approximation 0N/A // n - q*dlong == r && 0 <= r <dLong, hence we're done. 0N/A * Calculate GCD of this and b. This and b are changed by the computation. 0N/A // Use Euclid's algorithm until the numbers are approximately the 0N/A // same length, then use the binary GCD algorithm to find the GCD. 0N/A * Calculate GCD of this and v. 0N/A * Assumes that this and v are not zero. 0N/A // Algorithm B from Knuth section 4.5.2 0N/A // Special case one word numbers 0N/A * Calculate GCD of a and b interpreted as unsigned integers. 1246N/A // Right shift a & b till their last bits equal to 1. 0N/A if ((a+
0x80000000) > (b+
0x80000000)) {
// a > b as unsigned 0N/A * Returns the modInverse of this mod p. This and p are not affected by 0N/A // Modulus is odd, use Schroeppel's algorithm 0N/A // Base and modulus are even, throw exception 0N/A // Get even part of modulus expressed as a power of 2 0N/A // Construct odd part of modulus 0N/A // Calculate 1/a mod oddMod 0N/A // Calculate 1/a mod evenMod 0N/A // Combine the results using Chinese Remainder Theorem 0N/A * Calculate the multiplicative inverse of this mod 2^k. 0N/A t = (k ==
32 ? t : t & ((
1 << k) -
1));
0N/A * Returns the multiplicative inverse of val mod 2^32. Assumes val is odd. 0N/A // Newton's iteration! 0N/A * Calculate the multiplicative inverse of 2^k mod mod, where mod is odd. 0N/A // Copy the mod to protect original 0N/A * Calculate the multiplicative inverse of this mod mod, where mod is odd. 0N/A * This and mod are not changed by the calculation. 0N/A * This method implements an algorithm due to Richard Schroeppel, that uses 0N/A * the same intermediate representation as Montgomery Reduction 0N/A * ("Montgomery Form"). The algorithm is described in an unpublished 0N/A * manuscript entitled "Fast Modular Reciprocals." 0N/A // Right shift f k times until odd, left shift d k times 0N/A // The Almost Inverse Algorithm 0N/A // If gcd(f, g) != 1, number is not invertible modulo mod 0N/A // If f < g exchange f, g and c, d 0N/A // If f == g (mod 4) 0N/A }
else {
// If f != g (mod 4) 0N/A // Right shift f k times until odd, left shift d k times 0N/A * The Fixup Algorithm 0N/A * Calculates X such that X = C * 2^(-k) (mod P) 0N/A * Assumes C<P and P is odd. 0N/A // Set r to the multiplicative inverse of p mod 2^32 0N/A // V = R * c (mod 2^j) 0N/A // V = R * c (mod 2^j) 0N/A // In theory, c may be greater than p at this point (Very rare!) 0N/A * Uses the extended Euclidean algorithm to compute the modInverse of base 0N/A * mod a modulus that is a power of 2. The modulus is 2^k.