/*
 * Copyright (c) 1996, 2013, Oracle and/or its affiliates. All rights reserved.
 * Copyright (C) 2017-2023 MicroEJ Corp. - EDC compliance and optimizations.
 * 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.
 */

/*
 * Portions Copyright (c) 1995  Colin Plumb.  All rights reserved.
 */

package java.time;

import java.util.Arrays;

import ej.annotation.Nullable;

/**
 * Immutable arbitrary-precision integers. All operations behave as if BigIntegers were represented in two's-complement
 * notation (like Java's primitive integer types). BigInteger provides analogues to all of Java's primitive integer
 * operators, and all relevant methods from java.lang.Math. Additionally, BigInteger provides operations for modular
 * arithmetic, GCD calculation, primality testing, prime generation, bit manipulation, and a few other miscellaneous
 * operations.
 *
 * <p>
 * Semantics of arithmetic operations exactly mimic those of Java's integer arithmetic operators, as defined in <i>The
 * Java Language Specification</i>. For example, division by zero throws an {@code ArithmeticException}, and division of
 * a negative by a positive yields a negative (or zero) remainder. All of the details in the Spec concerning overflow
 * are ignored, as BigIntegers are made as large as necessary to accommodate the results of an operation.
 *
 * <p>
 * Semantics of shift operations extend those of Java's shift operators to allow for negative shift distances. A
 * right-shift with a negative shift distance results in a left shift, and vice-versa. The unsigned right shift operator
 * ({@code >>>}) is omitted, as this operation makes little sense in combination with the "infinite word size"
 * abstraction provided by this class.
 *
 * <p>
 * Semantics of bitwise logical operations exactly mimic those of Java's bitwise integer operators. The binary operators
 * ({@code and}, {@code or}, {@code xor}) implicitly perform sign extension on the shorter of the two operands prior to
 * performing the operation.
 *
 * <p>
 * Comparison operations perform signed integer comparisons, analogous to those performed by Java's relational and
 * equality operators.
 *
 * <p>
 * Modular arithmetic operations are provided to compute residues, perform exponentiation, and compute multiplicative
 * inverses. These methods always return a non-negative result, between {@code 0} and {@code (modulus - 1)}, inclusive.
 *
 * <p>
 * Bit operations operate on a single bit of the two's-complement representation of their operand. If necessary, the
 * operand is sign- extended so that it contains the designated bit. None of the single-bit operations can produce a
 * BigInteger with a different sign from the BigInteger being operated on, as they affect only a single bit, and the
 * "infinite word size" abstraction provided by this class ensures that there are infinitely many "virtual sign bits"
 * preceding each BigInteger.
 *
 * <p>
 * For the sake of brevity and clarity, pseudo-code is used throughout the descriptions of BigInteger methods. The
 * pseudo-code expression {@code (i + j)} is shorthand for "a BigInteger whose value is that of the BigInteger {@code i}
 * plus that of the BigInteger {@code j}." The pseudo-code expression {@code (i == j)} is shorthand for "{@code true} if
 * and only if the BigInteger {@code i} represents the same value as the BigInteger {@code j}." Other pseudo-code
 * expressions are interpreted similarly.
 *
 * <p>
 * All methods and constructors in this class throw {@code NullPointerException} when passed a null object reference for
 * any input parameter.
 *
 * BigInteger must support values in the range -2<sup>{@code Integer.MAX_VALUE}</sup> (exclusive) to +2
 * <sup>{@code Integer.MAX_VALUE}</sup> (exclusive) and may support values outside of that range.
 *
 * The range of probable prime values is limited and may be less than the full supported positive range of
 * {@code BigInteger}. The range must be at least 1 to 2<sup>500000000</sup>.
 *
 * implNote: BigInteger constructors and operations throw {@code ArithmeticException} when the result is out of the
 * supported range of -2<sup>{@code Integer.MAX_VALUE}</sup> (exclusive) to +2<sup> {@code Integer.MAX_VALUE}</sup>
 * (exclusive).
 *
 * @author Josh Bloch
 * @author Michael McCloskey
 * @author Alan Eliasen
 * @author Timothy Buktu
 * @since JDK1.1
 */

class BigInteger extends Number implements Comparable<BigInteger> {
	/**
	 * The signum of this BigInteger: -1 for negative, 0 for zero, or 1 for positive. Note that the BigInteger zero
	 * <i>must</i> have a signum of 0. This is necessary to ensures that there is exactly one representation for each
	 * BigInteger value.
	 *
	 * @serial
	 */
	final int signum;

	/**
	 * The magnitude of this BigInteger, in <i>big-endian</i> order: the zeroth element of this array is the
	 * most-significant int of the magnitude. The magnitude must be "minimal" in that the most-significant int (
	 * {@code mag[0]}) must be non-zero. This is necessary to ensure that there is exactly one representation for each
	 * BigInteger value. Note that this implies that the BigInteger zero has a zero-length mag array.
	 */
	final int[] mag;

	/**
	 * This mask is used to obtain the value of an int as if it were unsigned.
	 */
	final static long LONG_MASK = 0xffffffffL;

	/**
	 * This constant limits {@code mag.length} of BigIntegers to the supported range.
	 */
	private static final int MAX_MAG_LENGTH = Integer.MAX_VALUE / Integer.SIZE + 1; // (1 << 26)

	/**
	 * The threshold value for using Karatsuba multiplication. If the number of ints in both mag arrays are greater than
	 * this number, then Karatsuba multiplication will be used. This value is found experimentally to work well.
	 */
	private static final int KARATSUBA_THRESHOLD = 80;

	/**
	 * The threshold value for using 3-way Toom-Cook multiplication. If the number of ints in each mag array is greater
	 * than the Karatsuba threshold, and the number of ints in at least one of the mag arrays is greater than this
	 * threshold, then Toom-Cook multiplication will be used.
	 */
	private static final int TOOM_COOK_THRESHOLD = 240;

	/**
	 * The threshold value for using Karatsuba squaring. If the number of ints in the number are larger than this value,
	 * Karatsuba squaring will be used. This value is found experimentally to work well.
	 */
	private static final int KARATSUBA_SQUARE_THRESHOLD = 128;

	/**
	 * The threshold value for using Toom-Cook squaring. If the number of ints in the number are larger than this value,
	 * Toom-Cook squaring will be used. This value is found experimentally to work well.
	 */
	private static final int TOOM_COOK_SQUARE_THRESHOLD = 216;

