/*

 * Copyright (c) 1999, 2007, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package java.math;

/**

 * A class used to represent multiprecision integers that makes efficient

 * use of allocated space by allowing a number to occupy only part of

 * an array so that the arrays do not have to be reallocated as often.

 * When performing an operation with many iterations the array used to

 * hold a number is only reallocated when necessary and does not have to

 * be the same size as the number it represents. A mutable number allows

 * calculations to occur on the same number without having to create

 * a new number for every step of the calculation as occurs with

 * BigIntegers.

 *

 * @see     BigInteger

 * @author  Michael McCloskey

 * @since   1.3

 */

import java.util.Arrays;

import static java.math.BigInteger.LONG_MASK;

import static java.math.BigDecimal.INFLATED;

class MutableBigInteger {

    /**

     * Holds the magnitude of this MutableBigInteger in big endian order.

     * The magnitude may start at an offset into the value array, and it may

     * end before the length of the value array.

     */

    int[] value;

    /**

     * The number of ints of the value array that are currently used

     * to hold the magnitude of this MutableBigInteger. The magnitude starts

     * at an offset and offset + intLen may be less than value.length.

     */

    int intLen;

    /**

     * The offset into the value array where the magnitude of this

     * MutableBigInteger begins.

     */

    int offset = 0;

    // Constants

    /**

     * MutableBigInteger with one element value array with the value 1. Used by

     * BigDecimal divideAndRound to increment the quotient. Use this constant

     * only when the method is not going to modify this object.

     */

    static final MutableBigInteger ONE = new MutableBigInteger(1);

    // Constructors

    /**

     * The default constructor. An empty MutableBigInteger is created with

     * a one word capacity.

     */

    MutableBigInteger() {

        value = new int[1];

        intLen = 0;

    }

    /**

     * Construct a new MutableBigInteger with a magnitude specified by

     * the int val.

     */

    MutableBigInteger(int val) {

        value = new int[1];

        intLen = 1;

        value[0] = val;

    }

    /**

     * Construct a new MutableBigInteger with the specified value array

     * up to the length of the array supplied.

     */

    MutableBigInteger(int[] val) {

        value = val;

        intLen = val.length;

    }

    /**

     * Construct a new MutableBigInteger with a magnitude equal to the

     * specified BigInteger.

     */

    MutableBigInteger(BigInteger b) {

        intLen = b.mag.length;

        value = Arrays.copyOf(b.mag, intLen);

    }

    /**

     * Construct a new MutableBigInteger with a magnitude equal to the

     * specified MutableBigInteger.

     */

    MutableBigInteger(MutableBigInteger val) {

        intLen = val.intLen;

        value = Arrays.copyOfRange(val.value, val.offset, val.offset + intLen);

    }

    /**

     * Internal helper method to return the magnitude array. The caller is not

     * supposed to modify the returned array.

     */

    private int[] getMagnitudeArray() {

        if (offset > 0 || value.length != intLen)

            return Arrays.copyOfRange(value, offset, offset + intLen);

        return value;

    }

    /**

     * Convert this MutableBigInteger to a long value. The caller has to make

     * sure this MutableBigInteger can be fit into long.

     */

    private long toLong() {

        assert (intLen <= 2) : "this MutableBigInteger exceeds the range of long";

        if (intLen == 0)

            return 0;

        long d = value[offset] & LONG_MASK;

        return (intLen == 2) ? d << 32 | (value[offset + 1] & LONG_MASK) : d;

    }

    /**

     * Convert this MutableBigInteger to a BigInteger object.

     */

    BigInteger toBigInteger(int sign) {

        if (intLen == 0 || sign == 0)

            return BigInteger.ZERO;

        return new BigInteger(getMagnitudeArray(), sign);

    }

    /**

     * Convert this MutableBigInteger to BigDecimal object with the specified sign

     * and scale.

     */

