1 // BigInteger.java -- an arbitrary-precision integer
3 /* Copyright (C) 1999, 2000 Red Hat, Inc.
5 This file is part of libgcj.
7 This software is copyrighted work licensed under the terms of the
8 Libgcj License. Please consult the file "LIBGCJ_LICENSE" for
12 import gnu.gcj.math.*;
13 import java.util.Random;
16 * @author Warren Levy <warrenl@cygnus.com>
17 * @date December 20, 1999.
21 * Written using on-line Java Platform 1.2 API Specification, as well
22 * as "The Java Class Libraries", 2nd edition (Addison-Wesley, 1998).
24 * Based primarily on IntNum.java BitOps.java by Per Bothner <per@bothner.com>
25 * (found in Kawa 1.6.62).
27 * Status: Believed complete and correct.
30 public class BigInteger extends Number implements Comparable
32 /** All integers are stored in 2's-complement form.
33 * If words == null, the ival is the value of this BigInteger.
34 * Otherwise, the first ival elements of words make the value
35 * of this BigInteger, stored in little-endian order, 2's-complement form. */
40 /** We pre-allocate integers in the range minFixNum..maxFixNum. */
41 private static final int minFixNum = -100;
42 private static final int maxFixNum = 1024;
43 private static final int numFixNum = maxFixNum-minFixNum+1;
44 private static final BigInteger[] smallFixNums = new BigInteger[numFixNum];
47 for (int i = numFixNum; --i >= 0; )
48 smallFixNums[i] = new BigInteger(i + minFixNum);
52 public static final BigInteger ZERO = smallFixNums[-minFixNum];
55 public static final BigInteger ONE = smallFixNums[1 - minFixNum];
58 private static final int FLOOR = 1;
59 private static final int CEILING = 2;
60 private static final int TRUNCATE = 3;
61 private static final int ROUND = 4;
67 /* Create a new (non-shared) BigInteger, and initialize to an int. */
68 private BigInteger(int value)
73 public BigInteger(String val, int radix)
75 BigInteger result = valueOf(val, radix);
76 this.ival = result.ival;
77 this.words = result.words;
80 public BigInteger(String val)
85 /* Create a new (non-shared) BigInteger, and initialize from a byte array. */
86 public BigInteger(byte[] val)
88 if (val == null || val.length < 1)
89 throw new NumberFormatException();
91 words = byteArrayToIntArray(val, val[0] < 0 ? -1 : 0);
92 BigInteger result = make(words, words.length);
93 this.ival = result.ival;
94 this.words = result.words;
97 public BigInteger(int signum, byte[] magnitude)
99 if (magnitude == null || signum > 1 || signum < -1)
100 throw new NumberFormatException();
105 for (i = magnitude.length - 1; i >= 0 && magnitude[i] == 0; --i)
108 throw new NumberFormatException();
112 // Magnitude is always positive, so don't ever pass a sign of -1.
113 words = byteArrayToIntArray(magnitude, 0);
114 BigInteger result = make(words, words.length);
115 this.ival = result.ival;
116 this.words = result.words;
122 public BigInteger(int numBits, Random rnd)
125 throw new IllegalArgumentException();
127 // Result is always positive so tack on an extra zero word, it will be
128 // canonicalized out later if necessary.
129 int nwords = numBits / 32 + 2;
130 words = new int[nwords];
132 words[--nwords] = rnd.nextInt() >>> (numBits % 32);
133 while (--nwords >= 0)
134 words[nwords] = rnd.nextInt();
136 BigInteger result = make(words, words.length);
137 this.ival = result.ival;
138 this.words = result.words;
142 /** Return a (possibly-shared) BigInteger with a given long value. */
143 private static BigInteger make(long value)
145 if (value >= minFixNum && value <= maxFixNum)
146 return smallFixNums[(int)value - minFixNum];
148 if ((long)i == value)
149 return new BigInteger(i);
150 BigInteger result = alloc(2);
153 result.words[1] = (int) (value >> 32);
157 // FIXME: Could simply rename 'make' method above as valueOf while
158 // changing all instances of 'make'. Don't do this until this class
159 // is done as the Kawa class this is based on has 'make' methods
160 // with other parameters; wait to see if they are used in BigInteger.
161 public static BigInteger valueOf(long val)
166 /** Make a canonicalized BigInteger from an array of words.
167 * The array may be reused (without copying). */
168 private static BigInteger make(int[] words, int len)
172 len = BigInteger.wordsNeeded(words, len);
174 return len == 0 ? ZERO : make(words[0]);
175 BigInteger num = new BigInteger();
181 /** Convert a big-endian byte array to a little-endian array of words. */
182 private static int[] byteArrayToIntArray(byte[] bytes, int sign)
184 // Determine number of words needed.
185 int[] words = new int[(bytes.length + 3) / 4 + 1];
186 int nwords = words.length;
188 // For simplicity, tack on an extra word of sign at the front,
189 // it will be canonicalized out later. */
190 words[--nwords] = sign;
192 // Create a int out of modulo 4 high order bytes.
195 for (int i = bytes.length % 4; i > 0; --i, bptr++)
196 word = (word << 8) | (((int) bytes[bptr]) & 0xff);
197 words[--nwords] = word;
199 // Elements remaining in byte[] are a multiple of 4.
201 words[--nwords] = bytes[bptr++] << 24 |
202 (((int) bytes[bptr++]) & 0xff) << 16 |
203 (((int) bytes[bptr++]) & 0xff) << 8 |
204 (((int) bytes[bptr++]) & 0xff);
208 /** Allocate a new non-shared BigInteger.
209 * @param nwords number of words to allocate
211 private static BigInteger alloc(int nwords)
214 return new BigInteger();
215 BigInteger result = new BigInteger();
216 result.words = new int[nwords];
220 /** Change words.length to nwords.
221 * We allow words.length to be upto nwords+2 without reallocating.
223 private void realloc(int nwords)
234 else if (words == null
235 || words.length < nwords
236 || words.length > nwords + 2)
238 int[] new_words = new int [nwords];
248 System.arraycopy(words, 0, new_words, 0, ival);
254 private final boolean isNegative()
256 return (words == null ? ival : words[ival - 1]) < 0;
261 int top = words == null ? ival : words[ival-1];
262 return top > 0 ? 1 : top < 0 ? -1 : 0;
265 private static int compareTo(BigInteger x, BigInteger y)
267 if (x.words == null && y.words == null)
268 return x.ival < y.ival ? -1 : x.ival > y.ival ? 1 : 0;
269 boolean x_negative = x.isNegative();
270 boolean y_negative = y.isNegative();
271 if (x_negative != y_negative)
272 return x_negative ? -1 : 1;
273 int x_len = x.words == null ? 1 : x.ival;
274 int y_len = y.words == null ? 1 : y.ival;
276 return (x_len > y_len) != x_negative ? 1 : -1;
277 return MPN.cmp(x.words, y.words, x_len);
281 public int compareTo(Object obj)
283 if (obj instanceof BigInteger)
284 return compareTo(this, (BigInteger) obj);
285 throw new ClassCastException();
288 public int compareTo(BigInteger val)
290 return compareTo(this, val);
293 private final boolean isOdd()
295 int low = words == null ? ival : words[0];
296 return (low & 1) != 0;
299 private final boolean isZero()
301 return words == null && ival == 0;
304 private final boolean isOne()
306 return words == null && ival == 1;
309 private final boolean isMinusOne()
311 return words == null && ival == -1;
314 /** Calculate how many words are significant in words[0:len-1].
315 * Returns the least value x such that x>0 && words[0:x-1]==words[0:len-1],
316 * when words is viewed as a 2's complement integer.
318 private static int wordsNeeded(int[] words, int len)
323 int word = words[--i];
326 while (i > 0 && (word = words[i - 1]) < 0)
329 if (word != -1) break;
334 while (word == 0 && i > 0 && (word = words[i - 1]) >= 0) i--;
340 private BigInteger canonicalize()
343 && (ival = BigInteger.wordsNeeded(words, ival)) <= 1)
349 if (words == null && ival >= minFixNum && ival <= maxFixNum)
350 return smallFixNums[(int) ival - minFixNum];
354 /** Add two ints, yielding a BigInteger. */
355 private static final BigInteger add(int x, int y)
357 return BigInteger.make((long) x + (long) y);
360 /** Add a BigInteger and an int, yielding a new BigInteger. */
361 private static BigInteger add(BigInteger x, int y)
364 return BigInteger.add(x.ival, y);
365 BigInteger result = new BigInteger(0);
367 return result.canonicalize();
370 /** Set this to the sum of x and y.
372 private void setAdd(BigInteger x, int y)
376 set((long) x.ival + (long) y);
382 for (int i = 0; i < len; i++)
384 carry += ((long) x.words[i] & 0xffffffffL);
385 words[i] = (int) carry;
388 if (x.words[len - 1] < 0)
390 words[len] = (int) carry;
391 ival = wordsNeeded(words, len + 1);
394 /** Destructively add an int to this. */
395 private final void setAdd(int y)
400 /** Destructively set the value of this to a long. */
401 private final void set(long y)
413 words[1] = (int) (y >> 32);
418 /** Destructively set the value of this to the given words.
419 * The words array is reused, not copied. */
420 private final void set(int[] words, int length)
426 /** Destructively set the value of this to that of y. */
427 private final void set(BigInteger y)
434 System.arraycopy(y.words, 0, words, 0, y.ival);
439 /** Add two BigIntegers, yielding their sum as another BigInteger. */
440 private static BigInteger add(BigInteger x, BigInteger y, int k)
442 if (x.words == null && y.words == null)
443 return BigInteger.make((long) k * (long) y.ival + (long) x.ival);
447 y = BigInteger.neg(y);
449 y = BigInteger.times(y, BigInteger.make(k));
452 return BigInteger.add(y, x.ival);
454 return BigInteger.add(x, y.ival);
458 { // Swap so x is longer then y.
459 BigInteger tmp = x; x = y; y = tmp;
461 BigInteger result = alloc(x.ival + 1);
463 long carry = MPN.add_n(result.words, x.words, y.words, i);
464 long y_ext = y.words[i - 1] < 0 ? 0xffffffffL : 0;
465 for (; i < x.ival; i++)
467 carry += ((long) x.words[i] & 0xffffffffL) + y_ext;;
468 result.words[i] = (int) carry;
471 if (x.words[i - 1] < 0)
473 result.words[i] = (int) (carry + y_ext);
475 return result.canonicalize();
478 public BigInteger add(BigInteger val)
480 return add(this, val, 1);
483 public BigInteger subtract(BigInteger val)
485 return add(this, val, -1);
488 private static final BigInteger times(BigInteger x, int y)
494 int[] xwords = x.words;
497 return BigInteger.make((long) xlen * (long) y);
499 BigInteger result = BigInteger.alloc(xlen + 1);
500 if (xwords[xlen - 1] < 0)
503 negate(result.words, xwords, xlen);
504 xwords = result.words;
510 negative = !negative;
513 result.words[xlen] = MPN.mul_1(result.words, xwords, xlen, y);
514 result.ival = xlen + 1;
516 result.setNegative();
517 return result.canonicalize();
520 private static final BigInteger times(BigInteger x, BigInteger y)
523 return times(x, y.ival);
525 return times(y, x.ival);
526 boolean negative = false;
534 xwords = new int[xlen];
535 negate(xwords, x.words, xlen);
544 negative = !negative;
545 ywords = new int[ylen];
546 negate(ywords, y.words, ylen);
550 // Swap if x is shorter then y.
553 int[] twords = xwords; xwords = ywords; ywords = twords;
554 int tlen = xlen; xlen = ylen; ylen = tlen;
556 BigInteger result = BigInteger.alloc(xlen+ylen);
557 MPN.mul(result.words, xwords, xlen, ywords, ylen);
558 result.ival = xlen+ylen;
560 result.setNegative();
561 return result.canonicalize();
564 public BigInteger multiply(BigInteger y)
566 return times(this, y);
569 private static void divide(long x, long y,
570 BigInteger quotient, BigInteger remainder,
573 boolean xNegative, yNegative;
577 if (x == Long.MIN_VALUE)
579 divide(BigInteger.make(x), BigInteger.make(y),
580 quotient, remainder, rounding_mode);
591 if (y == Long.MIN_VALUE)
593 if (rounding_mode == TRUNCATE)
594 { // x != Long.Min_VALUE implies abs(x) < abs(y)
595 if (quotient != null)
597 if (remainder != null)
601 divide(BigInteger.make(x), BigInteger.make(y),
602 quotient, remainder, rounding_mode);
612 boolean qNegative = xNegative ^ yNegative;
614 boolean add_one = false;
617 switch (rounding_mode)
623 if (qNegative == (rounding_mode == FLOOR))
627 add_one = r > ((y - (q & 1)) >> 1);
631 if (quotient != null)
639 if (remainder != null)
641 // The remainder is by definition: X-Q*Y
644 // Subtract the remainder from Y.
646 // In this case, abs(Q*Y) > abs(X).
647 // So sign(remainder) = -sign(X).
648 xNegative = ! xNegative;
652 // If !add_one, then: abs(Q*Y) <= abs(X).
653 // So sign(remainder) = sign(X).
661 /** Divide two integers, yielding quotient and remainder.
662 * @param x the numerator in the division
663 * @param y the denominator in the division
664 * @param quotient is set to the quotient of the result (iff quotient!=null)
665 * @param remainder is set to the remainder of the result
666 * (iff remainder!=null)
667 * @param rounding_mode one of FLOOR, CEILING, TRUNCATE, or ROUND.
669 private static void divide(BigInteger x, BigInteger y,
670 BigInteger quotient, BigInteger remainder,
673 if ((x.words == null || x.ival <= 2)
674 && (y.words == null || y.ival <= 2))
676 long x_l = x.longValue();
677 long y_l = y.longValue();
678 if (x_l != Long.MIN_VALUE && y_l != Long.MIN_VALUE)
680 divide(x_l, y_l, quotient, remainder, rounding_mode);
685 boolean xNegative = x.isNegative();
686 boolean yNegative = y.isNegative();
687 boolean qNegative = xNegative ^ yNegative;
689 int ylen = y.words == null ? 1 : y.ival;
690 int[] ywords = new int[ylen];
691 y.getAbsolute(ywords);
692 while (ylen > 1 && ywords[ylen - 1] == 0) ylen--;
694 int xlen = x.words == null ? 1 : x.ival;
695 int[] xwords = new int[xlen+2];
696 x.getAbsolute(xwords);
697 while (xlen > 1 && xwords[xlen-1] == 0) xlen--;
701 int cmpval = MPN.cmp(xwords, xlen, ywords, ylen);
702 if (cmpval < 0) // abs(x) < abs(y)
703 { // quotient = 0; remainder = num.
704 int[] rwords = xwords; xwords = ywords; ywords = rwords;
705 rlen = xlen; qlen = 1; xwords[0] = 0;
707 else if (cmpval == 0) // abs(x) == abs(y)
709 xwords[0] = 1; qlen = 1; // quotient = 1
710 ywords[0] = 0; rlen = 1; // remainder = 0;
716 ywords[0] = MPN.divmod_1(xwords, xwords, xlen, ywords[0]);
718 else // abs(x) > abs(y)
720 // Normalize the denominator, i.e. make its most significant bit set by
721 // shifting it normalization_steps bits to the left. Also shift the
722 // numerator the same number of steps (to keep the quotient the same!).
724 int nshift = MPN.count_leading_zeros(ywords[ylen - 1]);
727 // Shift up the denominator setting the most significant bit of
728 // the most significant word.
729 MPN.lshift(ywords, 0, ywords, ylen, nshift);
731 // Shift up the numerator, possibly introducing a new most
733 int x_high = MPN.lshift(xwords, 0, xwords, xlen, nshift);
734 xwords[xlen++] = x_high;
739 MPN.divide(xwords, xlen, ywords, ylen);
741 if (remainder != null || rounding_mode != TRUNCATE)
744 System.arraycopy(xwords, 0, ywords, 0, rlen);
746 MPN.rshift(ywords, xwords, 0, rlen, nshift);
749 qlen = xlen + 1 - ylen;
750 if (quotient != null)
752 for (int i = 0; i < qlen; i++)
753 xwords[i] = xwords[i+ylen];
757 // Now the quotient is in xwords, and the remainder is in ywords.
759 boolean add_one = false;
760 if (rlen > 1 || ywords[0] != 0)
761 { // Non-zero remainder i.e. in-exact quotient.
762 switch (rounding_mode)
768 if (qNegative == (rounding_mode == FLOOR))
772 // int cmp = compareTo(remainder<<1, abs(y));
773 BigInteger tmp = remainder == null ? new BigInteger() : remainder;
774 tmp.set(ywords, rlen);
778 int cmp = compareTo(tmp, y);
779 // Now cmp == compareTo(sign(y)*(remainder<<1), y)
782 add_one = (cmp == 1) || (cmp == 0 && (xwords[0]&1) != 0);
785 if (quotient != null)
787 quotient.set(xwords, qlen);
790 if (add_one) // -(quotient + 1) == ~(quotient)
791 quotient.setInvert();
793 quotient.setNegative();
798 if (remainder != null)
800 // The remainder is by definition: X-Q*Y
801 remainder.set(ywords, rlen);
804 // Subtract the remainder from Y:
805 // abs(R) = abs(Y) - abs(orig_rem) = -(abs(orig_rem) - abs(Y)).
810 tmp.set(yNegative ? ywords[0] + y.ival : ywords[0] - y.ival);
813 tmp = BigInteger.add(remainder, y, yNegative ? 1 : -1);
815 // In this case, abs(Q) = 1 + floor(abs(X)/abs(Y)).
816 // Hence, abs(Q*Y) > abs(X).
817 // So sign(remainder) = -sign(X).
819 remainder.setNegative(tmp);
825 // If !add_one, then: abs(Q*Y) <= abs(X).
826 // So sign(remainder) = sign(X).
828 remainder.setNegative();
833 public BigInteger divide(BigInteger val)
836 throw new ArithmeticException("divisor is zero");
838 BigInteger quot = new BigInteger();
839 divide(this, val, quot, null, TRUNCATE);
840 return quot.canonicalize();
843 public BigInteger remainder(BigInteger val)
846 throw new ArithmeticException("divisor is zero");
848 BigInteger rem = new BigInteger();
849 divide(this, val, null, rem, TRUNCATE);
850 return rem.canonicalize();
853 public BigInteger[] divideAndRemainder(BigInteger val)
856 throw new ArithmeticException("divisor is zero");
858 BigInteger[] result = new BigInteger[2];
859 result[0] = new BigInteger();
860 result[1] = new BigInteger();
861 divide(this, val, result[0], result[1], TRUNCATE);
862 result[0].canonicalize();
863 result[1].canonicalize();
867 public BigInteger mod(BigInteger m)
869 if (m.isNegative() || m.isZero())
870 throw new ArithmeticException("non-positive modulus");
872 BigInteger rem = new BigInteger();
873 divide(this, m, null, rem, FLOOR);
874 return rem.canonicalize();
877 /** Calculate power for BigInteger exponents.
878 * @param y exponent assumed to be non-negative. */
879 private BigInteger pow(BigInteger y)
884 return y.isOdd () ? this : ONE;
885 if (y.words == null && y.ival >= 0)
888 // Assume exponent is non-negative.
892 // Implemented by repeated squaring and multiplication.
893 BigInteger pow2 = this;
895 for (;;) // for (i = 0; ; i++)
898 // prod = x**(sum(j=0..i-1, (y>>j)&1))
900 r = r == null ? pow2 : times(r, pow2); // r *= pow2
901 y = BigInteger.shift(y, -1);
905 pow2 = times(pow2, pow2);
907 return r == null ? ONE : r;
910 /** Calculate the integral power of a BigInteger.
911 * @param exponent the exponent (must be non-negative)
913 public BigInteger pow(int exponent)
920 throw new ArithmeticException("negative exponent");
924 int plen = words == null ? 1 : ival; // Length of pow2.
925 int blen = ((bitLength() * exponent) >> 5) + 2 * plen;
926 boolean negative = isNegative() && (exponent & 1) != 0;
927 int[] pow2 = new int [blen];
928 int[] rwords = new int [blen];
929 int[] work = new int [blen];
930 getAbsolute(pow2); // pow2 = abs(this);
932 rwords[0] = 1; // rwords = 1;
933 for (;;) // for (i = 0; ; i++)
935 // pow2 == this**(2**i)
936 // prod = this**(sum(j=0..i-1, (exponent>>j)&1))
937 if ((exponent & 1) != 0)
939 MPN.mul(work, pow2, plen, rwords, rlen);
940 int[] temp = work; work = rwords; rwords = temp;
942 while (rwords[rlen - 1] == 0) rlen--;
948 MPN.mul(work, pow2, plen, pow2, plen);
949 int[] temp = work; work = pow2; pow2 = temp; // swap to avoid a copy
951 while (pow2[plen - 1] == 0) plen--;
953 if (rwords[rlen - 1] < 0)
956 negate(rwords, rwords, rlen);
957 return BigInteger.make(rwords, rlen);
960 private static final int[] euclidInv(int a, int b, int prevDiv)
962 // Storage for return values, plus one slot for a temp int (see below).
966 throw new ArithmeticException("not invertible");
969 // Success: values are indeed invertible!
970 // Bottom of the recursion reached; start unwinding.
977 xy = euclidInv(b, a % b, a / b); // Recursion happens here.
979 // xy[2] is just temp storage for intermediate results in the following
980 // calculation. This saves us a bit of space over having an int
981 // allocated at every level of this recursive method.
983 xy[0] = xy[2] * -prevDiv + xy[1];
988 private static final BigInteger[]
989 euclidInv(BigInteger a, BigInteger b, BigInteger prevDiv)
991 // FIXME: This method could be more efficient memory-wise and should be
992 // modified as such since it is recursive.
994 // Storage for return values, plus one slot for a temp int (see below).
998 throw new ArithmeticException("not invertible");
1001 // Success: values are indeed invertible!
1002 // Bottom of the recursion reached; start unwinding.
1003 xy = new BigInteger[3];
1004 xy[0] = neg(prevDiv);
1009 // Recursion happens in the following conditional!
1011 // If a just contains an int, then use integer math for the rest.
1012 if (a.words == null)
1014 int[] xyInt = euclidInv(b.ival, a.ival % b.ival, a.ival / b.ival);
1015 xy = new BigInteger[3];
1016 xy[0] = new BigInteger(xyInt[0]);
1017 xy[1] = new BigInteger(xyInt[1]);
1021 BigInteger rem = new BigInteger();
1022 BigInteger quot = new BigInteger();
1023 divide(a, b, quot, rem, FLOOR);
1024 xy = euclidInv(b, rem, quot);
1027 // xy[2] is just temp storage for intermediate results in the following
1028 // calculation. This saves us a bit of space over having a BigInteger
1029 // allocated at every level of this recursive method.
1031 xy[0] = add(xy[1], times(xy[2], prevDiv), -1);
1036 public BigInteger modInverse(BigInteger y)
1038 if (y.isNegative() || y.isZero())
1039 throw new ArithmeticException("non-positive modulo");
1041 // Degenerate cases.
1047 // Use Euclid's algorithm as in gcd() but do this recursively
1048 // rather than in a loop so we can use the intermediate results as we
1049 // unwind from the recursion.
1050 // Used http://www.math.nmsu.edu/~crypto/EuclideanAlgo.html as reference.
1051 BigInteger result = new BigInteger();
1054 boolean swapped = false;
1056 if (y.words == null)
1058 // The result is guaranteed to be less than the modulus, y (which is
1059 // an int), so simplify this by working with the int result of this
1060 // modulo y. Also, if this is negative, make it positive via modulo
1061 // math. Note that BigInteger.mod() must be used even if this is
1062 // already an int as the % operator would provide a negative result if
1063 // this is negative, BigInteger.mod() never returns negative values.
1064 if (words != null || isNegative())
1067 // Swap values so x > y.
1070 int tmp = xval; xval = yval; yval = tmp;
1073 // Normally, the result is in the 2nd element of the array, but
1074 // if originally x < y, then x and y were swapped and the result
1075 // is in the 1st element of the array.
1077 euclidInv(yval, xval % yval, xval / yval)[swapped ? 0 : 1];
1079 // Result can't be negative, so make it positive by adding the
1080 // original modulus, y.ival (not the possibly "swapped" yval).
1081 if (result.ival < 0)
1082 result.ival += y.ival;
1086 BigInteger x = this;
1088 // As above, force this to be a positive value via modulo math.
1092 // Swap values so x > y.
1093 if (x.compareTo(y) < 0)
1095 BigInteger tmp = x; x = y; y = tmp;
1098 // As above (for ints), result will be in the 2nd element unless
1099 // the original x and y were swapped.
1100 BigInteger rem = new BigInteger();
1101 BigInteger quot = new BigInteger();
1102 divide(x, y, quot, rem, FLOOR);
1103 result = euclidInv(y, rem, quot)[swapped ? 0 : 1];
1105 // Result can't be negative, so make it positive by adding the
1106 // original modulus, y (which is now x if they were swapped).
1107 if (result.isNegative())
1108 result = add(result, swapped ? x : y, 1);
1114 public BigInteger modPow(BigInteger exponent, BigInteger m)
1116 if (m.isNegative() || m.isZero())
1117 throw new ArithmeticException("non-positive modulo");
1119 if (exponent.isNegative())
1120 return modInverse(m);
1121 if (exponent.isOne())
1124 return pow(exponent).mod(m);
1127 /** Calculate Greatest Common Divisor for non-negative ints. */
1128 private static final int gcd(int a, int b)
1130 // Euclid's algorithm, copied from libg++.
1133 int tmp = a; a = b; b = tmp;
1150 public BigInteger gcd(BigInteger y)
1157 return BigInteger.abs(y);
1159 && xval != Integer.MIN_VALUE && yval != Integer.MIN_VALUE)
1165 return BigInteger.make(BigInteger.gcd(xval, yval));
1169 if (y.words == null)
1172 return BigInteger.abs(this);
1175 int len = (xval > yval ? xval : yval) + 1;
1176 int[] xwords = new int[len];
1177 int[] ywords = new int[len];
1178 getAbsolute(xwords);
1179 y.getAbsolute(ywords);
1180 len = MPN.gcd(xwords, ywords, len);
1181 BigInteger result = new BigInteger(0);
1183 result.words = xwords;
1184 return result.canonicalize();
1187 private void setInvert()
1193 for (int i = ival; --i >= 0; )
1194 words[i] = ~words[i];
1198 private void setShiftLeft(BigInteger x, int count)
1202 if (x.words == null)
1206 set((long) x.ival << count);
1209 xwords = new int[1];
1218 int word_count = count >> 5;
1220 int new_len = xlen + word_count;
1224 for (int i = xlen; --i >= 0; )
1225 words[i+word_count] = xwords[i];
1231 int shift_out = MPN.lshift(words, word_count, xwords, xlen, count);
1233 words[new_len-1] = (shift_out << count) >> count; // sign-extend.
1236 for (int i = word_count; --i >= 0; )
1240 private void setShiftRight(BigInteger x, int count)
1242 if (x.words == null)
1243 set(count < 32 ? x.ival >> count : x.ival < 0 ? -1 : 0);
1244 else if (count == 0)
1248 boolean neg = x.isNegative();
1249 int word_count = count >> 5;
1251 int d_len = x.ival - word_count;
1256 if (words == null || words.length < d_len)
1258 MPN.rshift(words, x.words, word_count, d_len, count);
1261 words[ival-1] |= -1 << (32 - count);
1266 private void setShift(BigInteger x, int count)
1269 setShiftLeft(x, count);
1271 setShiftRight(x, -count);
1274 private static BigInteger shift(BigInteger x, int count)
1276 if (x.words == null)
1279 return make(count > -32 ? x.ival >> (-count) : x.ival < 0 ? -1 : 0);
1281 return make((long) x.ival << count);
1285 BigInteger result = new BigInteger(0);
1286 result.setShift(x, count);
1287 return result.canonicalize();
1290 public BigInteger shiftLeft(int n)
1292 return shift(this, n);
1295 public BigInteger shiftRight(int n)
1297 return shift(this, -n);
1300 private void format(int radix, StringBuffer buffer)
1303 buffer.append(Integer.toString(ival, radix));
1305 buffer.append(Long.toString(longValue(), radix));
1308 boolean neg = isNegative();
1310 if (neg || radix != 16)
1312 work = new int[ival];
1319 int buf_size = len * (MPN.chars_per_word(radix) + 1);
1324 int buf_start = buffer.length();
1325 for (int i = len; --i >= 0; )
1328 for (int j = 8; --j >= 0; )
1330 int hex_digit = (word >> (4 * j)) & 0xF;
1331 // Suppress leading zeros:
1332 if (hex_digit > 0 || buffer.length() > buf_start)
1333 buffer.append(Character.forDigit(hex_digit, 16));
1339 int i = buffer.length();
1342 int digit = MPN.divmod_1(work, work, len, radix);
1343 buffer.append(Character.forDigit(digit, radix));
1344 while (len > 0 && work[len-1] == 0) len--;
1350 /* Reverse buffer. */
1351 int j = buffer.length() - 1;
1354 char tmp = buffer.charAt(i);
1355 buffer.setCharAt(i, buffer.charAt(j));
1356 buffer.setCharAt(j, tmp);
1363 public String toString()
1365 return toString(10);
1368 public String toString(int radix)
1371 return Integer.toString(ival, radix);
1373 return Long.toString(longValue(), radix);
1374 int buf_size = ival * (MPN.chars_per_word(radix) + 1);
1375 StringBuffer buffer = new StringBuffer(buf_size);
1376 format(radix, buffer);
1377 return buffer.toString();
1380 public int intValue()
1387 public long longValue()
1393 return ((long)words[1] << 32) + ((long)words[0] & 0xffffffffL);
1396 public int hashCode()
1398 // FIXME: May not match hashcode of JDK.
1399 return words == null ? ival : (words[0] + words[ival - 1]);
1402 /* Assumes x and y are both canonicalized. */
1403 private static boolean equals(BigInteger x, BigInteger y)
1405 if (x.words == null && y.words == null)
1406 return x.ival == y.ival;
1407 if (x.words == null || y.words == null || x.ival != y.ival)
1409 for (int i = x.ival; --i >= 0; )
1411 if (x.words[i] != y.words[i])
1417 /* Assumes this and obj are both canonicalized. */
1418 public boolean equals(Object obj)
1420 if (obj == null || ! (obj instanceof BigInteger))
1422 return BigInteger.equals(this, (BigInteger) obj);
1425 private static BigInteger valueOf(String s, int radix)
1426 throws NumberFormatException
1428 int len = s.length();
1429 // Testing (len < MPN.chars_per_word(radix)) would be more accurate,
1430 // but slightly more expensive, for little practical gain.
1431 if (len <= 15 && radix <= 16)
1432 return BigInteger.make(Long.parseLong(s, radix));
1435 byte[] bytes = new byte[len];
1436 boolean negative = false;
1437 for (int i = 0; i < len; i++)
1439 char ch = s.charAt(i);
1442 else if (ch == '_' || (byte_len == 0 && (ch == ' ' || ch == '\t')))
1446 int digit = Character.digit(ch, radix);
1449 bytes[byte_len++] = (byte) digit;
1452 return valueOf(bytes, byte_len, negative, radix);
1455 private static BigInteger valueOf(byte[] digits, int byte_len,
1456 boolean negative, int radix)
1458 int chars_per_word = MPN.chars_per_word(radix);
1459 int[] words = new int[byte_len / chars_per_word + 1];
1460 int size = MPN.set_str(words, digits, byte_len, radix);
1463 if (words[size-1] < 0)
1466 negate(words, words, size);
1467 return make(words, size);
1470 public double doubleValue()
1473 return (double) ival;
1475 return (double) longValue();
1477 return BigInteger.neg(this).roundToDouble(0, true, false);
1479 return roundToDouble(0, false, false);
1482 public float floatValue()
1484 return (float) doubleValue();
1487 /** Return true if any of the lowest n bits are one.
1488 * (false if n is negative). */
1489 private boolean checkBits(int n)
1494 return n > 31 || ((ival & ((1 << n) - 1)) != 0);
1496 for (i = 0; i < (n >> 5) ; i++)
1499 return (n & 31) != 0 && (words[i] & ((1 << (n & 31)) - 1)) != 0;
1502 /** Convert a semi-processed BigInteger to double.
1503 * Number must be non-negative. Multiplies by a power of two, applies sign,
1504 * and converts to double, with the usual java rounding.
1505 * @param exp power of two, positive or negative, by which to multiply
1506 * @param neg true if negative
1507 * @param remainder true if the BigInteger is the result of a truncating
1508 * division that had non-zero remainder. To ensure proper rounding in
1509 * this case, the BigInteger must have at least 54 bits. */
1510 private double roundToDouble(int exp, boolean neg, boolean remainder)
1513 int il = bitLength();
1515 // Exponent when normalized to have decimal point directly after
1516 // leading one. This is stored excess 1023 in the exponent bit field.
1519 // Gross underflow. If exp == -1075, we let the rounding
1520 // computation determine whether it is minval or 0 (which are just
1521 // 0x0000 0000 0000 0001 and 0x0000 0000 0000 0000 as bit
1524 return neg ? -0.0 : 0.0;
1528 return neg ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
1530 // number of bits in mantissa, including the leading one.
1531 // 53 unless it's denormalized
1532 int ml = (exp >= -1022 ? 53 : 53 + exp + 1022);
1534 // Get top ml + 1 bits. The extra one is for rounding.
1536 int excess_bits = il - (ml + 1);
1537 if (excess_bits > 0)
1538 m = ((words == null) ? ival >> excess_bits
1539 : MPN.rshift_long(words, ival, excess_bits));
1541 m = longValue() << (- excess_bits);
1543 // Special rounding for maxval. If the number exceeds maxval by
1544 // any amount, even if it's less than half a step, it overflows.
1545 if (exp == 1023 && ((m >> 1) == (1L << 53) - 1))
1547 if (remainder || checkBits(il - ml))
1548 return neg ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
1550 return neg ? - Double.MAX_VALUE : Double.MAX_VALUE;
1553 // Normal round-to-even rule: round up if the bit dropped is a one, and
1554 // the bit above it or any of the bits below it is a one.
1556 && ((m & 2) == 2 || remainder || checkBits(excess_bits)))
1559 // Check if we overflowed the mantissa
1560 if ((m & (1L << 54)) != 0)
1566 // Check if a denormalized mantissa was just rounded up to a
1568 else if (ml == 52 && (m & (1L << 53)) != 0)
1572 // Discard the rounding bit
1575 long bits_sign = neg ? (1L << 63) : 0;
1577 long bits_exp = (exp <= 0) ? 0 : ((long)exp) << 52;
1578 long bits_mant = m & ~(1L << 52);
1579 return Double.longBitsToDouble(bits_sign | bits_exp | bits_mant);
1582 /** Copy the abolute value of this into an array of words.
1583 * Assumes words.length >= (this.words == null ? 1 : this.ival).
1584 * Result is zero-extended, but need not be a valid 2's complement number.
1587 private void getAbsolute(int[] words)
1590 if (this.words == null)
1593 words[0] = this.ival;
1598 for (int i = len; --i >= 0; )
1599 words[i] = this.words[i];
1601 if (words[len - 1] < 0)
1602 negate(words, words, len);
1603 for (int i = words.length; --i > len; )
1607 /** Set dest[0:len-1] to the negation of src[0:len-1].
1608 * Return true if overflow (i.e. if src is -2**(32*len-1)).
1609 * Ok for src==dest. */
1610 private static boolean negate(int[] dest, int[] src, int len)
1613 boolean negative = src[len-1] < 0;
1614 for (int i = 0; i < len; i++)
1616 carry += ((long) (~src[i]) & 0xffffffffL);
1617 dest[i] = (int) carry;
1620 return (negative && dest[len-1] < 0);
1623 /** Destructively set this to the negative of x.
1624 * It is OK if x==this.*/
1625 private void setNegative(BigInteger x)
1628 if (x.words == null)
1630 if (len == Integer.MIN_VALUE)
1637 if (BigInteger.negate(words, x.words, len))
1642 /** Destructively negate this. */
1643 private final void setNegative()
1648 private static BigInteger abs(BigInteger x)
1650 return x.isNegative() ? neg(x) : x;
1653 public BigInteger abs()
1658 public static BigInteger neg(BigInteger x)
1660 if (x.words == null && x.ival != Integer.MIN_VALUE)
1661 return make(- x.ival);
1662 BigInteger result = new BigInteger(0);
1663 result.setNegative(x);
1664 return result.canonicalize();
1667 public BigInteger negate()
1669 return BigInteger.neg(this);
1672 /** Calculates ceiling(log2(this < 0 ? -this : this+1))
1673 * See Common Lisp: the Language, 2nd ed, p. 361.
1675 public int bitLength()
1678 return MPN.intLength(ival);
1680 return MPN.intLength(words, ival);
1683 public byte[] toByteArray()
1685 // Determine number of bytes needed. The method bitlength returns
1686 // the size without the sign bit, so add one bit for that and then
1687 // add 7 more to emulate the ceil function using integer math.
1688 byte[] bytes = new byte[(bitLength() + 1 + 7) / 8];
1689 int nbytes = bytes.length;
1694 // Deal with words array until one word or less is left to process.
1695 // If BigInteger is an int, then it is in ival and nbytes will be <= 4.
1698 word = words[wptr++];
1699 for (int i = 4; i > 0; --i, word >>= 8)
1700 bytes[--nbytes] = (byte) word;
1703 // Deal with the last few bytes. If BigInteger is an int, use ival.
1704 word = (words == null) ? ival : words[wptr];
1705 for ( ; nbytes > 0; word >>= 8)
1706 bytes[--nbytes] = (byte) word;
1711 /** Return the boolean opcode (for bitOp) for swapped operands.
1712 * I.e. bitOp(swappedOp(op), x, y) == bitOp(op, y, x).
1714 private static int swappedOp(int op)
1717 "\000\001\004\005\002\003\006\007\010\011\014\015\012\013\016\017"
1721 /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
1722 private static BigInteger bitOp(int op, BigInteger x, BigInteger y)
1726 case 0: return ZERO;
1727 case 1: return x.and(y);
1730 case 15: return smallFixNums[-1 - minFixNum]; // Returns -1.
1732 BigInteger result = new BigInteger();
1733 setBitOp(result, op, x, y);
1734 return result.canonicalize();
1737 /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
1738 private static void setBitOp(BigInteger result, int op,
1739 BigInteger x, BigInteger y)
1741 if (y.words == null) ;
1742 else if (x.words == null || x.ival < y.ival)
1744 BigInteger temp = x; x = y; y = temp;
1750 if (y.words == null)
1760 if (x.words == null)
1771 result.realloc(xlen);
1772 int[] w = result.words;
1774 // Code for how to handle the remainder of x.
1775 // 0: Truncate to length of y.
1776 // 1: Copy rest of x.
1777 // 2: Invert rest of x.
1789 if (i+1 >= ylen) break;
1790 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
1792 if (yi < 0) finish = 1;
1798 if (i+1 >= ylen) break;
1799 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
1801 if (yi >= 0) finish = 1;
1805 finish = 1; // Copy rest
1811 if (i+1 >= ylen) break;
1812 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
1814 if (yi < 0) finish = 2;
1820 if (i+1 >= ylen) break;
1821 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
1828 if (i+1 >= ylen) break;
1829 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
1831 finish = yi < 0 ? 2 : 1;
1837 if (i+1 >= ylen) break;
1838 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
1840 if (yi >= 0) finish = 1;
1846 if (i+1 >= ylen) break;
1847 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
1849 if (yi >= 0) finish = 2;
1851 case 9: // eqv [exclusive nor]
1855 if (i+1 >= ylen) break;
1856 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
1858 finish = yi >= 0 ? 2 : 1;
1864 if (i+1 >= ylen) break;
1865 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
1872 if (i+1 >= ylen) break;
1873 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
1875 if (yi < 0) finish = 1;
1885 if (i+1 >= ylen) break;
1886 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
1888 if (yi >= 0) finish = 2;
1894 if (i+1 >= ylen) break;
1895 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
1897 if (yi < 0) finish = 2;
1904 // Here i==ylen-1; w[0]..w[i-1] have the correct result;
1905 // and ni contains the correct result for w[i+1].
1911 if (i == 0 && w == null)
1918 case 1: w[i] = ni; while (++i < xlen) w[i] = x.words[i]; break;
1919 case 2: w[i] = ni; while (++i < xlen) w[i] = ~x.words[i]; break;
1924 /** Return the logical (bit-wise) "and" of a BigInteger and an int. */
1925 private static BigInteger and(BigInteger x, int y)
1927 if (x.words == null)
1928 return BigInteger.make(x.ival & y);
1930 return BigInteger.make(x.words[0] & y);
1932 int[] words = new int[len];
1933 words[0] = x.words[0] & y;
1935 words[len] = x.words[len];
1936 return BigInteger.make(words, x.ival);
1939 /** Return the logical (bit-wise) "and" of two BigIntegers. */
1940 public BigInteger and(BigInteger y)
1942 if (y.words == null)
1943 return and(this, y.ival);
1944 else if (words == null)
1945 return and(y, ival);
1947 BigInteger x = this;
1950 BigInteger temp = this; x = y; y = temp;
1953 int len = y.isNegative() ? x.ival : y.ival;
1954 int[] words = new int[len];
1955 for (i = 0; i < y.ival; i++)
1956 words[i] = x.words[i] & y.words[i];
1957 for ( ; i < len; i++)
1958 words[i] = x.words[i];
1959 return BigInteger.make(words, len);
1962 /** Return the logical (bit-wise) "(inclusive) or" of two BigIntegers. */
1963 public BigInteger or(BigInteger y)
1965 return bitOp(7, this, y);
1968 /** Return the logical (bit-wise) "exclusive or" of two BigIntegers. */
1969 public BigInteger xor(BigInteger y)
1971 return bitOp(6, this, y);
1974 /** Return the logical (bit-wise) negation of a BigInteger. */
1975 public BigInteger not()
1977 return bitOp(12, this, ZERO);
1980 public BigInteger andNot(BigInteger val)
1982 return and(val.not());
1985 public BigInteger clearBit(int n)
1988 throw new ArithmeticException();
1990 return and(ONE.shiftLeft(n).not());
1993 public BigInteger setBit(int n)
1996 throw new ArithmeticException();
1998 return or(ONE.shiftLeft(n));
2001 // bit4count[I] is number of '1' bits in I.
2002 private static final byte[] bit4_count = { 0, 1, 1, 2, 1, 2, 2, 3,
2003 1, 2, 2, 3, 2, 3, 3, 4};
2005 private static int bitCount(int i)
2010 count += bit4_count[i & 15];
2016 private static int bitCount(int[] x, int len)
2020 count += bitCount(x[len]);
2024 /** Count one bits in a BigInteger.
2025 * If argument is negative, count zero bits instead. */
2026 public int bitCount()
2029 int[] x_words = words;
2030 if (x_words == null)
2038 i = bitCount(x_words, x_len);
2040 return isNegative() ? x_len * 32 - i : i;
2045 public BigInteger(int bitLength, int certainty, Random rnd)
2047 public boolean testBit(int n)
2049 public BigInteger flipBit(int n)
2051 public int getLowestSetBit()
2053 public boolean isProbablePrime(int certainty)
2055 public BigInteger min(BigInteger val)
2057 public BigInteger max(BigInteger val)