	/**
	 * The threshold value for using Burnikel-Ziegler division. If the number of ints in the divisor are larger than
	 * this value, Burnikel-Ziegler division may be used. This value is found experimentally to work well.
	 */
	static final int BURNIKEL_ZIEGLER_THRESHOLD = 80;

	/**
	 * The offset value for using Burnikel-Ziegler division. If the number of ints in the divisor exceeds the
	 * Burnikel-Ziegler threshold, and the number of ints in the dividend is greater than the number of ints in the
	 * divisor plus this value, Burnikel-Ziegler division will be used. This value is found experimentally to work well.
	 */
	static final int BURNIKEL_ZIEGLER_OFFSET = 40;

	/**
	 * The threshold value for using squaring code to perform multiplication of a {@code BigInteger} instance by itself.
	 * If the number of ints in the number are larger than this value, {@code multiply(this)} will return
	 * {@code square()}.
	 */
	private static final int MULTIPLY_SQUARE_THRESHOLD = 20;

	// Constructors


	/**
	 * This internal constructor differs from its public cousin with the arguments reversed in two ways: it assumes that
	 * its arguments are correct, and it doesn't copy the magnitude array.
	 */
	BigInteger(int[] magnitude, int signum) {
		this.signum = (magnitude.length == 0 ? 0 : signum);
		this.mag = magnitude;
		if (this.mag.length >= MAX_MAG_LENGTH) {
			checkRange();
		}
	}

	/**
	 * Throws an {@code ArithmeticException} if the {@code BigInteger} would be out of the supported range.
	 *
	 * @throws ArithmeticException
	 *             if {@code this} exceeds the supported range.
	 */
	private void checkRange() {
		if (this.mag.length > MAX_MAG_LENGTH || this.mag.length == MAX_MAG_LENGTH && this.mag[0] < 0) {
			reportOverflow();
		}
	}

	private static void reportOverflow() {
		throw new ArithmeticException("BigInteger would overflow supported range");
	}

	// Static Factory Methods

	/**
	 * Returns a BigInteger whose value is equal to that of the specified {@code long}. This "static factory method" is
	 * provided in preference to a ({@code long}) constructor because it allows for reuse of frequently used
	 * BigIntegers.
	 *
	 * @param val
	 *            value of the BigInteger to return.
	 * @return a BigInteger with the specified value.
	 */
	static BigInteger valueOf(long val) {
		if (val == 0) {
			return ZERO;
		}

		return new BigInteger(val);
	}

	/**
	 * Constructs a BigInteger with the specified value, which may not be zero.
	 */
	private BigInteger(long val) {
		if (val < 0) {
			val = -val;
			this.signum = -1;
		} else {
			this.signum = 1;
		}

		int highWord = (int) (val >>> 32);
		if (highWord == 0) {
			this.mag = new int[1];
			this.mag[0] = (int) val;
		} else {
			this.mag = new int[2];
			this.mag[0] = highWord;
			this.mag[1] = (int) val;
		}
	}


	// Constants

	/**
	 * The BigInteger constant zero.
	 */
	static final BigInteger ZERO = new BigInteger(new int[0], 0);


	// Arithmetic Operations

	/**
	 * Returns a BigInteger whose value is {@code (this + val)}.
	 *
	 * @param val
	 *            value to be added to this BigInteger.
	 * @return {@code this + val}
	 */
	BigInteger add(BigInteger val) {
		if (val.signum == 0) {
			return this;
		}
		if (this.signum == 0) {
			return val;
		}
		if (val.signum == this.signum) {
			return new BigInteger(add(this.mag, val.mag), this.signum);
		}

		int cmp = compareMagnitude(val);
		if (cmp == 0) {
			return ZERO;
		}
		int[] resultMag = (cmp > 0 ? subtract(this.mag, val.mag) : subtract(val.mag, this.mag));
		resultMag = trustedStripLeadingZeroInts(resultMag);

		return new BigInteger(resultMag, cmp == this.signum ? 1 : -1);
	}


	/**
	 * Adds the contents of the int arrays x and y. This method allocates a new int array to hold the answer and returns
	 * a reference to that array.
	 */
	private static int[] add(int[] x, int[] y) {
		// If x is shorter, swap the two arrays
		if (x.length < y.length) {
			int[] tmp = x;
			x = y;
			y = tmp;
		}

		int xIndex = x.length;
		int yIndex = y.length;
		int result[] = new int[xIndex];
		long sum = 0;
		if (yIndex == 1) {
			sum = (x[--xIndex] & LONG_MASK) + (y[0] & LONG_MASK);
			result[xIndex] = (int) sum;
		} else {
			// Add common parts of both numbers
			while (yIndex > 0) {
				sum = (x[--xIndex] & LONG_MASK) + (y[--yIndex] & LONG_MASK) + (sum >>> 32);
				result[xIndex] = (int) sum;
			}
		}
		// Copy remainder of longer number while carry propagation is required
		boolean carry = (sum >>> 32 != 0);
		while (xIndex > 0 && carry) {
			carry = ((result[--xIndex] = x[xIndex] + 1) == 0);
		}

		// Copy remainder of longer number
		while (xIndex > 0) {
			result[--xIndex] = x[xIndex];
		}

		// Grow result if necessary
		if (carry) {
			int bigger[] = new int[result.length + 1];
			System.arraycopy(result, 0, bigger, 1, result.length);
			bigger[0] = 0x01;
			return bigger;
		}
		return result;
	}

	/**
	 * Returns a BigInteger whose value is {@code (this - val)}.
	 *
	 * @param val
	 *            value to be subtracted from this BigInteger.
	 * @return {@code this - val}
	 */
	BigInteger subtract(BigInteger val) {
		if (val.signum == 0) {
			return this;
		}
		if (this.signum == 0) {
			return val.negate();
		}
		if (val.signum != this.signum) {
			return new BigInteger(add(this.mag, val.mag), this.signum);
		}

		int cmp = compareMagnitude(val);
		if (cmp == 0) {
			return ZERO;
		}
		int[] resultMag = (cmp > 0 ? subtract(this.mag, val.mag) : subtract(val.mag, this.mag));
		resultMag = trustedStripLeadingZeroInts(resultMag);
		return new BigInteger(resultMag, cmp == this.signum ? 1 : -1);
	}