    BigDecimal toBigDecimal(int sign, int scale) {

        if (intLen == 0 || sign == 0)

            return BigDecimal.valueOf(0, scale);

        int[] mag = getMagnitudeArray();

        int len = mag.length;

        int d = mag[0];

        // If this MutableBigInteger can't be fit into long, we need to

        // make a BigInteger object for the resultant BigDecimal object.

        if (len > 2 || (d < 0 && len == 2))

            return new BigDecimal(new BigInteger(mag, sign), INFLATED, scale, 0);

        long v = (len == 2) ?

            ((mag[1] & LONG_MASK) | (d & LONG_MASK) << 32) :

            d & LONG_MASK;

        return new BigDecimal(null, sign == -1 ? -v : v, scale, 0);

    }

    /**

     * Clear out a MutableBigInteger for reuse.

     */

    void clear() {

        offset = intLen = 0;

        for (int index=0, n=value.length; index < n; index++)

            value[index] = 0;

    }

    /**

     * Set a MutableBigInteger to zero, removing its offset.

     */

    void reset() {

        offset = intLen = 0;

    }

    /**

     * Compare the magnitude of two MutableBigIntegers. Returns -1, 0 or 1

     * as this MutableBigInteger is numerically less than, equal to, or

     * greater than <tt>b</tt>.

     */

    final int compare(MutableBigInteger b) {

        int blen = b.intLen;

        if (intLen < blen)

            return -1;

        if (intLen > blen)

           return 1;

        // Add Integer.MIN_VALUE to make the comparison act as unsigned integer

        // comparison.

        int[] bval = b.value;

        for (int i = offset, j = b.offset; i < intLen + offset; i++, j++) {

            int b1 = value[i] + 0x80000000;

            int b2 = bval[j]  + 0x80000000;

            if (b1 < b2)

                return -1;

            if (b1 > b2)

                return 1;

        }

        return 0;

    }

    /**

     * Compare this against half of a MutableBigInteger object (Needed for

     * remainder tests).

     * Assumes no leading unnecessary zeros, which holds for results

     * from divide().

     */

    final int compareHalf(MutableBigInteger b) {

        int blen = b.intLen;

        int len = intLen;

        if (len <= 0)

            return blen <=0 ? 0 : -1;

        if (len > blen)

            return 1;

        if (len < blen - 1)

            return -1;

        int[] bval = b.value;

        int bstart = 0;

        int carry = 0;

        // Only 2 cases left:len == blen or len == blen - 1

        if (len != blen) { // len == blen - 1

            if (bval[bstart] == 1) {

                ++bstart;

                carry = 0x80000000;

            } else

                return -1;

        }

        // compare values with right-shifted values of b,

        // carrying shifted-out bits across words

        int[] val = value;

        for (int i = offset, j = bstart; i < len + offset;) {

            int bv = bval[j++];

            long hb = ((bv >>> 1) + carry) & LONG_MASK;

            long v = val[i++] & LONG_MASK;

            if (v != hb)

                return v < hb ? -1 : 1;

            carry = (bv & 1) << 31; // carray will be either 0x80000000 or 0

        }

        return carry == 0? 0 : -1;

    }

    /**

     * Return the index of the lowest set bit in this MutableBigInteger. If the

     * magnitude of this MutableBigInteger is zero, -1 is returned.

     */

    private final int getLowestSetBit() {

        if (intLen == 0)

            return -1;

        int j, b;

        for (j=intLen-1; (j>0) && (value[j+offset]==0); j--)

            ;

        b = value[j+offset];

        if (b==0)

            return -1;

        return ((intLen-1-j)<<5) + Integer.numberOfTrailingZeros(b);

    }

    /**

     * Return the int in use in this MutableBigInteger at the specified

     * index. This method is not used because it is not inlined on all

     * platforms.

     */

    private final int getInt(int index) {

        return value[offset+index];

    }

    /**

     * Return a long which is equal to the unsigned value of the int in

     * use in this MutableBigInteger at the specified index. This method is

     * not used because it is not inlined on all platforms.

     */

    private final long getLong(int index) {

        return value[offset+index] & LONG_MASK;

    }

    /**

     * Ensure that the MutableBigInteger is in normal form, specifically

     * making sure that there are no leading zeros, and that if the

     * magnitude is zero, then intLen is zero.

     */

