Software Público Brasileiro

/***************************************************************************
 *   Copyright (C) 2005 by Jeff Ferr                                       *
 *   root@sat                                                              *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program 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 for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 a***************************************************************************/
#ifndef J_BIGINTEGER_H
#define J_BIGINTEGER_H

#include "jobject.h"

#include <string>

#include <stdint.h>

namespace jmath {

/**
 * \brief Immutable arbitrary-precision integers.
 * Additionally, BigInteger provides operations for modular arithmetic, GCD
 * calculation, primality testing, prime generation, bit manipulation,
 * and a few other miscellaneous operations.
 * Semantics of shift operations extend those of 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 (&gt;&gt;&gt;) is omitted, as this operation makes
 * little sense in combination with the "infinite word size" abstraction
 * provided by this class.
 * 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.
 *
 * \author Jeff Ferr
 */
class BigInteger : public virtual jcommon::Object{
	
	private:
		/**
		 * \brief 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.
		 */
		int signum;
		
	 	/**
		 * \brief 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 (<tt>mag[0]</tt>) 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.
		 */
		int *mag;
		
		/**
		 * \brief The bitCount of this BigInteger, as returned by bitCount(), or -1
		 * (either value is acceptable).
		 */
		int bitCount =  -1;
		
		/**
		 * \brief The bitLength of this BigInteger, as returned by bitLength(), or -1
		 * (either value is acceptable).
		 */
		int bitLength = -1;
		
		/**
		 * \brief The lowest set bit of this BigInteger, as returned by getLowestSetBit(),
		 * or -2 (either value is acceptable).
		 */
		int lowestSetBit = -2;
		
		/**
		 * \brief The index of the lowest-order byte in the magnitude of this BigInteger
		 * that contains a nonzero byte, or -2 (either value is acceptable).  The
		 * least significant byte has int-number 0, the next byte in order of
		 * increasing significance has byte-number 1, and so forth.
		 */
		int firstNonzeroByteNum = -2;
		
		/**
		 * \brief The index of the lowest-order int in the magnitude of this BigInteger
		 * that contains a nonzero int, or -2 (either value is acceptable).  The
		 * least significant int has int-number 0, the next int in order of
		 * increasing significance has int-number 1, and so forth.
		 */
		int firstNonzeroIntNum = -2;
		
		/** \brief This mask is used to obtain the value of an int as if it were unsigned. */
		const static long LONG_MASK = 0xffffffffL;
		
		// Minimum size in bits that the requested prime number has
		// before we use the large prime number generating algorithms
		static final int SMALL_PRIME_THRESHOLD = 95;
		
		// Certainty required to meet the spec of probablePrime
		static final int DEFAULT_PRIME_CERTAINTY = 100;
		
		static byte * randomBits(int numBits, Random rnd);
		
		/**
		 * Find a random number of the specified bitLength that is probably prime.
		 * This method is used for smaller primes, its performance degrades on
		 * larger bitlengths.
		 *
		 * This method assumes bitLength > 1.
		 */
		static BigInteger smallPrime(int bitLength, int certainty, Random rnd);
		
		static final BigInteger SMALL_PRIME_PRODUCT = valueOf(3L*5*7*11*13*17*19*23*29*31*37*41);
		
		/**
		 * Find a random number of the specified bitLength that is probably prime.
		 * This method is more appropriate for larger bitlengths since it uses
		 * a sieve to eliminate most composites before using a more expensive
		 * test.
		 */
		static BigInteger largePrime(int bitLength, int certainty, Random rnd);
		
		/**
		 * \brief This private constructor translates an int array containing the
		 * two's-complement binary representation of a BigInteger into a
		 * BigInteger. The input array is assumed to be in <i>big-endian</i>
		 * int-order: the most significant int is in the zeroth element.
		 */
		BigInteger(int *val);

		/**
		 * Returns true iff this BigInteger is a Lucas-Lehmer probable prime.
		 *
		 * The following assumptions are made:
		 * This BigInteger is a positive, odd number.
		 */
		boolean passesLucasLehmer();
		
		/**
		 * Computes Jacobi(p,n).
		 * Assumes n positive, odd, n>=3.
		 */
		static int jacobiSymbol(int p, BigInteger n);
		
		static BigInteger lucasLehmerSequence(int z, BigInteger k, BigInteger n);
		
		/**
		 * Returns true iff this BigInteger passes the specified number of
		 * Miller-Rabin tests. This test is taken from the DSA spec (NIST FIPS
		 * 186-2).
		 *
		 * The following assumptions are made:
		 * This BigInteger is a positive, odd number greater than 2.
		 * iterations<=50.
		 */
		boolean passesMillerRabin(int iterations);
		
		/**
		 * This private 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 private constructor is for internal use and assumes that its
		 * arguments are correct.
		 */
		BigInteger(byte[] magnitude, int signum);
		
		/**
		 * This private constructor is for internal use in converting
		 * from a MutableBigInteger object into a BigInteger.
		 */
		BigInteger(MutableBigInteger val, int sign);
		
		/**
		 * Constructs a BigInteger with the specified value, which may not be zero.
		 */
		BigInteger(long val);
		
		/**
		 * Returns a BigInteger with the given two's complement representation.
		 * Assumes that the input array will not be modified (the returned
		 * BigInteger will reference the input array if feasible).
		 */
		static BigInteger valueOf(int val[]);
		
		// Constants
		