	/**
	 * Subtracts the contents of the second int arrays (little) from the first (big). The first int array (big) must
	 * represent a larger number than the second. This method allocates the space necessary to hold the answer.
	 */
	private static int[] subtract(int[] big, int[] little) {
		int bigIndex = big.length;
		int result[] = new int[bigIndex];
		int littleIndex = little.length;
		long difference = 0;

		// Subtract common parts of both numbers
		while (littleIndex > 0) {
			difference = (big[--bigIndex] & LONG_MASK) - (little[--littleIndex] & LONG_MASK) + (difference >> 32);
			result[bigIndex] = (int) difference;
		}

		// Subtract remainder of longer number while borrow propagates
		boolean borrow = (difference >> 32 != 0);
		while (bigIndex > 0 && borrow) {
			borrow = ((result[--bigIndex] = big[bigIndex] - 1) == -1);
		}

		// Copy remainder of longer number
		while (bigIndex > 0) {
			result[--bigIndex] = big[bigIndex];
		}

		return result;
	}

	/**
	 * Returns a BigInteger whose value is {@code (this * val)}.
	 *
	 * implNote: An implementation may offer better algorithmic performance when {@code val == this}.
	 *
	 * @param val
	 *            value to be multiplied by this BigInteger.
	 * @return {@code this * val}
	 */
	BigInteger multiply(BigInteger val) {
		if (val.signum == 0 || this.signum == 0) {
			return ZERO;
		}

		int xlen = this.mag.length;

		if (val == this && xlen > MULTIPLY_SQUARE_THRESHOLD) {
			return square();
		}

		int ylen = val.mag.length;

		if ((xlen < KARATSUBA_THRESHOLD) || (ylen < KARATSUBA_THRESHOLD)) {
			int resultSign = this.signum == val.signum ? 1 : -1;
			if (val.mag.length == 1) {
				return multiplyByInt(this.mag, val.mag[0], resultSign);
			}
			if (this.mag.length == 1) {
				return multiplyByInt(val.mag, this.mag[0], resultSign);
			}
			int[] result = multiplyToLen(this.mag, xlen, val.mag, ylen, null);
			result = trustedStripLeadingZeroInts(result);
			return new BigInteger(result, resultSign);
		} else {
			if ((xlen < TOOM_COOK_THRESHOLD) && (ylen < TOOM_COOK_THRESHOLD)) {
				return multiplyKaratsuba(this, val);
			} else {
				return multiplyToomCook3(this, val);
			}
		}
	}

	private static BigInteger multiplyByInt(int[] x, int y, int sign) {
		if (IntegerHelper.bitCount(y) == 1) {
			return new BigInteger(shiftLeft(x, IntegerHelper.numberOfTrailingZeros(y)), sign);
		}
		int xlen = x.length;
		int[] rmag = new int[xlen + 1];
		long carry = 0;
		long yl = y & LONG_MASK;
		int rstart = rmag.length - 1;
		for (int i = xlen - 1; i >= 0; i--) {
			long product = (x[i] & LONG_MASK) * yl + carry;
			rmag[rstart--] = (int) product;
			carry = product >>> 32;
		}
		if (carry == 0L) {
			rmag = java.util.Arrays.copyOfRange(rmag, 1, rmag.length);
		} else {
			rmag[rstart] = (int) carry;
		}
		return new BigInteger(rmag, sign);
	}

	/**
	 * Package private methods used by BigDecimal code to multiply a BigInteger with a long. Assumes v is not equal to
	 * INFLATED.
	 */
	BigInteger multiply(long v) {
		if (v == 0 || this.signum == 0) {
			return ZERO;
		}
//		if (v == BigDecimal.INFLATED) {
//			return multiply(BigInteger.valueOf(v));
//		}
		int rsign = (v > 0 ? this.signum : -this.signum);
		if (v < 0) {
			v = -v;
		}
		long dh = v >>> 32; // higher order bits
		long dl = v & LONG_MASK; // lower order bits

		int xlen = this.mag.length;
		int[] value = this.mag;
		int[] rmag = (dh == 0L) ? (new int[xlen + 1]) : (new int[xlen + 2]);
		long carry = 0;
		int rstart = rmag.length - 1;
		for (int i = xlen - 1; i >= 0; i--) {
			long product = (value[i] & LONG_MASK) * dl + carry;
			rmag[rstart--] = (int) product;
			carry = product >>> 32;
		}
		rmag[rstart] = (int) carry;
		if (dh != 0L) {
			carry = 0;
			rstart = rmag.length - 2;
			for (int i = xlen - 1; i >= 0; i--) {
				long product = (value[i] & LONG_MASK) * dh + (rmag[rstart] & LONG_MASK) + carry;
				rmag[rstart--] = (int) product;
				carry = product >>> 32;
			}
			rmag[0] = (int) carry;
		}
		if (carry == 0L) {
			rmag = java.util.Arrays.copyOfRange(rmag, 1, rmag.length);
		}
		return new BigInteger(rmag, rsign);
	}

	/**
	 * Multiplies int arrays x and y to the specified lengths and places the result into z. There will be no leading
	 * zeros in the resultant array.
	 */
	private int[] multiplyToLen(int[] x, int xlen, int[] y, int ylen, @Nullable int[] z) {
		int xstart = xlen - 1;
		int ystart = ylen - 1;

		if (z == null || z.length < (xlen + ylen)) {
			z = new int[xlen + ylen];
		}

		long carry = 0;
		for (int j = ystart, k = ystart + 1 + xstart; j >= 0; j--, k--) {
			long product = (y[j] & LONG_MASK) * (x[xstart] & LONG_MASK) + carry;
			z[k] = (int) product;
			carry = product >>> 32;
		}
		z[xstart] = (int) carry;

		for (int i = xstart - 1; i >= 0; i--) {
			carry = 0;
			for (int j = ystart, k = ystart + 1 + i; j >= 0; j--, k--) {
				long product = (y[j] & LONG_MASK) * (x[i] & LONG_MASK) + (z[k] & LONG_MASK) + carry;
				z[k] = (int) product;
				carry = product >>> 32;
			}
			z[i] = (int) carry;
		}
		return z;
	}