    final void normalize() {

        if (intLen == 0) {

            offset = 0;

            return;

        }

        int index = offset;

        if (value[index] != 0)

            return;

        int indexBound = index+intLen;

        do {

            index++;

        } while(index < indexBound && value[index]==0);

        int numZeros = index - offset;

        intLen -= numZeros;

        offset = (intLen==0 ?  0 : offset+numZeros);

    }

    /**

     * If this MutableBigInteger cannot hold len words, increase the size

     * of the value array to len words.

     */

    private final void ensureCapacity(int len) {

        if (value.length < len) {

            value = new int[len];

            offset = 0;

            intLen = len;

        }

    }

    /**

     * Convert this MutableBigInteger into an int array with no leading

     * zeros, of a length that is equal to this MutableBigInteger's intLen.

     */

    int[] toIntArray() {

        int[] result = new int[intLen];

        for(int i=0; i<intLen; i++)

            result[i] = value[offset+i];

        return result;

    }

    /**

     * Sets the int at index+offset in this MutableBigInteger to val.

     * This does not get inlined on all platforms so it is not used

     * as often as originally intended.

     */

    void setInt(int index, int val) {

        value[offset + index] = val;

    }

    /**

     * Sets this MutableBigInteger's value array to the specified array.

     * The intLen is set to the specified length.

     */

    void setValue(int[] val, int length) {

        value = val;

        intLen = length;

        offset = 0;

    }

    /**

     * Sets this MutableBigInteger's value array to a copy of the specified

     * array. The intLen is set to the length of the new array.

     */

    void copyValue(MutableBigInteger src) {

        int len = src.intLen;

        if (value.length < len)

            value = new int[len];

        System.arraycopy(src.value, src.offset, value, 0, len);

        intLen = len;

        offset = 0;

    }

    /**

     * Sets this MutableBigInteger's value array to a copy of the specified

     * array. The intLen is set to the length of the specified array.

     */

    void copyValue(int[] val) {

        int len = val.length;

        if (value.length < len)

            value = new int[len];

        System.arraycopy(val, 0, value, 0, len);

        intLen = len;

        offset = 0;

    }

    /**

     * Returns true iff this MutableBigInteger has a value of one.

     */

    boolean isOne() {

        return (intLen == 1) && (value[offset] == 1);

    }

    /**

     * Returns true iff this MutableBigInteger has a value of zero.

     */

    boolean isZero() {

        return (intLen == 0);

    }

    /**

     * Returns true iff this MutableBigInteger is even.

     */

    boolean isEven() {

        return (intLen == 0) || ((value[offset + intLen - 1] & 1) == 0);

    }

    /**

     * Returns true iff this MutableBigInteger is odd.

     */

    boolean isOdd() {

        return isZero() ? false : ((value[offset + intLen - 1] & 1) == 1);

    }

    /**

     * Returns true iff this MutableBigInteger is in normal form. A

     * MutableBigInteger is in normal form if it has no leading zeros

     * after the offset, and intLen + offset <= value.length.

     */

    boolean isNormal() {

        if (intLen + offset > value.length)

            return false;

        if (intLen ==0)

            return true;

        return (value[offset] != 0);

    }

    /**

     * Returns a String representation of this MutableBigInteger in radix 10.

     */

    public String toString() {

        BigInteger b = toBigInteger(1);

        return b.toString();

    }

    /**

     * Right shift this MutableBigInteger n bits. The MutableBigInteger is left

     * in normal form.

     */

    void rightShift(int n) {

        if (intLen == 0)

            return;

        int nInts = n >>> 5;

        int nBits = n & 0x1F;

        this.intLen -= nInts;

        if (nBits == 0)

            return;

        int bitsInHighWord = BigInteger.bitLengthForInt(value[offset]);

        if (nBits >= bitsInHighWord) {

            this.primitiveLeftShift(32 - nBits);

            this.intLen--;

        } else {

            primitiveRightShift(nBits);

        }

    }