		/**
		 * Initialize static constant array when class is loaded.
		 */
		final static int MAX_CONSTANT = 16;
		static BigInteger posConst[] = new BigInteger[MAX_CONSTANT+1];
		static BigInteger negConst[] = new BigInteger[MAX_CONSTANT+1];
		static {
			for (int i = 1; i <= MAX_CONSTANT; i++) {
				int[] magnitude = new int[1];
				magnitude[0] = (int) i;
				posConst[i] = new BigInteger(magnitude,  1);
				negConst[i] = new BigInteger(magnitude, -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.
		 */
		static int[] add(int[] x, int[] y);
		
		/**
		 * 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);
		
		/**
		 * Returns a BigInteger whose value is <tt>(this * val)</tt>.
		 *
		 * @param  val value to be multiplied by this BigInteger.
		 * @return <tt>this * val</tt>
		 */
		public BigInteger multiply(BigInteger val);
		
		/**
		 * Multiplies int arrays x and y to the specified lengths and places
		 * the result into z.
		 */
		private int[] multiplyToLen(int[] x, int xlen, int[] y, int ylen, int[] z);
		
		/**
		 * Returns a BigInteger whose value is <tt>(this<sup>2</sup>)</tt>.
		 *
		 * @return <tt>this<sup>2</sup></tt>
		 */
		private BigInteger square();
		
		/**
		 * Squares the contents of the int array x. The result is placed into the
		 * int array z.  The contents of x are not changed.
		 * 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.
         */
		private static final int[] squareToLen(int[] x, int len, int[] z);
		
		/**
		 * Left shift int array a up to len by n bits. Returns the array that
		 * results from the shift since space may have to be reallocated.
		 */
		static int[] leftShift(int[] a, int len, int n);
		
		// shifts a up to len right n bits assumes no leading zeros, 0<n<32
		static void primitiveRightShift(int[] a, int len, int 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);
		
		/**
		 * Calculate bitlength of contents of the first len elements an int array,
		 * assuming there are no leading zero ints.
		 */
		static int bitLength(int[] val, int len);
		
		/**
		 * Montgomery reduce n, modulo mod.  This reduces modulo mod and divides
		 * by 2^(32*mlen). Adapted from Colin Plumb's C library.
		 */
		static int[] montReduce(int[] n, int[] mod, int mlen, int inv);
		
		/*
		 * Returns -1, 0 or +1 as big-endian unsigned int array arg1 is less than,
		 * equal to, or greater than arg2 up to length len.
		 */
		static int intArrayCmpToLen(int[] arg1, int[] arg2, int len);
		
		/**
		 * Subtracts two numbers of same length, returning borrow.
		 */
		static int subN(int[] a, int[] b, int len);
		
		/**
		 * Multiply an array by one word k and add to result, return the carry
		 */
		int mulAdd(int[] out, int[] in, int offset, int len, int k);
		
		/**
		 * 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);
		
		/**
		 * Returns a BigInteger whose value is (this ** exponent) mod (2**p)
		 * Perform exponentiation using repeated squaring trick, chopping off
		 * high order bits as indicated by modulus.
		 */
		BigInteger modPow2(BigInteger exponent, int p);
		
		/**
		 * Returns a BigInteger whose value is this mod(2**p).
		 * Assumes that this BigInteger &gt;= 0 and p &gt; 0.
		 */
		BigInteger mod2(int p);
		
		/**
		 * Returns a BigInteger whose value is x to the power of y mod z.
		 * Assumes: z is odd && x < z.
		 * The algorithm is adapted from Colin Plumb's C library.
		 *
		 * The window algorithm:
		 * The idea is to keep a running product of b1 = n^(high-order bits of exp)
		 * and then keep appending exponent bits to it.  The following patterns
		 * apply to a 3-bit window (k = 3):
		 * To append   0: square
		 * To append   1: square, multiply by n^1
		 * To append  10: square, multiply by n^1, square
		 * To append  11: square, square, multiply by n^3
		 * To append 100: square, multiply by n^1, square, square
		 * To append 101: square, square, square, multiply by n^5
		 * To append 110: square, square, multiply by n^3, square
		 * To append 111: square, square, square, multiply by n^7
		 *
		 * Since each pattern involves only one multiply, the longer the pattern
		 * the better, except that a 0 (no multiplies) can be appended directly.
		 * We precompute a table of odd powers of n, up to 2^k, and can then
		 * multiply k bits of exponent at a time.  Actually, assuming random
		 * exponents, there is on average one zero bit between needs to
		 * multiply (1/2 of the time there's none, 1/4 of the time there's 1,
		 * 1/8 of the time, there's 2, 1/32 of the time, there's 3, etc.), so
		 * you have to do one multiply per k+1 bits of exponent.
		 *
		 * The loop walks down the exponent, squaring the result buffer as
		 * it goes.  There is a wbits+1 bit lookahead buffer, buf, that is
		 * filled with the upcoming exponent bits.  (What is read after the
		 * end of the exponent is unimportant, but it is filled with zero here.)
		 * When the most-significant bit of this buffer becomes set, i.e.
		 * (buf & tblmask) != 0, we have to decide what pattern to multiply
		 * by, and when to do it.  We decide, remember to do it in future
		 * after a suitable number of squarings have passed (e.g. a pattern
		 * of "100" in the buffer requires that we multiply by n^1 immediately;
		 * a pattern of "110" calls for multiplying by n^3 after one more
		 * squaring), clear the buffer, and continue.
		 *
		 * When we start, there is one more optimization: the result buffer
		 * is implcitly one, so squaring it or multiplying by it can be
		 * optimized away.  Further, if we start with a pattern like "100"
		 * in the lookahead window, rather than placing n into the buffer
		 * and then starting to square it, we have already computed n^2
		 * to compute the odd-powers table, so we can place that into
		 * the buffer and save a squaring.
		 *
		 * This means that if you have a k-bit window, to compute n^z,
		 * where z is the high k bits of the exponent, 1/2 of the time
		 * it requires no squarings.  1/4 of the time, it requires 1
		 * squaring, ... 1/2^(k-1) of the time, it reqires k-2 squarings.
		 * And the remaining 1/2^(k-1) of the time, the top k bits are a
		 * 1 followed by k-1 0 bits, so it again only requires k-2
		 * squarings, not k-1.  The average of these is 1.  Add that
		 * to the one squaring we have to do to compute the table,
		 * and you'll see that a k-bit window saves k-2 squarings
		 * as well as reducing the multiplies.  (It actually doesn't
		 * hurt in the case k = 1, either.)
		 */
		BigInteger oddModPow(BigInteger y, BigInteger z);
		
		/**
		 * bitLen(val) is the number of bits in val.
		 */
		static int bitLen(int w);
		
		/*
		 * trailingZeroTable[i] is the number of trailing zero bits in the binary
		 * representation of i.
		 */
		final static byte trailingZeroTable[] = {
			-25, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
			4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
			5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
			4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
			6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
			4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
			5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
			4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
			7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
			4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
			5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
			4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
			6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
			4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
			5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
			4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0};
		
		/* zero[i] is a string of i consecutive zeros. */
		private static std::string zeros[] = new std::string[64];
		
		static {
			zeros[63] = "000000000000000000000000000000000000000000000000000000000000000";
			for (int i=0; i<63; i++)
				zeros[i] = zeros[63].substring(0, i);
		}
		
		/**
		 * Returns a copy of the input array stripped of any leading zero bytes.
		 */
		static int[] stripLeadingZeroInts(int val[]);
		
		/**
		 * Returns the input array stripped of any leading zero bytes.
		 * Since the source is trusted the copying may be skipped.
		 */
		static int[] trustedStripLeadingZeroInts(int val[]);
		
		/**
		 * Returns a copy of the input array stripped of any leading zero bytes.
		 */
		static int[] stripLeadingZeroBytes(byte a[]);
		
		/**
		 * Takes an array a representing a negative 2's-complement number and
		 * returns the minimal (no leading zero bytes) unsigned whose value is -a.
		 */
		static int[] makePositive(byte a[]);
		
		/**
		 * Takes an array a representing a negative 2's-complement number and
		 * returns the minimal (no leading zero ints) unsigned whose value is -a.
		 */
		static int[] makePositive(int a[]);
		
		/*
		 * The following two arrays are used for fast std::string conversions.  Both
		 * are indexed by radix.  The first is the number of digits of the given
		 * radix that can fit in a Java long without "going negative", i.e., the
		 * highest integer n such that radix**n < 2**63.  The second is the
		 * "long radix" that tears each number into "long digits", each of which
		 * consists of the number of digits in the corresponding element in
		 * digitsPerLong (longRadix[i] = i**digitPerLong[i]).  Both arrays have
		 * nonsense values in their 0 and 1 elements, as radixes 0 and 1 are not
		 * used.
		 */
		static int digitsPerLong[] = {0, 0,
			62, 39, 31, 27, 24, 22, 20, 19, 18, 18, 17, 17, 16, 16, 15, 15, 15, 14,
			14, 14, 14, 13, 13, 13, 13, 13, 13, 12, 12, 12, 12, 12, 12, 12, 12};
		
		static BigInteger longRadix[] = {null, null,
			valueOf(0x4000000000000000L), valueOf(0x383d9170b85ff80bL),
			valueOf(0x4000000000000000L), valueOf(0x6765c793fa10079dL),
			valueOf(0x41c21cb8e1000000L), valueOf(0x3642798750226111L),
			valueOf(0x1000000000000000L), valueOf(0x12bf307ae81ffd59L),
			valueOf( 0xde0b6b3a7640000L), valueOf(0x4d28cb56c33fa539L),
			valueOf(0x1eca170c00000000L), valueOf(0x780c7372621bd74dL),
			valueOf(0x1e39a5057d810000L), valueOf(0x5b27ac993df97701L),
			valueOf(0x1000000000000000L), valueOf(0x27b95e997e21d9f1L),
			valueOf(0x5da0e1e53c5c8000L), valueOf( 0xb16a458ef403f19L),
			valueOf(0x16bcc41e90000000L), valueOf(0x2d04b7fdd9c0ef49L),
			valueOf(0x5658597bcaa24000L), valueOf( 0x6feb266931a75b7L),
			valueOf( 0xc29e98000000000L), valueOf(0x14adf4b7320334b9L),
			valueOf(0x226ed36478bfa000L), valueOf(0x383d9170b85ff80bL),
			valueOf(0x5a3c23e39c000000L), valueOf( 0x4e900abb53e6b71L),
			valueOf( 0x7600ec618141000L), valueOf( 0xaee5720ee830681L),
			valueOf(0x1000000000000000L), valueOf(0x172588ad4f5f0981L),
			valueOf(0x211e44f7d02c1000L), valueOf(0x2ee56725f06e5c71L),
			valueOf(0x41c21cb8e1000000L)};
		
		/*
		 * These two arrays are the integer analogue of above.
		 */
		static int digitsPerInt[] = {0, 0, 30, 19, 15, 13, 11,
			11, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6,
			6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5};
		
		static int intRadix[] = {0, 0,
			0x40000000, 0x4546b3db, 0x40000000, 0x48c27395, 0x159fd800,
			0x75db9c97, 0x40000000, 0x17179149, 0x3b9aca00, 0xcc6db61,
			0x19a10000, 0x309f1021, 0x57f6c100, 0xa2f1b6f,  0x10000000,
			0x18754571, 0x247dbc80, 0x3547667b, 0x4c4b4000, 0x6b5a6e1d,
			0x6c20a40,  0x8d2d931,  0xb640000,  0xe8d4a51,  0x1269ae40,
			0x17179149, 0x1cb91000, 0x23744899, 0x2b73a840, 0x34e63b41,
			0x40000000, 0x4cfa3cc1, 0x5c13d840, 0x6d91b519, 0x39aa400
		};
		
		/**
		 * Returns the length of the two's complement representation in ints,
		 * including space for at least one sign bit.
		 */
		int intLength();
		
		/* Returns sign bit */
		int signBit();
		
		/* Returns an int of sign bits */
		int signInt();
		
		/**
		 * 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).
		 */
		int getInt(int n);
		
		/**
		 * 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.
		 * Initialize firstNonzeroIntNum field the first time this method is
		 * executed. This method depends on the atomicity of int modifies;
		 * without this guarantee, it would have to be synchronized.
		 */
		int firstNonzeroIntNum();
		
		/** use serialVersionUID from JDK 1.1. for interoperability */
		static final long serialVersionUID = -8287574255936472291L;
		
		/**
		 * Returns the mag array as an array of bytes.
		 */
		byte[] magSerializedForm() {
			int bitLen = (mag.length == 0 ? 0 :
				 	((mag.length - 1) << 5) + bitLen(mag[0]));
			int byteLen = (bitLen + 7)/8;
			byte[] result = new byte[byteLen];
			
			for (int i=byteLen-1, bytesCopied=4, intIndex=mag.length-1, nextInt=0;
					i>=0; i--) {
				if (bytesCopied == 4) {
					nextInt = mag[intIndex--];
					bytesCopied = 1;
				} else {
					nextInt >>>= 8;
					bytesCopied++;
				}
				result[i] = (byte)nextInt;
			}
			return result;
		}
		
		/**
		 * \brief A constructor for internal use that translates the sign-magnitude
		 * representation of a BigInteger into a BigInteger. It checks the
		 * arguments and copies the magnitude so this constructor would be
		 * safe for external use.
		 */
		BigInteger(int signum, int *magnitude);
		
		// Create an integer with the digits between the two indexes
		// Assumes start < end. The result may be negative, but it
		// is to be treated as an unsigned value.
		int parseInt(char[] source, int start, int end);
		
		// Multiply x array times word y in place, and add word z
		static void destructiveMulAdd(int[] x, int y, int z);
		
		/**
		 * \brief Translates the decimal std::string representation of a BigInteger into a
		 * BigInteger.  The std::string representation consists of an optional minus
		 * sign followed by a sequence of one or more decimal digits.  The
		 * character-to-digit mapping is provided by <tt>Character.digit</tt>.
		 * The std::string may not contain any extraneous characters (whitespace, for
		 * example).
		 *
		 * \param val decimal std::string representation of BigInteger.
		 */
		BigInteger(std::string val);
		
		/**
		 * \brief Constructs a randomly generated BigInteger, uniformly distributed over
		 * the range <tt>0</tt> to <tt>(2<sup>numBits</sup> - 1)</tt>, inclusive.
		 * The uniformity of the distribution assumes that a fair source of random
		 * bits is provided in <tt>rnd</tt>.  Note that this constructor always
		 * constructs a non-negative BigInteger.
		 *
		 * \param  numBits maximum bitLength of the new BigInteger.
		 * \param  rnd source of randomness to be used in computing the new BigInteger.
		 */
		BigInteger(int numBits, Random rnd);
		
		/**
		 * \brief Constructs a randomly generated positive BigInteger that is probably
		 * prime, with the specified bitLength.<p>
		 *
		 * It is recommended that the {@link #probablePrime probablePrime}
		 * method be used in preference to this constructor unless there
		 * is a compelling need to specify a certainty.
		 *
		 * \param  bitLength bitLength of the returned BigInteger.
		 * \param  certainty a measure of the uncertainty that the caller is
		 *         willing to tolerate.  The probability that the new BigInteger
		 *	       represents a prime number will exceed
		 *	       <tt>(1 - 1/2<sup>certainty</sup></tt>).  The execution time of
		 *	       this constructor is proportional to the value of this parameter.
		 * \param  rnd source of random bits used to select candidates to be
		 *	       tested for primality.
		 */
		public BigInteger(int bitLength, int certainty, Random rnd);
		
		/**
		 * \brief Returns <tt>true</tt> if this BigInteger is probably prime,
		 * <tt>false</tt> if it's definitely composite.
		 *
		 * This method assumes bitLength > 2.
		 *
		 * \param  certainty a measure of the uncertainty that the caller is
		 *	       willing to tolerate: if the call returns <tt>true</tt>
		 *	       the probability that this BigInteger is prime exceeds
		 *	       <tt>(1 - 1/2<sup>certainty</sup>)</tt>.  The execution time of
		 * 	       this method is proportional to the value of this parameter.
		 * \return <tt>true</tt> if this BigInteger is probably prime,
		 * 	       <tt>false</tt> if it's definitely composite.
		 */
		boolean primeToCertainty(int certainty);
		
		/**
		 * The BigInteger constant two.  (Not exported.)
		 */
		private static final BigInteger TWO = valueOf(2);
		
		// bitsPerDigit in the given radix times 1024
		// Rounded up to avoid underallocation.
		private static long bitsPerDigit[] = { 0, 0,
			1024, 1624, 2048, 2378, 2648, 2875, 3072, 3247, 3402, 3543, 
			3672, 3790, 3899, 4001, 4096, 4186, 4271, 4350, 4426, 4498, 
			4567, 4633, 4696, 4756, 4814, 4870, 4923, 4975, 5025, 5074, 
			5120, 5166, 5210, 5253, 5295};
		
		static int bitCnt(int val);
		
		static int trailingZeroCnt(int val);
		
		static int bitCnt(int val);
		
		static int trailingZeroCnt(int val);
		
		/*
		 * Returns -1, 0 or +1 as big-endian unsigned int array arg1 is
		 * less than, equal to, or greater than arg2.
		 */
		private static int intArrayCmp(int[] arg1, int[] arg2);
		
	public:
		/**
		 * \brief Translates a byte array containing the two's-complement binary
		 * representation of a BigInteger into a BigInteger.  The input array is
		 * assumed to be in <i>big-endian</i> byte-order: the most significant
		 * byte is in the zeroth element.
		 */
		BigInteger(byte *val);
		
		/**
		 * \brief Translates the sign-magnitude representation of a BigInteger into a
		 * BigInteger.  The sign is represented as an integer signum value: -1 for
		 * negative, 0 for zero, or 1 for positive.  The magnitude is a byte array
		 * in <i>big-endian</i> byte-order: the most significant byte is in the
		 * zeroth element.  A zero-length magnitude array is permissible, and will
		 * result inin a BigInteger value of 0, whether signum is -1, 0 or 1.
		 *
		 * \param  signum signum of the number (-1 for negative, 0 for zero, 1
		 * 	       for positive).
		 * \param  magnitude big-endian binary representation of the magnitude of
		 * 	       the number.
		 */
		BigInteger(int signum, byte *magnitude);
		
		/**
		 * \brief Translates the std::string representation of a BigInteger in the specified
		 * radix into a BigInteger.  The std::string representation consists of an
		 * optional minus sign followed by a sequence of one or more digits in the
		 * specified radix.  The character-to-digit mapping is provided by
		 * <tt>Character.digit</tt>.  The std::string may not contain any extraneous
		 * characters (whitespace, for example).
		 *
		 * \param val std::string representation of BigInteger.
		 * \param radix radix to be used in interpreting <tt>val</tt>.
		 */
		BigInteger(std::string val, int radix);
		
		// Constructs a new BigInteger using a char array with radix=10
		BigInteger(char[] val);
		
		/**
		 * \brief Returns a positive BigInteger that is probably prime, with the
		 * specified bitLength. The probability that a BigInteger returned
		 * by this method is composite does not exceed 2<sup>-100</sup>.
		 *
		 * \param  bitLength bitLength of the returned BigInteger.
		 * \param  rnd source of random bits used to select candidates to be
		 *	       tested for primality.
		 * \return a BigInteger of <tt>bitLength</tt> bits that is probably prime
		 */
		public static BigInteger probablePrime(int bitLength, Random rnd);
		
		/**
		 * \brief Returns the first integer greater than this <code>BigInteger</code> that
		 * is probably prime.  The probability that the number returned by this
		 * method is composite does not exceed 2<sup>-100</sup>. This method will
		 * never skip over a prime when searching: if it returns <tt>p</tt>, there
		 * is no prime <tt>q</tt> such that <tt>this &lt; q &lt; p</tt>.
		 *
		 * \return the first integer greater than this <code>BigInteger</code> that is probably prime.
		 */
		BigInteger nextProbablePrime();
		
		/**
		 * \brief Returns a BigInteger whose value is equal to that of the
		 * specified <code>long</code>.  This "static factory method" is
		 * provided in preference to a (<code>long</code>) 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);
		
		/**
		 * The BigInteger constant zero.
		 */
		static final BigInteger ZERO = new BigInteger(new int[0], 0);
		
		/**
		 * The BigInteger constant one.
		 */
		static final BigInteger ONE = valueOf(1);
		
		/**
		 * The BigInteger constant ten.
		 */
		static final BigInteger TEN = valueOf(10);
		
		/**
		 * \brief Returns a BigInteger whose value is <tt>(this + val)</tt>.
		 *
		 * \param  val value to be added to this BigInteger.
		 * \return <tt>this + val</tt>
		 */
		BigInteger add(BigInteger val);
		
		/**
		 * Returns a BigInteger whose value is <tt>(this / val)</tt>.
		 *
		 * \param  val value by which this BigInteger is to be divided.
		 * \return <tt>this / val</tt>
		 */
		BigInteger divide(BigInteger val);
		
		/**
		 * Returns an array of two BigIntegers containing <tt>(this / val)</tt>
		 * followed by <tt>(this % val)</tt>.
		 *
		 * \param  val value by which this BigInteger is to be divided, and the remainder computed.
		 * \return an array of two BigIntegers: the quotient <tt>(this / val)</tt>
		 *	       is the initial element, and the remainder <tt>(this % val)</tt>
		 *	       is the final element.
		 */
		BigInteger[] divideAndRemainder(BigInteger val);
		
		/**
		 * Returns a BigInteger whose value is <tt>(this % val)</tt>.
		 *
		 * @param  val value by which this BigInteger is to be divided, and the
		 *	       remainder computed.
		 * @return <tt>this % val</tt>
		 * @throws ArithmeticException <tt>val==0</tt>
		 */
		BigInteger remainder(BigInteger val);
		
		/**
		 * \brief Returns a BigInteger whose value is <tt>(this<sup>exponent</sup>)</tt>.
		 * Note that <tt>exponent</tt> is an integer rather than a BigInteger.
		 *
		 * \param  exponent exponent to which this BigInteger is to be raised.
		 * \return <tt>this<sup>exponent</sup></tt>
		 */
		BigInteger pow(int exponent);
		
		/**
		 * \brief Returns a BigInteger whose value is the greatest common divisor of
		 * <tt>abs(this)</tt> and <tt>abs(val)</tt>.  Returns 0 if
		 * <tt>this==0 &amp;&amp; val==0</tt>.
		 *
		 * \param  val value with which the GCD is to be computed.
		 * \return <tt>GCD(abs(this), abs(val))</tt>
		 */
		BigInteger gcd(BigInteger val);
		
		/**
		 * Returns a BigInteger whose value is the absolute value of this
		 * BigInteger. 
		 *
		 * @return <tt>abs(this)</tt>
		 */
		BigInteger abs();
		
		/**
		 * Returns a BigInteger whose value is <tt>(-this)</tt>.
		 *
		 * @return <tt>-this</tt>
		 */
		BigInteger negate();
		
		/**
		 * Returns the signum function of this BigInteger.
		 *
		 * @return -1, 0 or 1 as the value of this BigInteger is negative, zero or
		 *	       positive.
		 */
		int signum();
		
		/**
		 * \brief Returns a BigInteger whose value is <tt>(this mod m</tt>).  This method
		 * differs from <tt>remainder</tt> in that it always returns a
		 * <i>non-negative</i> BigInteger.
		 *
		 * \param  m the modulus.
		 * \return <tt>this mod m</tt>
		 */
		BigInteger mod(BigInteger m);
		
		/**
		 * \brief Returns a BigInteger whose value is
		 * <tt>(this<sup>exponent</sup> mod m)</tt>.  (Unlike <tt>pow</tt>, this
		 * method permits negative exponents.)
		 *
		 * \param  exponent the exponent.
		 * \param  m the modulus.
		 * \return <tt>this<sup>exponent</sup> mod m</tt>
		 */
		BigInteger modPow(BigInteger exponent, BigInteger m);
		
		static int[] bnExpModThreshTable = {7, 25, 81, 241, 673, 1793, Integer.MAX_VALUE}; // Sentinel
		
		/**
		 * Returns a BigInteger whose value is <tt>(this<sup>-1</sup> mod m)</tt>.
		 *
		 * @param  m the modulus.
		 * @return <tt>this<sup>-1</sup> mod m</tt>.
		 * @throws ArithmeticException <tt> m &lt;= 0</tt>, or this BigInteger
		 *	       has no multiplicative inverse mod m (that is, this BigInteger
		 *	       is not <i>relatively prime</i> to m).
		 */
		public BigInteger modInverse(BigInteger m);
		
		/**
		 * Returns a BigInteger whose value is <tt>(this &lt;&lt; n)</tt>.
		 * The shift distance, <tt>n</tt>, 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 <tt>this &lt;&lt; n</tt>
		 * @see #shiftRight
		 */
		BigInteger shiftLeft(int n);
		
		/**
		 * Returns a BigInteger whose value is <tt>(this &gt;&gt; n)</tt>.  Sign
		 * extension is performed.  The shift distance, <tt>n</tt>, 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 <tt>this &gt;&gt; n</tt>
		 * @see #shiftLeft
		 */
		BigInteger shiftRight(int n);
		
		int[] javaIncrement(int[] val);
		
		/**
		 * \brief Returns a BigInteger whose value is <tt>(this &amp; val)</tt>.  (This
		 * method returns a negative BigInteger if and only if this and val are
		 * both negative.)
		 *
		 * \param val value to be AND'ed with this BigInteger.
		 * \return <tt>this &amp; val</tt>
		 */
		BigInteger and(BigInteger val);
		
		/**
		 * \brief Returns a BigInteger whose value is <tt>(this | val)</tt>.  (This method
		 * returns a negative BigInteger if and only if either this or val is
		 * negative.) 
		 *
		 * \param val value to be OR'ed with this BigInteger.
		 * \return <tt>this | val</tt>
		 */
		BigInteger or(BigInteger val);
		
		/**
		 * \brief Returns a BigInteger whose value is <tt>(this ^ val)</tt>.  (This method
		 * returns a negative BigInteger if and only if exactly one of this and
		 * val are negative.)
		 *
		 * \param val value to be XOR'ed with this BigInteger.
		 * \return <tt>this ^ val</tt>
		 */
		BigInteger xor(BigInteger val);
		
		/**
		 * Returns a BigInteger whose value is <tt>(~this)</tt>.  (This method
		 * returns a negative value if and only if this BigInteger is
		 * non-negative.)
		 *
		 * @return <tt>~this</tt>
		 */
		BigInteger not();
		
		/**
		 * Returns a BigInteger whose value is <tt>(this &amp; ~val)</tt>.  This
		 * method, which is equivalent to <tt>and(val.not())</tt>, is provided as
		 * a convenience for masking operations.  (This method returns a negative
		 * BigInteger if and only if <tt>this</tt> is negative and <tt>val</tt> is
		 * positive.)
		 *
		 * \param val value to be complemented and AND'ed with this BigInteger.
		 * \return <tt>this &amp; ~val</tt>
		 */
		BigInteger andNot(BigInteger val);
		
		
		/**
		 * \brief Returns <tt>true</tt> if and only if the designated bit is set.
		 * (Computes <tt>((this &amp; (1&lt;&lt;n)) != 0)</tt>.)
		 *
		 * \param  n index of bit to test.
		 * \return <tt>true</tt> if and only if the designated bit is set.
		 */
		boolean testBit(int n);
		
		/**
		 * Returns a BigInteger whose value is equivalent to this BigInteger
		 * with the designated bit set.  (Computes <tt>(this | (1&lt;&lt;n))</tt>.)
		 *
		 * @param  n index of bit to set.
		 * @return <tt>this | (1&lt;&lt;n)</tt>
		 */
		BigInteger setBit(int n);
		
		/**
		 * \brief Returns a BigInteger whose value is equivalent to this BigInteger
		 * with the designated bit cleared.
		 * (Computes <tt>(this &amp; ~(1&lt;&lt;n))</tt>.)
		 *
		 * \param  n index of bit to clear.
		 * \return <tt>this & ~(1&lt;&lt;n)</tt>
		 */
		BigInteger clearBit(int n);
		
		/**
		 * \brief Returns a BigInteger whose value is equivalent to this BigInteger
		 * with the designated bit flipped.
		 * (Computes <tt>(this ^ (1&lt;&lt;n))</tt>.)
		 *
		 * \param  n index of bit to flip.
		 * \return <tt>this ^ (1&lt;&lt;n)</tt>
		 */
		BigInteger flipBit(int n);
		
		/**
		 * \brief Returns the index of the rightmost (lowest-order) one bit in this
		 * BigInteger (the number of zero bits to the right of the rightmost
		 * one bit).  Returns -1 if this BigInteger contains no one bits.
		 * (Computes <tt>(this==0? -1 : log<sub>2</sub>(this &amp; -this))</tt>.)
		 *
		 * Initialize lowestSetBit field the first time this method is
		 * executed. This method depends on the atomicity of int modifies;
		 * without this guarantee, it would have to be synchronized.
		 * 
		 * \return index of the rightmost one bit in this BigInteger.
		 */
		int getLowestSetBit();
		
		/**
		 * \brief 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
		 * <tt>(ceil(log<sub>2</sub>(this &lt; 0 ? -this : this+1)))</tt>.)
		 *
		 * Initialize bitLength field the first time this method is executed.
		 * This method depends on the atomicity of int modifies; without
		 * this guarantee, it would have to be synchronized.
		 *
		 *  \return number of bits in the minimal two's-complement
		 *         representation of this BigInteger, <i>excluding</i> a sign bit.
		 */
		int bitLength();
		
		/**
		 * Returns the number of bits in the two's complement representation
		 * of this BigInteger that differ from its sign bit.  This method is
		 * useful when implementing bit-vector style sets atop BigIntegers.
		 *
		 * Initialize bitCount field the first time this method is executed.
		 * This method depends on the atomicity of int modifies; without
		 * this guarantee, it would have to be synchronized.
		 * 
		 * @return number of bits in the two's complement representation
		 *         of this BigInteger that differ from its sign bit.
		 */
		int bitCount();
		
		/**
		 * Returns a BigInteger whose value is <tt>(this - val)</tt>.
		 *
		 * @param  val value to be subtracted from this BigInteger.
		 * @return <tt>this - val</tt>
		 */
		public BigInteger subtract(BigInteger val);
		
		/**
		 * \brief Returns <tt>true</tt> if this BigInteger is probably prime,
		 * <tt>false</tt> if it's definitely composite.  If
		 * <tt>certainty</tt> is <tt> &lt;= 0</tt>, <tt>true</tt> is
		 * returned.
		 *
		 * \param  certainty a measure of the uncertainty that the caller is
		 *	       willing to tolerate: if the call returns <tt>true</tt>
		 *	       the probability that this BigInteger is prime exceeds
		 *	       <tt>(1 - 1/2<sup>certainty</sup>)</tt>.  The execution time of
		 * 	       this method is proportional to the value of this parameter.
		 * \return <tt>true</tt> if this BigInteger is probably prime,
		 * 	       <tt>false</tt> if it's definitely composite.
		 */
		boolean isProbablePrime(int certainty) {
			
			/**
			 * Compares this BigInteger with the specified BigInteger.  This method is
			 * provided in preference to individual methods for each of the six
			 * boolean comparison operators (&lt;, ==, &gt;, &gt;=, !=, &lt;=).  The
			 * suggested idiom for performing these comparisons is:
			 * <tt>(x.compareTo(y)</tt> &lt;<i>op</i>&gt; <tt>0)</tt>,
			 * where &lt;<i>op</i>&gt; is one of the six comparison operators.
			 *
			 * @param  val BigInteger to which this BigInteger is to be compared.
			 * @return -1, 0 or 1 as this BigInteger is numerically less than, equal
			 *         to, or greater than <tt>val</tt>.
			 */
			int compareTo(BigInteger val);
			
			/**
			 * Compares this BigInteger with the specified jcommon::Object *for equality.
			 *
			 * @param  x jcommon::Object *to which this BigInteger is to be compared.
			 * @return <tt>true</tt> if and only if the specified jcommon::Object *is a
			 *	       BigInteger whose value is numerically equal to this BigInteger.
			 */
			boolean equals(jcommon::Object *x);
			
			/**
			 * \brief Returns the minimum of this BigInteger and <tt>val</tt>.
			 *
			 * \param  val value with which the minimum is to be computed.
			 * \return the BigInteger whose value is the lesser of this BigInteger and 
			 *	       <tt>val</tt>.  If they are equal, either may be returned.
			 */
			BigInteger min(BigInteger val);
			
			/**
			 * \brief Returns the maximum of this BigInteger and <tt>val</tt>.
			 *
			 * \param  val value with which the maximum is to be computed.
			 * \return the BigInteger whose value is the greater of this and
			 *         <tt>val</tt>.  If they are equal, either may be returned.
			 */
			BigInteger max(BigInteger val);
			
			/**
			 * \brief Returns the hash code for this BigInteger.
			 *
			 * \return hash code for this BigInteger.
			 */
			int hashCode();
			
			/**
			 * \brief Returns the std::string representation of this BigInteger in the
			 * given radix.  If the radix is outside the range from {@link
			 * Character#MIN_RADIX} to {@link Character#MAX_RADIX} inclusive,
			 * it will default to 10 (as is the case for
			 * <tt>Integer.tostd::string</tt>).  The digit-to-character mapping
			 * provided by <tt>Character.forDigit</tt> is used, and a minus
			 * sign is prepended if appropriate.  (This representation is
			 * compatible with the {@link #BigInteger(std::string, int) (std::string,
			 * <code>int</code>)} constructor.)
			 *
			 * \param  radix  radix of the std::string representation.
			 * @return std::string representation of this BigInteger in the given radix.
			 */
			std::string tostd::string(int radix);
			
			/**
			 * Returns the decimal std::string representation of this BigInteger.
			 * The digit-to-character mapping provided by
			 * <tt>Character.forDigit</tt> is used, and a minus sign is
			 * prepended if appropriate.  (This representation is compatible
			 * with the {@link #BigInteger(std::string) (std::string)} constructor, and
			 * allows for std::string concatenation with Java's + operator.)
			 *
			 * @return decimal std::string representation of this BigInteger.
			 * @see    Character#forDigit
			 * @see    #BigInteger(java.lang.std::string)
			 */
			std::string tostd::string();
			
			/**
			 * Returns a byte array containing the two's-complement
			 * representation of this BigInteger.  The byte array will be in
			 * <i>big-endian</i> byte-order: the most significant byte is in
			 * the zeroth element.  The array will contain the minimum number
			 * of bytes required to represent this BigInteger, including at
			 * least one sign bit, which is <tt>(ceil((this.bitLength() +
			 * 1)/8))</tt>.  (This representation is compatible with the
			 * {@link #BigInteger(byte[]) (byte[])} constructor.)
			 *
			 * \return a byte array containing the two's-complement representation of this BigInteger.
			 */
			byte[] toByteArray();
			
			/**
			 * \brief Converts this BigInteger to an <code>int</code>.  This
			 * conversion is analogous to a <a
			 * href="http://java.sun.com/docs/books/jls/second_edition/html/conversions.doc.html#25363"><i>narrowing
			 * primitive conversion</i></a> from <code>long</code> to
			 * <code>int</code> as defined in the <a
			 * href="http://java.sun.com/docs/books/jls/html/">Java Language
			 * Specification</a>: if this BigInteger is too big to fit in an
			 * <code>int</code>, 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</code>.
			 */
			int intValue();
			
			/**
			 * Converts this BigInteger to a <code>long</code>.  This
			 * conversion is analogous to a <a
			 * href="http://java.sun.com/docs/books/jls/second_edition/html/conversions.doc.html#25363"><i>narrowing
			 * primitive conversion</i></a> from <code>long</code> to
			 * <code>int</code> as defined in the <a
			 * href="http://java.sun.com/docs/books/jls/html/">Java Language
			 * Specification</a>: if this BigInteger is too big to fit in a
			 * <code>long</code>, 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</code>.
			 */
			long longValue();
			
			/**
			 * \brief Converts this BigInteger to a <code>float</code>.  This
			 * conversion is similar to the <a
			 * href="http://java.sun.com/docs/books/jls/second_edition/html/conversions.doc.html#25363"><i>narrowing
			 * primitive conversion</i></a> from <code>double</code> to
			 * <code>float</code> defined in the <a
			 * href="http://java.sun.com/docs/books/jls/html/">Java Language
			 * Specification</a>: if this BigInteger has too great a magnitude
			 * to represent as a <code>float</code>, it will be converted to
			 * {@link Float#NEGATIVE_INFINITY} or {@link
			 * Float#POSITIVE_INFINITY} as appropriate.  Note that even when
			 * the return value is finite, this conversion can lose
			 * information about the precision of the BigInteger value.
			 *
			 * \return this BigInteger converted to a <code>float</code>.
			 */
			float floatValue();
			
			/**
			 * \brief Converts this BigInteger to a <code>double</code>.  This
			 * conversion is similar to the <a
			 * href="http://java.sun.com/docs/books/jls/second_edition/html/conversions.doc.html#25363"><i>narrowing
			 * primitive conversion</i></a> from <code>double</code> to
			 * <code>float</code> defined in the <a
			 * href="http://java.sun.com/docs/books/jls/html/">Java Language
			 * Specification</a>: if this BigInteger has too great a magnitude
			 * to represent as a <code>double</code>, it will be converted to
			 * {@link Double#NEGATIVE_INFINITY} or {@link
			 * Double#POSITIVE_INFINITY} as appropriate.  Note that even when
			 * the return value is finite, this conversion can lose
			 * information about the precision of the BigInteger value.
			 *
			 * \return this BigInteger converted to a <code>double</code>.
			 */
			double doubleValue();
			
};
		
};

#endif