	/**
	 * Multiplies two BigIntegers using the Karatsuba multiplication algorithm. This is a recursive divide-and-conquer
	 * algorithm which is more efficient for large numbers than what is commonly called the "grade-school" algorithm
	 * used in multiplyToLen. If the numbers to be multiplied have length n, the "grade-school" algorithm has an
	 * asymptotic complexity of O(n^2). In contrast, the Karatsuba algorithm has complexity of O(n^(log2(3))), or
	 * O(n^1.585). It achieves this increased performance by doing 3 multiplies instead of 4 when evaluating the
	 * product. As it has some overhead, should be used when both numbers are larger than a certain threshold (found
	 * experimentally).
	 *
	 * See: http://en.wikipedia.org/wiki/Karatsuba_algorithm
	 */
	private static BigInteger multiplyKaratsuba(BigInteger x, BigInteger y) {
		int xlen = x.mag.length;
		int ylen = y.mag.length;

		// The number of ints in each half of the number.
		int half = (Math.max(xlen, ylen) + 1) / 2;

		// xl and yl are the lower halves of x and y respectively,
		// xh and yh are the upper halves.
		BigInteger xl = x.getLower(half);
		BigInteger xh = x.getUpper(half);
		BigInteger yl = y.getLower(half);
		BigInteger yh = y.getUpper(half);

		BigInteger p1 = xh.multiply(yh); // p1 = xh*yh
		BigInteger p2 = xl.multiply(yl); // p2 = xl*yl

		// p3=(xh+xl)*(yh+yl)
		BigInteger p3 = xh.add(xl).multiply(yh.add(yl));

		// result = p1 * 2^(32*2*half) + (p3 - p1 - p2) * 2^(32*half) + p2
		BigInteger result = p1.shiftLeft(32 * half).add(p3.subtract(p1).subtract(p2)).shiftLeft(32 * half).add(p2);

		if (x.signum != y.signum) {
			return result.negate();
		} else {
			return result;
		}
	}

	/**
	 * Multiplies two BigIntegers using a 3-way Toom-Cook multiplication algorithm. This is a recursive
	 * divide-and-conquer algorithm which is more efficient for large numbers than what is commonly called the
	 * "grade-school" algorithm used in multiplyToLen. If the numbers to be multiplied have length n, the "grade-school"
	 * algorithm has an asymptotic complexity of O(n^2). In contrast, 3-way Toom-Cook has a complexity of about
	 * O(n^1.465). It achieves this increased asymptotic performance by breaking each number into three parts and by
	 * doing 5 multiplies instead of 9 when evaluating the product. Due to overhead (additions, shifts, and one
	 * division) in the Toom-Cook algorithm, it should only be used when both numbers are larger than a certain
	 * threshold (found experimentally). This threshold is generally larger than that for Karatsuba multiplication, so
	 * this algorithm is generally only used when numbers become significantly larger.
	 *
	 * The algorithm used is the "optimal" 3-way Toom-Cook algorithm outlined by Marco Bodrato.
	 *
	 * See: http://bodrato.it/toom-cook/ http://bodrato.it/papers/#WAIFI2007
	 *
	 * "Towards Optimal Toom-Cook Multiplication for Univariate and Multivariate Polynomials in Characteristic 2 and 0."
	 * by Marco BODRATO; In C.Carlet and B.Sunar, Eds., "WAIFI'07 proceedings", p. 116-133, LNCS #4547. Springer,
	 * Madrid, Spain, June 21-22, 2007.
	 *
	 */
	private static BigInteger multiplyToomCook3(BigInteger a, BigInteger b) {
		int alen = a.mag.length;
		int blen = b.mag.length;

		int largest = Math.max(alen, blen);

		// k is the size (in ints) of the lower-order slices.
		int k = (largest + 2) / 3; // Equal to ceil(largest/3)

		// r is the size (in ints) of the highest-order slice.
		int r = largest - 2 * k;

		// Obtain slices of the numbers. a2 and b2 are the most significant
		// bits of the numbers a and b, and a0 and b0 the least significant.
		BigInteger a0, a1, a2, b0, b1, b2;
		a2 = a.getToomSlice(k, r, 0, largest);
		a1 = a.getToomSlice(k, r, 1, largest);
		a0 = a.getToomSlice(k, r, 2, largest);
		b2 = b.getToomSlice(k, r, 0, largest);
		b1 = b.getToomSlice(k, r, 1, largest);
		b0 = b.getToomSlice(k, r, 2, largest);

		BigInteger v0, v1, v2, vm1, vinf, t1, t2, tm1, da1, db1;

		v0 = a0.multiply(b0);
		da1 = a2.add(a0);
		db1 = b2.add(b0);
		vm1 = da1.subtract(a1).multiply(db1.subtract(b1));
		da1 = da1.add(a1);
		db1 = db1.add(b1);
		v1 = da1.multiply(db1);
		v2 = da1.add(a2).shiftLeft(1).subtract(a0).multiply(db1.add(b2).shiftLeft(1).subtract(b0));
		vinf = a2.multiply(b2);

		// The algorithm requires two divisions by 2 and one by 3.
		// All divisions are known to be exact, that is, they do not produce
		// remainders, and all results are positive. The divisions by 2 are
		// implemented as right shifts which are relatively efficient, leaving
		// only an exact division by 3, which is done by a specialized
		// linear-time algorithm.
		t2 = v2.subtract(vm1).exactDivideBy3();
		tm1 = v1.subtract(vm1).shiftRight(1);
		t1 = v1.subtract(v0);
		t2 = t2.subtract(t1).shiftRight(1);
		t1 = t1.subtract(tm1).subtract(vinf);
		t2 = t2.subtract(vinf.shiftLeft(1));
		tm1 = tm1.subtract(t2);

		// Number of bits to shift left.
		int ss = k * 32;

		BigInteger result = vinf.shiftLeft(ss).add(t2).shiftLeft(ss).add(t1).shiftLeft(ss).add(tm1).shiftLeft(ss)
				.add(v0);

		if (a.signum != b.signum) {
			return result.negate();
		} else {
			return result;
		}
	}

	/**
	 * Returns a slice of a BigInteger for use in Toom-Cook multiplication.
	 *
	 * @param lowerSize
	 *            The size of the lower-order bit slices.
	 * @param upperSize
	 *            The size of the higher-order bit slices.
	 * @param slice
	 *            The index of which slice is requested, which must be a number from 0 to size-1. Slice 0 is the
	 *            highest-order bits, and slice size-1 are the lowest-order bits. Slice 0 may be of different size than
	 *            the other slices.
	 * @param fullsize
	 *            The size of the larger integer array, used to align slices to the appropriate position when
	 *            multiplying different-sized numbers.
	 */
	private BigInteger getToomSlice(int lowerSize, int upperSize, int slice, int fullsize) {
		int start, end, sliceSize, len, offset;

		len = this.mag.length;
		offset = fullsize - len;

		if (slice == 0) {
			start = 0 - offset;
			end = upperSize - 1 - offset;
		} else {
			start = upperSize + (slice - 1) * lowerSize - offset;
			end = start + lowerSize - 1;
		}

		if (start < 0) {
			start = 0;
		}
		if (end < 0) {
			return ZERO;
		}

		sliceSize = (end - start) + 1;

		if (sliceSize <= 0) {
			return ZERO;
		}

		// While performing Toom-Cook, all slices are positive and
		// the sign is adjusted when the final number is composed.
		if (start == 0 && sliceSize >= len) {
			return this.abs();
		}

		int intSlice[] = new int[sliceSize];
		System.arraycopy(this.mag, start, intSlice, 0, sliceSize);

		return new BigInteger(trustedStripLeadingZeroInts(intSlice), 1);
	}