    /**

     * Left shift this MutableBigInteger n bits.

     */

    void leftShift(int n) {

        /*

         * If there is enough storage space in this MutableBigInteger already

         * the available space will be used. Space to the right of the used

         * ints in the value array is faster to utilize, so the extra space

         * will be taken from the right if possible.

         */

        if (intLen == 0)

           return;

        int nInts = n >>> 5;

        int nBits = n&0x1F;

        int bitsInHighWord = BigInteger.bitLengthForInt(value[offset]);

        // If shift can be done without moving words, do so

        if (n <= (32-bitsInHighWord)) {

            primitiveLeftShift(nBits);

            return;

        }

        int newLen = intLen + nInts +1;

        if (nBits <= (32-bitsInHighWord))

            newLen--;

        if (value.length < newLen) {

            // The array must grow

            int[] result = new int[newLen];

            for (int i=0; i<intLen; i++)

                result[i] = value[offset+i];

            setValue(result, newLen);

        } else if (value.length - offset >= newLen) {

            // Use space on right

            for(int i=0; i<newLen - intLen; i++)

                value[offset+intLen+i] = 0;

        } else {

            // Must use space on left

            for (int i=0; i<intLen; i++)

                value[i] = value[offset+i];

            for (int i=intLen; i<newLen; i++)

                value[i] = 0;

            offset = 0;

        }

        intLen = newLen;

        if (nBits == 0)

            return;

        if (nBits <= (32-bitsInHighWord))

            primitiveLeftShift(nBits);

        else

            primitiveRightShift(32 -nBits);

    }

    /**

     * A primitive used for division. This method adds in one multiple of the

     * divisor a back to the dividend result at a specified offset. It is used

     * when qhat was estimated too large, and must be adjusted.

     */

    private int divadd(int[] a, int[] result, int offset) {

        long carry = 0;

        for (int j=a.length-1; j >= 0; j--) {

            long sum = (a[j] & LONG_MASK) +

                       (result[j+offset] & LONG_MASK) + carry;

            result[j+offset] = (int)sum;

            carry = sum >>> 32;

        }

        return (int)carry;

    }

    /**

     * This method is used for division. It multiplies an n word input a by one

     * word input x, and subtracts the n word product from q. This is needed

     * when subtracting qhat*divisor from dividend.

     */

    private int mulsub(int[] q, int[] a, int x, int len, int offset) {

        long xLong = x & LONG_MASK;

        long carry = 0;

        offset += len;

        for (int j=len-1; j >= 0; j--) {

            long product = (a[j] & LONG_MASK) * xLong + carry;

            long difference = q[offset] - product;

            q[offset--] = (int)difference;

            carry = (product >>> 32)

                     + (((difference & LONG_MASK) >

                         (((~(int)product) & LONG_MASK))) ? 1:0);

        }

        return (int)carry;

    }

    /**

     * Right shift this MutableBigInteger n bits, where n is

     * less than 32.

     * Assumes that intLen > 0, n > 0 for speed

     */

    private final void primitiveRightShift(int n) {

        int[] val = value;

        int n2 = 32 - n;

        for (int i=offset+intLen-1, c=val[i]; i>offset; i--) {

            int b = c;

            c = val[i-1];

            val[i] = (c << n2) | (b >>> n);

        }

        val[offset] >>>= n;

    }

    /**

     * Left shift this MutableBigInteger n bits, where n is

     * less than 32.

     * Assumes that intLen > 0, n > 0 for speed

     */

    private final void primitiveLeftShift(int n) {

        int[] val = value;

        int n2 = 32 - n;

        for (int i=offset, c=val[i], m=i+intLen-1; i<m; i++) {

            int b = c;

            c = val[i+1];

            val[i] = (b << n) | (c >>> n2);

        }

        val[offset+intLen-1] <<= n;

    }

    /**

     * Adds the contents of two MutableBigInteger objects.The result

     * is placed within this MutableBigInteger.

     * The contents of the addend are not changed.

     */