	/**
	 * Does an exact division (that is, the remainder is known to be zero) of the specified number by 3. This is used in
	 * Toom-Cook multiplication. This is an efficient algorithm that runs in linear time. If the argument is not exactly
	 * divisible by 3, results are undefined. Note that this is expected to be called with positive arguments only.
	 */
	private BigInteger exactDivideBy3() {
		int len = this.mag.length;
		int[] result = new int[len];
		long x, w, q, borrow;
		borrow = 0L;
		for (int i = len - 1; i >= 0; i--) {
			x = (this.mag[i] & LONG_MASK);
			w = x - borrow;
			if (borrow > x) { // Did we make the number go negative?
				borrow = 1L;
			} else {
				borrow = 0L;
			}

			// 0xAAAAAAAB is the modular inverse of 3 (mod 2^32). Thus,
			// the effect of this is to divide by 3 (mod 2^32).
			// This is much faster than division on most architectures.
			q = (w * 0xAAAAAAABL) & LONG_MASK;
			result[i] = (int) q;

			// Now check the borrow. The second check can of course be
			// eliminated if the first fails.
			if (q >= 0x55555556L) {
				borrow++;
				if (q >= 0xAAAAAAABL) {
					borrow++;
				}
			}
		}
		result = trustedStripLeadingZeroInts(result);
		return new BigInteger(result, this.signum);
	}

	/**
	 * Returns a new BigInteger representing n lower ints of the number. This is used by Karatsuba multiplication and
	 * Karatsuba squaring.
	 */
	private BigInteger getLower(int n) {
		int len = this.mag.length;

		if (len <= n) {
			return abs();
		}

		int lowerInts[] = new int[n];
		System.arraycopy(this.mag, len - n, lowerInts, 0, n);

		return new BigInteger(trustedStripLeadingZeroInts(lowerInts), 1);
	}

	/**
	 * Returns a new BigInteger representing mag.length-n upper ints of the number. This is used by Karatsuba
	 * multiplication and Karatsuba squaring.
	 */
	private BigInteger getUpper(int n) {
		int len = this.mag.length;

		if (len <= n) {
			return ZERO;
		}

		int upperLen = len - n;
		int upperInts[] = new int[upperLen];
		System.arraycopy(this.mag, 0, upperInts, 0, upperLen);

		return new BigInteger(trustedStripLeadingZeroInts(upperInts), 1);
	}

	// Squaring

	/**
	 * Returns a BigInteger whose value is {@code (this<sup>2</sup>)}.
	 *
	 * @return {@code this<sup>2</sup>}
	 */
	private BigInteger square() {
		if (this.signum == 0) {
			return ZERO;
		}
		int len = this.mag.length;

		if (len < KARATSUBA_SQUARE_THRESHOLD) {
			int[] z = squareToLen(this.mag, len, null);
			return new BigInteger(trustedStripLeadingZeroInts(z), 1);
		} else {
			if (len < TOOM_COOK_SQUARE_THRESHOLD) {
				return squareKaratsuba();
			} else {
				return squareToomCook3();
			}
		}
	}

	/**
	 * Squares the contents of the int array x. The result is placed into the int array z. The contents of x are not
	 * changed.
	 */
	private static final int[] squareToLen(int[] x, int len, @Nullable int[] z) {
		/*
		 * The algorithm used here is adapted from Colin Plumb's C library. Technique: Consider the partial products in
		 * the multiplication of "abcde" by itself:
		 *
		 * a b c d e * a b c d e ================== ae be ce de ee ad bd cd dd de ac bc cc cd ce ab bb bc bd be aa ab ac
		 * ad ae
		 *
		 * Note that everything above the main diagonal: ae be ce de = (abcd) * e ad bd cd = (abc) * d ac bc = (ab) * c
		 * ab = (a) * b
		 *
		 * is a copy of everything below the main diagonal: de cd ce bc bd be ab ac ad ae
		 *
		 * Thus, the sum is 2 * (off the diagonal) + diagonal.
		 *
		 * This is accumulated beginning with the diagonal (which consist of the squares of the digits of the input),
		 * which is then divided by two, the off-diagonal added, and multiplied by two again. The low bit is simply a
		 * copy of the low bit of the input, so it doesn't need special care.
		 */
		int zlen = len << 1;
		if (z == null || z.length < zlen) {
			z = new int[zlen];
		}

		// Store the squares, right shifted one bit (i.e., divided by 2)
		int lastProductLowWord = 0;
		for (int j = 0, i = 0; j < len; j++) {
			long piece = (x[j] & LONG_MASK);
			long product = piece * piece;
			z[i++] = (lastProductLowWord << 31) | (int) (product >>> 33);
			z[i++] = (int) (product >>> 1);
			lastProductLowWord = (int) product;
		}

		// Add in off-diagonal sums
		for (int i = len, offset = 1; i > 0; i--, offset += 2) {
			int t = x[i - 1];
			t = mulAdd(z, x, offset, i - 1, t);
			addOne(z, offset - 1, i, t);
		}

		// Shift back up and set low bit
		primitiveLeftShift(z, zlen, 1);
		z[zlen - 1] |= x[len - 1] & 1;

		return z;
	}

	/**
	 * Squares a BigInteger using the Karatsuba squaring algorithm. It should be used when both numbers are larger than
	 * a certain threshold (found experimentally). It is a recursive divide-and-conquer algorithm that has better
	 * asymptotic performance than the algorithm used in squareToLen.
	 */
	private BigInteger squareKaratsuba() {
		int half = (this.mag.length + 1) / 2;

		BigInteger xl = getLower(half);
		BigInteger xh = getUpper(half);

		BigInteger xhs = xh.square(); // xhs = xh^2
		BigInteger xls = xl.square(); // xls = xl^2

		// xh^2 << 64 + (((xl+xh)^2 - (xh^2 + xl^2)) << 32) + xl^2
		return xhs.shiftLeft(half * 32).add(xl.add(xh).square().subtract(xhs.add(xls))).shiftLeft(half * 32).add(xls);
	}

	/**
	 * Squares a BigInteger using the 3-way Toom-Cook squaring algorithm. It should be used when both numbers are larger
	 * than a certain threshold (found experimentally). It is a recursive divide-and-conquer algorithm that has better
	 * asymptotic performance than the algorithm used in squareToLen or squareKaratsuba.
	 */
	private BigInteger squareToomCook3() {
		int len = this.mag.length;

		// k is the size (in ints) of the lower-order slices.
		int k = (len + 2) / 3; // Equal to ceil(largest/3)

		// r is the size (in ints) of the highest-order slice.
		int r = len - 2 * k;

		// Obtain slices of the numbers. a2 is the most significant
		// bits of the number, and a0 the least significant.
		BigInteger a0, a1, a2;
		a2 = getToomSlice(k, r, 0, len);
		a1 = getToomSlice(k, r, 1, len);
		a0 = getToomSlice(k, r, 2, len);
		BigInteger v0, v1, v2, vm1, vinf, t1, t2, tm1, da1;

		v0 = a0.square();
		da1 = a2.add(a0);
		vm1 = da1.subtract(a1).square();
		da1 = da1.add(a1);
		v1 = da1.square();
		vinf = a2.square();
		v2 = da1.add(a2).shiftLeft(1).subtract(a0).square();

		// The algorithm requires two divisions by 2 and one by 3.
		// All divisions are known to be exact, that is, they do not produce
		// remainders, and all results are positive. The divisions by 2 are
		// implemented as right shifts which are relatively efficient, leaving
		// only a division by 3.
		// The division by 3 is done by an optimized algorithm for this case.
		t2 = v2.subtract(vm1).exactDivideBy3();
		tm1 = v1.subtract(vm1).shiftRight(1);
		t1 = v1.subtract(v0);
		t2 = t2.subtract(t1).shiftRight(1);
		t1 = t1.subtract(tm1).subtract(vinf);
		t2 = t2.subtract(vinf.shiftLeft(1));
		tm1 = tm1.subtract(t2);

		// Number of bits to shift left.
		int ss = k * 32;

		return vinf.shiftLeft(ss).add(t2).shiftLeft(ss).add(t1).shiftLeft(ss).add(tm1).shiftLeft(ss).add(v0);
	}

	// Division

	/**
	 * Returns a BigInteger whose value is {@code (this / val)}.
	 *
	 * @param val
	 *            value by which this BigInteger is to be divided.
	 * @return {@code this / val}
	 * @throws ArithmeticException
	 *             if {@code val} is zero.
	 */
	BigInteger divide(BigInteger val) {
		return divideKnuth(val);
	}

	/**
	 * Returns a BigInteger whose value is {@code (this / val)} using an O(n^2) algorithm from Knuth.
	 *
	 * @param val
	 *            value by which this BigInteger is to be divided.
	 * @return {@code this / val}
	 * @throws ArithmeticException
	 *             if {@code val} is zero.
	 * @see MutableBigInteger#divideKnuth(MutableBigInteger, MutableBigInteger, boolean)
	 */
	private BigInteger divideKnuth(BigInteger val) {
		MutableBigInteger q = new MutableBigInteger(), a = new MutableBigInteger(this.mag),
				b = new MutableBigInteger(val.mag);

		a.divideKnuth(b, q, false);
		return q.toBigInteger(this.signum * val.signum);
	}

	/**
	 * Returns an array of two BigIntegers containing {@code (this / val)} followed by {@code (this % val)}.
	 *
	 * @param val
	 *            value by which this BigInteger is to be divided, and the remainder computed.
	 * @return an array of two BigIntegers: the quotient {@code (this / val)} is the initial element, and the remainder
	 *         {@code (this % val)} is the final element.
	 * @throws ArithmeticException
	 *             if {@code val} is zero.
	 */
	BigInteger[] divideAndRemainder(BigInteger val) {
		return divideAndRemainderKnuth(val);
	}

	/** Long division */
	private BigInteger[] divideAndRemainderKnuth(BigInteger val) {
		BigInteger[] result = new BigInteger[2];
		MutableBigInteger q = new MutableBigInteger(), a = new MutableBigInteger(this.mag),
				b = new MutableBigInteger(val.mag);
		MutableBigInteger r = a.divideKnuth(b, q);
		result[0] = q.toBigInteger(this.signum == val.signum ? 1 : -1);
		result[1] = r.toBigInteger(this.signum);
		return result;
	}


	/**
	 * Package private method to return bit length for an integer.
	 */
	static int bitLengthForInt(int n) {
		return 32 - IntegerHelper.numberOfLeadingZeros(n);
	}


	// shifts a up to len left n bits assumes no leading zeros, 0<=n<32
	static void primitiveLeftShift(int[] a, int len, int n) {
		if (len == 0 || n == 0) {
			return;
		}

		int n2 = 32 - n;
		for (int i = 0, c = a[i], m = i + len - 1; i < m; i++) {
			int b = c;
			c = a[i + 1];
			a[i] = (b << n) | (c >>> n2);
		}
		a[len - 1] <<= n;
	}

	/**
	 * Returns a BigInteger whose value is the absolute value of this BigInteger.
	 *
	 * @return {@code abs(this)}
	 */
	BigInteger abs() {
		return (this.signum >= 0 ? this : this.negate());
	}

	/**
	 * Returns a BigInteger whose value is {@code (-this)}.
	 *
	 * @return {@code -this}
	 */
	BigInteger negate() {
		return new BigInteger(this.mag, -this.signum);
	}


	/**
	 * Multiply an array by one word k and add to result, return the carry
	 */
	static int mulAdd(int[] out, int[] in, int offset, int len, int k) {
		long kLong = k & LONG_MASK;
		long carry = 0;

		offset = out.length - offset - 1;
		for (int j = len - 1; j >= 0; j--) {
			long product = (in[j] & LONG_MASK) * kLong + (out[offset] & LONG_MASK) + carry;
			out[offset--] = (int) product;
			carry = product >>> 32;
		}
		return (int) carry;
	}

	/**
	 * Add one word to the number a mlen words into a. Return the resulting carry.
	 */
	static int addOne(int[] a, int offset, int mlen, int carry) {
		offset = a.length - 1 - mlen - offset;
		long t = (a[offset] & LONG_MASK) + (carry & LONG_MASK);

		a[offset] = (int) t;
		if ((t >>> 32) == 0) {
			return 0;
		}
		while (--mlen >= 0) {
			if (--offset < 0) { // Carry out of number
				return 1;
			} else {
				a[offset]++;
				if (a[offset] != 0) {
					return 0;
				}
			}
		}
		return 1;
	}