    void add(MutableBigInteger addend) {

        int x = intLen;

        int y = addend.intLen;

        int resultLen = (intLen > addend.intLen ? intLen : addend.intLen);

        int[] result = (value.length < resultLen ? new int[resultLen] : value);

        int rstart = result.length-1;

        long sum;

        long carry = 0;

        // Add common parts of both numbers

        while(x>0 && y>0) {

            x--; y--;

            sum = (value[x+offset] & LONG_MASK) +

                (addend.value[y+addend.offset] & LONG_MASK) + carry;

            result[rstart--] = (int)sum;

            carry = sum >>> 32;

        }

        // Add remainder of the longer number

        while(x>0) {

            x--;

            if (carry == 0 && result == value && rstart == (x + offset))

                return;

            sum = (value[x+offset] & LONG_MASK) + carry;

            result[rstart--] = (int)sum;

            carry = sum >>> 32;

        }

        while(y>0) {

            y--;

            sum = (addend.value[y+addend.offset] & LONG_MASK) + carry;

            result[rstart--] = (int)sum;

            carry = sum >>> 32;

        }

        if (carry > 0) { // Result must grow in length

            resultLen++;

            if (result.length < resultLen) {

                int temp[] = new int[resultLen];

                // Result one word longer from carry-out; copy low-order

                // bits into new result.

                System.arraycopy(result, 0, temp, 1, result.length);

                temp[0] = 1;

                result = temp;

            } else {

                result[rstart--] = 1;

            }

        }

        value = result;

        intLen = resultLen;

        offset = result.length - resultLen;

    }

    /**

     * Subtracts the smaller of this and b from the larger and places the

     * result into this MutableBigInteger.

     */

    int subtract(MutableBigInteger b) {

        MutableBigInteger a = this;

        int[] result = value;

        int sign = a.compare(b);

        if (sign == 0) {

            reset();

            return 0;

        }

        if (sign < 0) {

            MutableBigInteger tmp = a;

            a = b;

            b = tmp;

        }

        int resultLen = a.intLen;

        if (result.length < resultLen)

            result = new int[resultLen];

        long diff = 0;

        int x = a.intLen;

        int y = b.intLen;

        int rstart = result.length - 1;

        // Subtract common parts of both numbers

        while (y>0) {

            x--; y--;

            diff = (a.value[x+a.offset] & LONG_MASK) -

                   (b.value[y+b.offset] & LONG_MASK) - ((int)-(diff>>32));

            result[rstart--] = (int)diff;

        }

        // Subtract remainder of longer number

        while (x>0) {

            x--;

            diff = (a.value[x+a.offset] & LONG_MASK) - ((int)-(diff>>32));

            result[rstart--] = (int)diff;

        }

        value = result;

        intLen = resultLen;

        offset = value.length - resultLen;

        normalize();

        return sign;

    }

    /**

     * Subtracts the smaller of a and b from the larger and places the result

     * into the larger. Returns 1 if the answer is in a, -1 if in b, 0 if no

     * operation was performed.

     */

    private int difference(MutableBigInteger b) {

        MutableBigInteger a = this;

        int sign = a.compare(b);

        if (sign ==0)

            return 0;

        if (sign < 0) {

            MutableBigInteger tmp = a;

            a = b;

            b = tmp;

        }

        long diff = 0;

        int x = a.intLen;

        int y = b.intLen;

        // Subtract common parts of both numbers

        while (y>0) {

            x--; y--;

            diff = (a.value[a.offset+ x] & LONG_MASK) -

                (b.value[b.offset+ y] & LONG_MASK) - ((int)-(diff>>32));

            a.value[a.offset+x] = (int)diff;

        }

        // Subtract remainder of longer number

        while (x>0) {

            x--;

            diff = (a.value[a.offset+ x] & LONG_MASK) - ((int)-(diff>>32));

            a.value[a.offset+x] = (int)diff;

        }

        a.normalize();

        return sign;

    }

    /**

     * Multiply the contents of two MutableBigInteger objects. The result is

     * placed into MutableBigInteger z. The contents of y are not changed.

     */