	// Shift Operations

	/**
	 * Returns a BigInteger whose value is {@code (this << n)}. The shift distance, {@code n}, may be negative, in which
	 * case this method performs a right shift. (Computes <tt>floor(this * 2<sup>n</sup>)</tt>.)
	 *
	 * @param n
	 *            shift distance, in bits.
	 * @return {@code this << n}
	 * @see #shiftRight
	 */
	BigInteger shiftLeft(int n) {
		if (this.signum == 0) {
			return ZERO;
		}
		if (n > 0) {
			return new BigInteger(shiftLeft(this.mag, n), this.signum);
		} else if (n == 0) {
			return this;
		} else {
			// Possible int overflow in (-n) is not a trouble,
			// because shiftRightImpl considers its argument unsigned
			return shiftRightImpl(-n);
		}
	}

	/**
	 * Returns a magnitude array whose value is {@code (mag << n)}. The shift distance, {@code n}, is considered
	 * unnsigned. (Computes <tt>this * 2<sup>n</sup></tt>.)
	 *
	 * @param mag
	 *            magnitude, the most-significant int ({@code mag[0]}) must be non-zero.
	 * @param n
	 *            unsigned shift distance, in bits.
	 * @return {@code mag << n}
	 */
	private static int[] shiftLeft(int[] mag, int n) {
		int nInts = n >>> 5;
		int nBits = n & 0x1f;
		int magLen = mag.length;
		int newMag[] = null;

		if (nBits == 0) {
			newMag = new int[magLen + nInts];
			System.arraycopy(mag, 0, newMag, 0, magLen);
		} else {
			int i = 0;
			int nBits2 = 32 - nBits;
			int highBits = mag[0] >>> nBits2;
			if (highBits != 0) {
				newMag = new int[magLen + nInts + 1];
				newMag[i++] = highBits;
			} else {
				newMag = new int[magLen + nInts];
			}
			int j = 0;
			while (j < magLen - 1) {
				newMag[i++] = mag[j++] << nBits | mag[j] >>> nBits2;
			}
			newMag[i] = mag[j] << nBits;
		}
		return newMag;
	}

	/**
	 * Returns a BigInteger whose value is {@code (this >> n)}. Sign extension is performed. The shift distance,
	 * {@code n}, may be negative, in which case this method performs a left shift. (Computes
	 * <tt>floor(this / 2<sup>n</sup>)</tt>.)
	 *
	 * @param n
	 *            shift distance, in bits.
	 * @return {@code this >> n}
	 * @see #shiftLeft
	 */
	BigInteger shiftRight(int n) {
		if (this.signum == 0) {
			return ZERO;
		}
		if (n > 0) {
			return shiftRightImpl(n);
		} else if (n == 0) {
			return this;
		} else {
			// Possible int overflow in {@code -n} is not a trouble,
			// because shiftLeft considers its argument unsigned
			return new BigInteger(shiftLeft(this.mag, -n), this.signum);
		}
	}

	/**
	 * Returns a BigInteger whose value is {@code (this >> n)}. The shift distance, {@code n}, is considered unsigned.
	 * (Computes <tt>floor(this * 2<sup>-n</sup>)</tt>.)
	 *
	 * @param n
	 *            unsigned shift distance, in bits.
	 * @return {@code this >> n}
	 */
	private BigInteger shiftRightImpl(int n) {
		int nInts = n >>> 5;
		int nBits = n & 0x1f;
		int magLen = this.mag.length;
		int newMag[] = null;

		// Special case: entire contents shifted off the end
		if (nInts >= magLen) {
			return (this.signum >= 0 ? ZERO : BigInteger.valueOf(-1L));
		}

		if (nBits == 0) {
			int newMagLen = magLen - nInts;
			newMag = Arrays.copyOf(this.mag, newMagLen);
		} else {
			int i = 0;
			int highBits = this.mag[0] >>> nBits;
			if (highBits != 0) {
				newMag = new int[magLen - nInts];
				newMag[i++] = highBits;
			} else {
				newMag = new int[magLen - nInts - 1];
			}

			int nBits2 = 32 - nBits;
			int j = 0;
			while (j < magLen - nInts - 1) {
				newMag[i++] = (this.mag[j++] << nBits2) | (this.mag[j] >>> nBits);
			}
		}

		if (this.signum < 0) {
			// Find out whether any one-bits were shifted off the end.
			boolean onesLost = false;
			for (int i = magLen - 1, j = magLen - nInts; i >= j && !onesLost; i--) {
				onesLost = (this.mag[i] != 0);
			}
			if (!onesLost && nBits != 0) {
				onesLost = (this.mag[magLen - nInts - 1] << (32 - nBits) != 0);
			}

			if (onesLost) {
				newMag = javaIncrement(newMag);
			}
		}

		return new BigInteger(newMag, this.signum);
	}

	int[] javaIncrement(int[] val) {
		int lastSum = 0;
		for (int i = val.length - 1; i >= 0 && lastSum == 0; i--) {
			lastSum = (val[i] += 1);
		}
		if (lastSum == 0) {
			val = new int[val.length + 1];
			val[0] = 1;
		}
		return val;
	}



	// Comparison Operations

	@Override
	public int compareTo(BigInteger val) {
		throw new UnsupportedOperationException();
	}

	/**
	 * Compares the magnitude array of this BigInteger with the specified BigInteger's. This is the version of compareTo
	 * ignoring sign.
	 *
	 * @param val
	 *            BigInteger whose magnitude array to be compared.
	 * @return -1, 0 or 1 as this magnitude array is less than, equal to or greater than the magnitude aray for the
	 *         specified BigInteger's.
	 */
	final int compareMagnitude(BigInteger val) {
		int[] m1 = this.mag;
		int len1 = m1.length;
		int[] m2 = val.mag;
		int len2 = m2.length;
		if (len1 < len2) {
			return -1;
		}
		if (len1 > len2) {
			return 1;
		}
		for (int i = 0; i < len1; i++) {
			int a = m1[i];
			int b = m2[i];
			if (a != b) {
				return ((a & LONG_MASK) < (b & LONG_MASK)) ? -1 : 1;
			}
		}
		return 0;
	}