    void multiply(MutableBigInteger y, MutableBigInteger z) {

        int xLen = intLen;

        int yLen = y.intLen;

        int newLen = xLen + yLen;

        // Put z into an appropriate state to receive product

        if (z.value.length < newLen)

            z.value = new int[newLen];

        z.offset = 0;

        z.intLen = newLen;

        // The first iteration is hoisted out of the loop to avoid extra add

        long carry = 0;

        for (int j=yLen-1, k=yLen+xLen-1; j >= 0; j--, k--) {

                long product = (y.value[j+y.offset] & LONG_MASK) *

                               (value[xLen-1+offset] & LONG_MASK) + carry;

                z.value[k] = (int)product;

                carry = product >>> 32;

        }

        z.value[xLen-1] = (int)carry;

        // Perform the multiplication word by word

        for (int i = xLen-2; i >= 0; i--) {

            carry = 0;

            for (int j=yLen-1, k=yLen+i; j >= 0; j--, k--) {

                long product = (y.value[j+y.offset] & LONG_MASK) *

                               (value[i+offset] & LONG_MASK) +

                               (z.value[k] & LONG_MASK) + carry;

                z.value[k] = (int)product;

                carry = product >>> 32;

            }

            z.value[i] = (int)carry;

        }

        // Remove leading zeros from product

        z.normalize();

    }

    /**

     * Multiply the contents of this MutableBigInteger by the word y. The

     * result is placed into z.

     */

    void mul(int y, MutableBigInteger z) {

        if (y == 1) {

            z.copyValue(this);

            return;

        }

        if (y == 0) {

            z.clear();

            return;

        }

        // Perform the multiplication word by word

        long ylong = y & LONG_MASK;

        int[] zval = (z.value.length<intLen+1 ? new int[intLen + 1]

                                              : z.value);

        long carry = 0;

        for (int i = intLen-1; i >= 0; i--) {

            long product = ylong * (value[i+offset] & LONG_MASK) + carry;

            zval[i+1] = (int)product;

            carry = product >>> 32;

        }

        if (carry == 0) {

            z.offset = 1;

            z.intLen = intLen;

        } else {

            z.offset = 0;

            z.intLen = intLen + 1;

            zval[0] = (int)carry;

        }

        z.value = zval;

    }

     /**

     * This method is used for division of an n word dividend by a one word

     * divisor. The quotient is placed into quotient. The one word divisor is

     * specified by divisor.

     *

     * @return the remainder of the division is returned.

     *

     */

    int divideOneWord(int divisor, MutableBigInteger quotient) {

        long divisorLong = divisor & LONG_MASK;

        // Special case of one word dividend

        if (intLen == 1) {

            long dividendValue = value[offset] & LONG_MASK;

            int q = (int) (dividendValue / divisorLong);

            int r = (int) (dividendValue - q * divisorLong);

            quotient.value[0] = q;

            quotient.intLen = (q == 0) ? 0 : 1;

            quotient.offset = 0;

            return r;

        }

        if (quotient.value.length < intLen)

            quotient.value = new int[intLen];

        quotient.offset = 0;

        quotient.intLen = intLen;

        // Normalize the divisor

        int shift = Integer.numberOfLeadingZeros(divisor);

        int rem = value[offset];

        long remLong = rem & LONG_MASK;

        if (remLong < divisorLong) {

            quotient.value[0] = 0;

        } else {

            quotient.value[0] = (int)(remLong / divisorLong);

            rem = (int) (remLong - (quotient.value[0] * divisorLong));

            remLong = rem & LONG_MASK;

        }

        int xlen = intLen;

        int[] qWord = new int[2];

        while (--xlen > 0) {

            long dividendEstimate = (remLong<<32) |

                (value[offset + intLen - xlen] & LONG_MASK);

            if (dividendEstimate >= 0) {

                qWord[0] = (int) (dividendEstimate / divisorLong);

                qWord[1] = (int) (dividendEstimate - qWord[0] * divisorLong);

            } else {

                divWord(qWord, dividendEstimate, divisor);

            }

            quotient.value[intLen - xlen] = qWord[0];

            rem = qWord[1];

            remLong = rem & LONG_MASK;

        }

        quotient.normalize();

        // Unnormalize

        if (shift > 0)

            return rem % divisor;

        else

            return rem;

    }

    /**

     * Calculates the quotient of this div b and places the quotient in the

     * provided MutableBigInteger objects and the remainder object is returned.

     *

     * Uses Algorithm D in Knuth section 4.3.1.

     * Many optimizations to that algorithm have been adapted from the Colin

     * Plumb C library.

     * It special cases one word divisors for speed. The content of b is not

     * changed.

     *

     */

    MutableBigInteger divide(MutableBigInteger b, MutableBigInteger quotient) {

        if (b.intLen == 0)

            throw new ArithmeticException("BigInteger divide by zero");

        // Dividend is zero

        if (intLen == 0) {

            quotient.intLen = quotient.offset;

            return new MutableBigInteger();

        }

        int cmp = compare(b);

        // Dividend less than divisor

        if (cmp < 0) {

            quotient.intLen = quotient.offset = 0;

            return new MutableBigInteger(this);

        }

        // Dividend equal to divisor

        if (cmp == 0) {

            quotient.value[0] = quotient.intLen = 1;

            quotient.offset = 0;

            return new MutableBigInteger();

        }

        quotient.clear();

        // Special case one word divisor

        if (b.intLen == 1) {

            int r = divideOneWord(b.value[b.offset], quotient);

            if (r == 0)

                return new MutableBigInteger();

            return new MutableBigInteger(r);

        }

        // Copy divisor value to protect divisor

        int[] div = Arrays.copyOfRange(b.value, b.offset, b.offset + b.intLen);

        return divideMagnitude(div, quotient);

    }

    /**

     * Internally used  to calculate the quotient of this div v and places the

     * quotient in the provided MutableBigInteger object and the remainder is

     * returned.

     *

     * @return the remainder of the division will be returned.

     */

    long divide(long v, MutableBigInteger quotient) {

        if (v == 0)

            throw new ArithmeticException("BigInteger divide by zero");

        // Dividend is zero

        if (intLen == 0) {

            quotient.intLen = quotient.offset = 0;

            return 0;

        }

        if (v < 0)

            v = -v;

        int d = (int)(v >>> 32);

        quotient.clear();

        // Special case on word divisor

        if (d == 0)

            return divideOneWord((int)v, quotient) & LONG_MASK;

        else {

            int[] div = new int[]{ d, (int)(v & LONG_MASK) };

            return divideMagnitude(div, quotient).toLong();

        }

    }

    /**

     * Divide this MutableBigInteger by the divisor represented by its magnitude

     * array. The quotient will be placed into the provided quotient object &

     * the remainder object is returned.

     */

    private MutableBigInteger divideMagnitude(int[] divisor,

                                              MutableBigInteger quotient) {

        // Remainder starts as dividend with space for a leading zero

        MutableBigInteger rem = new MutableBigInteger(new int[intLen + 1]);

        System.arraycopy(value, offset, rem.value, 1, intLen);

        rem.intLen = intLen;

        rem.offset = 1;

        int nlen = rem.intLen;

        // Set the quotient size

        int dlen = divisor.length;

        int limit = nlen - dlen + 1;

        if (quotient.value.length < limit) {

            quotient.value = new int[limit];

            quotient.offset = 0;

        }

        quotient.intLen = limit;

        int[] q = quotient.value;

        // D1 normalize the divisor

        int shift = Integer.numberOfLeadingZeros(divisor[0]);

        if (shift > 0) {

            // First shift will not grow array

            BigInteger.primitiveLeftShift(divisor, dlen, shift);

            // But this one might

            rem.leftShift(shift);

        }

        // Must insert leading 0 in rem if its length did not change

        if (rem.intLen == nlen) {

            rem.offset = 0;

            rem.value[0] = 0;

            rem.intLen++;

        }

        int dh = divisor[0];

        long dhLong = dh & LONG_MASK;

        int dl = divisor[1];

        int[] qWord = new int[2];