	/**
	 * Version of compareMagnitude that compares magnitude with long value. val can't be Long.MIN_VALUE.
	 */
	final int compareMagnitude(long val) {
		assert val != Long.MIN_VALUE;
		int[] m1 = this.mag;
		int len = m1.length;
		if (len > 2) {
			return 1;
		}
		if (val < 0) {
			val = -val;
		}
		int highWord = (int) (val >>> 32);
		if (highWord == 0) {
			if (len < 1) {
				return -1;
			}
			if (len > 1) {
				return 1;
			}
			int a = m1[0];
			int b = (int) val;
			if (a != b) {
				return ((a & LONG_MASK) < (b & LONG_MASK)) ? -1 : 1;
			}
			return 0;
		} else {
			if (len < 2) {
				return -1;
			}
			int a = m1[0];
			int b = highWord;
			if (a != b) {
				return ((a & LONG_MASK) < (b & LONG_MASK)) ? -1 : 1;
			}
			a = m1[1];
			b = (int) val;
			if (a != b) {
				return ((a & LONG_MASK) < (b & LONG_MASK)) ? -1 : 1;
			}
			return 0;
		}
	}

	/**
	 * Compares this BigInteger with the specified Object for equality.
	 *
	 * @param x
	 *            Object to which this BigInteger is to be compared.
	 * @return {@code true} if and only if the specified Object is a BigInteger whose value is numerically equal to this
	 *         BigInteger.
	 */
	@Override
	public boolean equals(@Nullable Object x) {
		// This test is just an optimization, which may or may not help
		if (x == this) {
			return true;
		}

		if (!(x instanceof BigInteger)) {
			return false;
		}

		BigInteger xInt = (BigInteger) x;
		if (xInt.signum != this.signum) {
			return false;
		}

		int[] m = this.mag;
		int len = m.length;
		int[] xm = xInt.mag;
		if (len != xm.length) {
			return false;
		}

		for (int i = 0; i < len; i++) {
			if (xm[i] != m[i]) {
				return false;
			}
		}

		return true;
	}


	// Hash Function

	/**
	 * Returns the hash code for this BigInteger.
	 *
	 * @return hash code for this BigInteger.
	 */
	@Override
	public int hashCode() {
		int hashCode = 0;

		for (int i = 0; i < this.mag.length; i++) {
			hashCode = (int) (31 * hashCode + (this.mag[i] & LONG_MASK));
		}

		return hashCode * this.signum;
	}


	/**
	 * Converts this BigInteger to an {@code int}. This conversion is analogous to a <i>narrowing primitive
	 * conversion</i> from {@code long} to {@code int} as defined in section 5.1.3 of <cite>The Java&trade; Language
	 * Specification</cite>: if this BigInteger is too big to fit in an {@code int}, only the low-order 32 bits are
	 * returned. Note that this conversion can lose information about the overall magnitude of the BigInteger value as
	 * well as return a result with the opposite sign.
	 *
	 * @return this BigInteger converted to an {@code int}.
	 */
	@Override
	public int intValue() {
		int result = 0;
		result = getInt(0);
		return result;
	}

	/**
	 * Converts this BigInteger to a {@code long}. This conversion is analogous to a <i>narrowing primitive
	 * conversion</i> from {@code long} to {@code int} as defined in section 5.1.3 of <cite>The Java&trade; Language
	 * Specification</cite>: if this BigInteger is too big to fit in a {@code long}, only the low-order 64 bits are
	 * returned. Note that this conversion can lose information about the overall magnitude of the BigInteger value as
	 * well as return a result with the opposite sign.
	 *
	 * @return this BigInteger converted to a {@code long}.
	 */
	@Override
	public long longValue() {
		long result = 0;

		for (int i = 1; i >= 0; i--) {
			result = (result << 32) + (getInt(i) & LONG_MASK);
		}
		return result;
	}
	
	/**
	 * Returns the specified int of the little-endian two's complement representation (int 0 is the least significant).
	 * The int number can be arbitrarily high (values are logically preceded by infinitely many sign ints).
	 */
	private int getInt(int n) {
		if (n < 0) {
			return 0;
		}
		if (n >= this.mag.length) {
			return this.signum < 0 ? -1 : 0;
		}

		int magInt = this.mag[this.mag.length - n - 1];

		return (this.signum >= 0 ? magInt : (n <= firstNonzeroIntNum() ? -magInt : ~magInt));
	}

	/**
	 * Returns the index of the int that contains the first nonzero int in the little-endian binary representation of
	 * the magnitude (int 0 is the least significant). If the magnitude is zero, return value is undefined.
	 */
	private int firstNonzeroIntNum() {
		// Search for the first nonzero int
		int i;
		int mlen = this.mag.length;
		for (i = mlen - 1; i >= 0 && this.mag[i] == 0; i--) {
			;
		}
		return mlen - i - 1;
	}


	/**
	 * Returns the input array stripped of any leading zero bytes. Since the source is trusted the copying may be
	 * skipped.
	 */
	private static int[] trustedStripLeadingZeroInts(int val[]) {
		int vlen = val.length;
		int keep;

		// Find first nonzero byte
		for (keep = 0; keep < vlen && val[keep] == 0; keep++) {
			;
		}
		return keep == 0 ? val : java.util.Arrays.copyOfRange(val, keep, vlen);
	}


    /**
     * Returns the number of bits in the minimal two's-complement
     * representation of this BigInteger, <i>excluding</i> a sign bit.
     * For positive BigIntegers, this is equivalent to the number of bits in
     * the ordinary binary representation.  (Computes
     * {@code (ceil(log2(this < 0 ? -this : this+1)))}.)
     *
     * @return number of bits in the minimal two's-complement
     *         representation of this BigInteger, <i>excluding</i> a sign bit.
     */
    int bitLength() {
    	int n;
    	int[] m = mag;
    	int len = m.length;
    	if (len == 0) {
    		n = 0; // offset by one to initialize
    	}  else {
    		// Calculate the bit length of the magnitude
    		int magBitLength = ((len - 1) << 5) + bitLengthForInt(mag[0]);
    		if (signum < 0) {
    			// Check if magnitude is a power of two
    			boolean pow2 = (IntegerHelper.bitCount(mag[0]) == 1);
    			for (int i=1; i< len && pow2; i++)
    				pow2 = (mag[i] == 0);

    			n = (pow2 ? magBitLength - 1 : magBitLength);
    		} else {
    			n = magBitLength;
    		}
    	}
    	return n;
    }
	


	@Override
	public double doubleValue() {
		throw new UnsupportedOperationException();
	}

	@Override
	public float floatValue() {
		throw new UnsupportedOperationException();
	}
}