1 /* java.math.BigInteger -- Arbitary precision integers
2 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2005, 2006, 2007 Free Software Foundation, Inc.
4 This file is part of GNU Classpath.
6 GNU Classpath is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 GNU Classpath is distributed in the hope that it will be useful, but
12 WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with GNU Classpath; see the file COPYING. If not, write to the
18 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21 Linking this library statically or dynamically with other modules is
22 making a combined work based on this library. Thus, the terms and
23 conditions of the GNU General Public License cover the whole
26 As a special exception, the copyright holders of this library give you
27 permission to link this library with independent modules to produce an
28 executable, regardless of the license terms of these independent
29 modules, and to copy and distribute the resulting executable under
30 terms of your choice, provided that you also meet, for each linked
31 independent module, the terms and conditions of the license of that
32 module. An independent module is a module which is not derived from
33 or based on this library. If you modify this library, you may extend
34 this exception to your version of the library, but you are not
35 obligated to do so. If you do not wish to do so, delete this
36 exception statement from your version. */
41 /*import gnu.classpath.Configuration;
43 import gnu.java.lang.CPStringBuilder;
44 import gnu.java.math.GMP;
45 import gnu.java.math.MPN;
47 import java.io.IOException;
48 import java.io.ObjectInputStream;
49 import java.io.ObjectOutputStream;
50 import java.util.Random;
51 import java.util.logging.Logger;
54 * Written using on-line Java Platform 1.2 API Specification, as well
55 * as "The Java Class Libraries", 2nd edition (Addison-Wesley, 1998) and
56 * "Applied Cryptography, Second Edition" by Bruce Schneier (Wiley, 1996).
58 * Based primarily on IntNum.java BitOps.java by Per Bothner (per@bothner.com)
59 * (found in Kawa 1.6.62).
61 * @author Warren Levy (warrenl@cygnus.com)
62 * @date December 20, 1999.
63 * @status believed complete and correct.
65 public class BigInteger //extends Number implements Comparable<BigInteger>
67 //private static final Logger log = Logger.getLogger(BigInteger.class.getName());
69 /** All integers are stored in 2's-complement form.
70 * If words == null, the ival is the value of this BigInteger.
71 * Otherwise, the first ival elements of words make the value
72 * of this BigInteger, stored in little-endian order, 2's-complement form. */
73 private transient int ival;
74 private transient int[] words;
76 // Serialization fields.
77 // the first three, although not used in the code, are present for
78 // compatibility with older RI versions of this class. DO NOT REMOVE.
79 private int bitCount = -1;
80 private int bitLength = -1;
81 private int lowestSetBit = -2;
82 private byte[] magnitude;
84 private static final long serialVersionUID = -8287574255936472291L;
87 /** We pre-allocate integers in the range minFixNum..maxFixNum.
88 * Note that we must at least preallocate 0, 1, and 10. */
89 private static final int minFixNum = -100;
90 private static final int maxFixNum = 1024;
91 private static final int numFixNum = maxFixNum-minFixNum+1;
92 private static final BigInteger[] smallFixNums;
94 /** The alter-ego GMP instance for this. */
95 //private transient GMP mpz;
97 /*private static final boolean USING_NATIVE = Configuration.WANT_NATIVE_BIG_INTEGER
98 && initializeLibrary();*/
111 smallFixNums = new BigInteger[numFixNum];
112 for (int i = numFixNum; --i >= 0; )
113 smallFixNums[i] = new BigInteger(i + minFixNum);
115 ZERO = smallFixNums[-minFixNum];
116 ONE = smallFixNums[1 - minFixNum];
117 TEN = smallFixNums[10 - minFixNum];
122 * The constant zero as a BigInteger.
125 public static final BigInteger ZERO;
128 * The constant one as a BigInteger.
131 public static final BigInteger ONE;
134 * The constant ten as a BigInteger.
137 public static final BigInteger TEN;
139 /* Rounding modes: */
140 private static final int FLOOR = 1;
141 private static final int CEILING = 2;
142 private static final int TRUNCATE = 3;
143 private static final int ROUND = 4;
145 /** When checking the probability of primes, it is most efficient to
146 * first check the factoring of small primes, so we'll use this array.
148 private static final int[] primes =
149 { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
150 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
151 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181,
152 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251 };
154 /** HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Table 4.4. */
155 private static final int[] k =
156 {100,150,200,250,300,350,400,500,600,800,1250, Integer.MAX_VALUE};
157 private static final int[] t =
158 { 27, 18, 15, 12, 9, 8, 7, 6, 5, 4, 3, 2};
168 /* Create a new (non-shared) BigInteger, and initialize to an int. */
169 private BigInteger(int value)
176 public BigInteger(String s, int radix)
180 int len = s.length();
184 char ch = s.charAt(0);
189 bytes = new byte[len - 1];
195 bytes = new byte[len];
198 for ( ; i < len; i++)
201 digit = Character.digit(ch, radix);
203 throw new Error/*NumberFormatException*/("Invalid character at position #" + i);
204 bytes[byte_len++] = (byte) digit;
210 if (mpz.fromString(s, radix) != 0)
211 throw new NumberFormatException("String \"" + s
212 + "\" is NOT a valid number in base "
218 // Testing (len < MPN.chars_per_word(radix)) would be more accurate,
219 // but slightly more expensive, for little practical gain.
220 if (len <= 15 && radix <= 16)
221 result = valueOf(Long.parseLong(s, radix));
223 result = valueOf(bytes, byte_len, negative, radix);
225 this.ival = result.ival;
226 this.words = result.words;
230 public BigInteger(String val)
235 /* Create a new (non-shared) BigInteger, and initialize from a byte array. */
236 public BigInteger(byte[] val)
240 if (val == null || val.length < 1)
241 throw new Error("Number Format Exception")/*NumberFormatException()*/;
244 mpz.fromByteArray(val);
247 words = byteArrayToIntArray(val, val[0] < 0 ? -1 : 0);
248 BigInteger result = make(words, words.length);
249 this.ival = result.ival;
250 this.words = result.words;
254 public BigInteger(int signum, byte[] magnitude)
258 if (magnitude == null || signum > 1 || signum < -1)
259 throw new Error("Number Format Exception")/*NumberFormatException()*/;
264 for (i = magnitude.length - 1; i >= 0 && magnitude[i] == 0; --i)
267 throw new Error("Number Format Exception")/*NumberFormatException()*/;
272 mpz.fromSignedMagnitude(magnitude, signum == -1);
275 // Magnitude is always positive, so don't ever pass a sign of -1.
276 words = byteArrayToIntArray(magnitude, 0);
277 BigInteger result = make(words, words.length);
278 this.ival = result.ival;
279 this.words = result.words;
286 public BigInteger(int numBits, Random rnd)
291 throw new Error("Illegal Argument Exception")/*IllegalArgumentException()*/;
296 private void init(int numBits, Random rnd)
300 int length = (numBits + 7) / 8;
301 byte[] magnitude = new byte[length];
302 rnd.nextBytes(magnitude);
303 int discardedBitCount = numBits % 8;
304 if (discardedBitCount != 0)
306 discardedBitCount = 8 - discardedBitCount;
307 magnitude[0] = (byte)((magnitude[0] & 0xFF) >>> discardedBitCount);
309 mpz.fromSignedMagnitude(magnitude, false);
314 int highbits = numBits & 31;
315 // minimum number of bytes to store the above number of bits
316 int highBitByteCount = (highbits + 7) / 8;
317 // number of bits to discard from the last byte
318 int discardedBitCount = highbits % 8;
319 if (discardedBitCount != 0)
320 discardedBitCount = 8 - discardedBitCount;
321 byte[] highBitBytes = new byte[highBitByteCount];
324 rnd.nextBytes(highBitBytes);
325 highbits = (highBitBytes[highBitByteCount - 1] & 0xFF) >>> discardedBitCount;
326 for (int i = highBitByteCount - 2; i >= 0; i--)
327 highbits = (highbits << 8) | (highBitBytes[i] & 0xFF);
329 int nwords = numBits / 32;
331 while (highbits == 0 && nwords > 0)
333 highbits = rnd.nextInt();
336 if (nwords == 0 && highbits >= 0)
342 ival = highbits < 0 ? nwords + 2 : nwords + 1;
343 words = new int[ival];
344 words[nwords] = highbits;
345 while (--nwords >= 0)
346 words[nwords] = rnd.nextInt();
350 public BigInteger(int bitLength, int certainty, Random rnd)
354 BigInteger result = new BigInteger();
357 result.init(bitLength, rnd);
358 result = result.setBit(bitLength - 1);
359 if (result.isProbablePrime(certainty))
364 mpz.fromBI(result.mpz);
367 this.ival = result.ival;
368 this.words = result.words;
373 * Return a BigInteger that is bitLength bits long with a
374 * probability < 2^-100 of being composite.
376 * @param bitLength length in bits of resulting number
377 * @param rnd random number generator to use
378 * @throws ArithmeticException if bitLength < 2
381 public static BigInteger probablePrime(int bitLength, Random rnd)
384 throw new Error("Arithmetic Exception")/*ArithmeticException()*/;
386 return new BigInteger(bitLength, 100, rnd);
389 /** Return a (possibly-shared) BigInteger with a given long value. */
390 public static BigInteger valueOf(long val)
394 BigInteger result = new BigInteger();
395 result.mpz.fromLong(val);
399 if (val >= minFixNum && val <= maxFixNum)
400 return smallFixNums[(int) val - minFixNum];
403 return new BigInteger(i);
404 BigInteger result = alloc(2);
407 result.words[1] = (int)(val >> 32);
412 * @return <code>true</code> if the GMP-based native implementation library
413 * was successfully loaded. Returns <code>false</code> otherwise.
415 /*private static boolean initializeLibrary()
420 System.loadLibrary("javamath");
421 GMP.natInitializeLibrary();
427 if (Configuration.DEBUG)
429 log.info("Unable to use native BigInteger: " + x);
430 log.info("Will use a pure Java implementation instead");
436 /** Make a canonicalized BigInteger from an array of words.
437 * The array may be reused (without copying). */
438 private static BigInteger make(int[] words, int len)
442 len = BigInteger.wordsNeeded(words, len);
444 return len == 0 ? ZERO : valueOf(words[0]);
445 BigInteger num = new BigInteger();
451 /** Convert a big-endian byte array to a little-endian array of words. */
452 private static int[] byteArrayToIntArray(byte[] bytes, int sign)
454 // Determine number of words needed.
455 int[] words = new int[bytes.length/4 + 1];
456 int nwords = words.length;
458 // Create a int out of modulo 4 high order bytes.
461 for (int i = bytes.length % 4; i > 0; --i, bptr++)
462 word = (word << 8) | (bytes[bptr] & 0xff);
463 words[--nwords] = word;
465 // Elements remaining in byte[] are a multiple of 4.
467 words[--nwords] = bytes[bptr++] << 24 |
468 (bytes[bptr++] & 0xff) << 16 |
469 (bytes[bptr++] & 0xff) << 8 |
470 (bytes[bptr++] & 0xff);
474 /** Allocate a new non-shared BigInteger.
475 * @param nwords number of words to allocate
477 private static BigInteger alloc(int nwords)
479 BigInteger result = new BigInteger();
481 result.words = new int[nwords];
485 /** Change words.length to nwords.
486 * We allow words.length to be upto nwords+2 without reallocating.
488 private void realloc(int nwords)
499 else if (words == null
500 || words.length < nwords
501 || words.length > nwords + 2)
503 int[] new_words = new int [nwords];
513 System.arraycopy(words, 0, new_words, 0, ival);
519 private boolean isNegative()
521 return (words == null ? ival : words[ival - 1]) < 0;
527 return mpz.compare(ZERO.mpz);*/
529 if (ival == 0 && words == null)
531 int top = words == null ? ival : words[ival-1];
532 return top < 0 ? -1 : 1;
535 private static int compareTo(BigInteger x, BigInteger y)
539 int dummy = y.signum; // force NPE check
540 return x.mpz.compare(y.mpz);
543 if (x.words == null && y.words == null)
544 return x.ival < y.ival ? -1 : x.ival > y.ival ? 1 : 0;
545 boolean x_negative = x.isNegative();
546 boolean y_negative = y.isNegative();
547 if (x_negative != y_negative)
548 return x_negative ? -1 : 1;
549 int x_len = x.words == null ? 1 : x.ival;
550 int y_len = y.words == null ? 1 : y.ival;
552 return (x_len > y_len) != x_negative ? 1 : -1;
553 return MPN.cmp(x.words, y.words, x_len);
557 public int compareTo(BigInteger val)
559 return compareTo(this, val);
562 public BigInteger min(BigInteger val)
564 return compareTo(this, val) < 0 ? this : val;
567 public BigInteger max(BigInteger val)
569 return compareTo(this, val) > 0 ? this : val;
572 private boolean isZero()
574 return words == null && ival == 0;
577 private boolean isOne()
579 return words == null && ival == 1;
582 /** Calculate how many words are significant in words[0:len-1].
583 * Returns the least value x such that x>0 && words[0:x-1]==words[0:len-1],
584 * when words is viewed as a 2's complement integer.
586 private static int wordsNeeded(int[] words, int len)
591 int word = words[--i];
594 while (i > 0 && (word = words[i - 1]) < 0)
597 if (word != -1) break;
602 while (word == 0 && i > 0 && (word = words[i - 1]) >= 0) i--;
608 private BigInteger canonicalize()
611 && (ival = BigInteger.wordsNeeded(words, ival)) <= 1)
617 if (words == null && ival >= minFixNum && ival <= maxFixNum)
618 return smallFixNums[ival - minFixNum];
622 /** Add two ints, yielding a BigInteger. */
623 private static BigInteger add(int x, int y)
625 return valueOf((long) x + (long) y);
628 /** Add a BigInteger and an int, yielding a new BigInteger. */
629 private static BigInteger add(BigInteger x, int y)
632 return BigInteger.add(x.ival, y);
633 BigInteger result = new BigInteger(0);
635 return result.canonicalize();
638 /** Set this to the sum of x and y.
640 private void setAdd(BigInteger x, int y)
644 set((long) x.ival + (long) y);
650 for (int i = 0; i < len; i++)
652 carry += ((long) x.words[i] & 0xffffffffL);
653 words[i] = (int) carry;
656 if (x.words[len - 1] < 0)
658 words[len] = (int) carry;
659 ival = wordsNeeded(words, len + 1);
662 /** Destructively add an int to this. */
663 private void setAdd(int y)
668 /** Destructively set the value of this to a long. */
669 private void set(long y)
681 words[1] = (int) (y >> 32);
686 /** Destructively set the value of this to the given words.
687 * The words array is reused, not copied. */
688 private void set(int[] words, int length)
694 /** Destructively set the value of this to that of y. */
695 private void set(BigInteger y)
702 System.arraycopy(y.words, 0, words, 0, y.ival);
707 /** Add two BigIntegers, yielding their sum as another BigInteger. */
708 private static BigInteger add(BigInteger x, BigInteger y, int k)
710 if (x.words == null && y.words == null)
711 return valueOf((long) k * (long) y.ival + (long) x.ival);
715 y = BigInteger.neg(y);
717 y = BigInteger.times(y, valueOf(k));
720 return BigInteger.add(y, x.ival);
722 return BigInteger.add(x, y.ival);
725 { // Swap so x is longer then y.
726 BigInteger tmp = x; x = y; y = tmp;
728 BigInteger result = alloc(x.ival + 1);
730 long carry = MPN.add_n(result.words, x.words, y.words, i);
731 long y_ext = y.words[i - 1] < 0 ? 0xffffffffL : 0;
732 for (; i < x.ival; i++)
734 carry += ((long) x.words[i] & 0xffffffffL) + y_ext;
735 result.words[i] = (int) carry;
738 if (x.words[i - 1] < 0)
740 result.words[i] = (int) (carry + y_ext);
742 return result.canonicalize();
745 public BigInteger add(BigInteger val)
749 int dummy = val.signum; // force NPE check
750 BigInteger result = new BigInteger();
751 mpz.add(val.mpz, result.mpz);
755 return add(this, val, 1);
758 public BigInteger subtract(BigInteger val)
762 int dummy = val.signum; // force NPE check
763 BigInteger result = new BigInteger();
764 mpz.subtract(val.mpz, result.mpz);
768 return add(this, val, -1);
771 private static BigInteger times(BigInteger x, int y)
777 int[] xwords = x.words;
780 return valueOf((long) xlen * (long) y);
782 BigInteger result = BigInteger.alloc(xlen + 1);
783 if (xwords[xlen - 1] < 0)
786 negate(result.words, xwords, xlen);
787 xwords = result.words;
793 negative = !negative;
796 result.words[xlen] = MPN.mul_1(result.words, xwords, xlen, y);
797 result.ival = xlen + 1;
799 result.setNegative();
800 return result.canonicalize();
803 private static BigInteger times(BigInteger x, BigInteger y)
806 return times(x, y.ival);
808 return times(y, x.ival);
809 boolean negative = false;
817 xwords = new int[xlen];
818 negate(xwords, x.words, xlen);
827 negative = !negative;
828 ywords = new int[ylen];
829 negate(ywords, y.words, ylen);
833 // Swap if x is shorter then y.
836 int[] twords = xwords; xwords = ywords; ywords = twords;
837 int tlen = xlen; xlen = ylen; ylen = tlen;
839 BigInteger result = BigInteger.alloc(xlen+ylen);
840 MPN.mul(result.words, xwords, xlen, ywords, ylen);
841 result.ival = xlen+ylen;
843 result.setNegative();
844 return result.canonicalize();
847 public BigInteger multiply(BigInteger y)
851 int dummy = y.signum; // force NPE check
852 BigInteger result = new BigInteger();
853 mpz.multiply(y.mpz, result.mpz);
857 return times(this, y);
860 private static void divide(long x, long y,
861 BigInteger quotient, BigInteger remainder,
864 boolean xNegative, yNegative;
868 if (x == Long.MIN_VALUE)
870 divide(valueOf(x), valueOf(y),
871 quotient, remainder, rounding_mode);
882 if (y == Long.MIN_VALUE)
884 if (rounding_mode == TRUNCATE)
885 { // x != Long.Min_VALUE implies abs(x) < abs(y)
886 if (quotient != null)
888 if (remainder != null)
892 divide(valueOf(x), valueOf(y),
893 quotient, remainder, rounding_mode);
903 boolean qNegative = xNegative ^ yNegative;
905 boolean add_one = false;
908 switch (rounding_mode)
914 if (qNegative == (rounding_mode == FLOOR))
918 add_one = r > ((y - (q & 1)) >> 1);
922 if (quotient != null)
930 if (remainder != null)
932 // The remainder is by definition: X-Q*Y
935 // Subtract the remainder from Y.
937 // In this case, abs(Q*Y) > abs(X).
938 // So sign(remainder) = -sign(X).
939 xNegative = ! xNegative;
943 // If !add_one, then: abs(Q*Y) <= abs(X).
944 // So sign(remainder) = sign(X).
952 /** Divide two integers, yielding quotient and remainder.
953 * @param x the numerator in the division
954 * @param y the denominator in the division
955 * @param quotient is set to the quotient of the result (iff quotient!=null)
956 * @param remainder is set to the remainder of the result
957 * (iff remainder!=null)
958 * @param rounding_mode one of FLOOR, CEILING, TRUNCATE, or ROUND.
960 private static void divide(BigInteger x, BigInteger y,
961 BigInteger quotient, BigInteger remainder,
964 if ((x.words == null || x.ival <= 2)
965 && (y.words == null || y.ival <= 2))
967 long x_l = x.longValue();
968 long y_l = y.longValue();
969 if (x_l != Long.MIN_VALUE && y_l != Long.MIN_VALUE)
971 divide(x_l, y_l, quotient, remainder, rounding_mode);
976 boolean xNegative = x.isNegative();
977 boolean yNegative = y.isNegative();
978 boolean qNegative = xNegative ^ yNegative;
980 int ylen = y.words == null ? 1 : y.ival;
981 int[] ywords = new int[ylen];
982 y.getAbsolute(ywords);
983 while (ylen > 1 && ywords[ylen - 1] == 0) ylen--;
985 int xlen = x.words == null ? 1 : x.ival;
986 int[] xwords = new int[xlen+2];
987 x.getAbsolute(xwords);
988 while (xlen > 1 && xwords[xlen-1] == 0) xlen--;
992 int cmpval = MPN.cmp(xwords, xlen, ywords, ylen);
993 if (cmpval < 0) // abs(x) < abs(y)
994 { // quotient = 0; remainder = num.
995 int[] rwords = xwords; xwords = ywords; ywords = rwords;
996 rlen = xlen; qlen = 1; xwords[0] = 0;
998 else if (cmpval == 0) // abs(x) == abs(y)
1000 xwords[0] = 1; qlen = 1; // quotient = 1
1001 ywords[0] = 0; rlen = 1; // remainder = 0;
1006 // Need to leave room for a word of leading zeros if dividing by 1
1007 // and the dividend has the high bit set. It might be safe to
1008 // increment qlen in all cases, but it certainly is only necessary
1009 // in the following case.
1010 if (ywords[0] == 1 && xwords[xlen-1] < 0)
1013 ywords[0] = MPN.divmod_1(xwords, xwords, xlen, ywords[0]);
1015 else // abs(x) > abs(y)
1017 // Normalize the denominator, i.e. make its most significant bit set by
1018 // shifting it normalization_steps bits to the left. Also shift the
1019 // numerator the same number of steps (to keep the quotient the same!).
1021 int nshift = MPN.count_leading_zeros(ywords[ylen - 1]);
1024 // Shift up the denominator setting the most significant bit of
1025 // the most significant word.
1026 MPN.lshift(ywords, 0, ywords, ylen, nshift);
1028 // Shift up the numerator, possibly introducing a new most
1029 // significant word.
1030 int x_high = MPN.lshift(xwords, 0, xwords, xlen, nshift);
1031 xwords[xlen++] = x_high;
1036 MPN.divide(xwords, xlen, ywords, ylen);
1038 MPN.rshift0 (ywords, xwords, 0, rlen, nshift);
1040 qlen = xlen + 1 - ylen;
1041 if (quotient != null)
1043 for (int i = 0; i < qlen; i++)
1044 xwords[i] = xwords[i+ylen];
1048 if (ywords[rlen-1] < 0)
1054 // Now the quotient is in xwords, and the remainder is in ywords.
1056 boolean add_one = false;
1057 if (rlen > 1 || ywords[0] != 0)
1058 { // Non-zero remainder i.e. in-exact quotient.
1059 switch (rounding_mode)
1065 if (qNegative == (rounding_mode == FLOOR))
1069 // int cmp = compareTo(remainder<<1, abs(y));
1070 BigInteger tmp = remainder == null ? new BigInteger() : remainder;
1071 tmp.set(ywords, rlen);
1072 tmp = shift(tmp, 1);
1075 int cmp = compareTo(tmp, y);
1076 // Now cmp == compareTo(sign(y)*(remainder<<1), y)
1079 add_one = (cmp == 1) || (cmp == 0 && (xwords[0]&1) != 0);
1082 if (quotient != null)
1084 quotient.set(xwords, qlen);
1087 if (add_one) // -(quotient + 1) == ~(quotient)
1088 quotient.setInvert();
1090 quotient.setNegative();
1095 if (remainder != null)
1097 // The remainder is by definition: X-Q*Y
1098 remainder.set(ywords, rlen);
1101 // Subtract the remainder from Y:
1102 // abs(R) = abs(Y) - abs(orig_rem) = -(abs(orig_rem) - abs(Y)).
1104 if (y.words == null)
1107 tmp.set(yNegative ? ywords[0] + y.ival : ywords[0] - y.ival);
1110 tmp = BigInteger.add(remainder, y, yNegative ? 1 : -1);
1112 // In this case, abs(Q) = 1 + floor(abs(X)/abs(Y)).
1113 // Hence, abs(Q*Y) > abs(X).
1114 // So sign(remainder) = -sign(X).
1116 remainder.setNegative(tmp);
1122 // If !add_one, then: abs(Q*Y) <= abs(X).
1123 // So sign(remainder) = sign(X).
1125 remainder.setNegative();
1130 public BigInteger divide(BigInteger val)
1134 if (val.compareTo(ZERO) == 0)
1135 throw new ArithmeticException("divisor is zero");
1137 BigInteger result = new BigInteger();
1138 mpz.quotient(val.mpz, result.mpz);
1143 throw new Error/*ArithmeticException*/("divisor is zero");
1145 BigInteger quot = new BigInteger();
1146 divide(this, val, quot, null, TRUNCATE);
1147 return quot.canonicalize();
1150 public BigInteger remainder(BigInteger val)
1154 if (val.compareTo(ZERO) == 0)
1155 throw new ArithmeticException("divisor is zero");
1157 BigInteger result = new BigInteger();
1158 mpz.remainder(val.mpz, result.mpz);
1163 throw new Error/*ArithmeticException*/("divisor is zero");
1165 BigInteger rem = new BigInteger();
1166 divide(this, val, null, rem, TRUNCATE);
1167 return rem.canonicalize();
1170 public BigInteger[] divideAndRemainder(BigInteger val)
1174 if (val.compareTo(ZERO) == 0)
1175 throw new ArithmeticException("divisor is zero");
1177 BigInteger q = new BigInteger();
1178 BigInteger r = new BigInteger();
1179 mpz.quotientAndRemainder(val.mpz, q.mpz, r.mpz);
1180 return new BigInteger[] { q, r };
1184 throw new Error/*ArithmeticException*/("divisor is zero");
1186 BigInteger[] result = new BigInteger[2];
1187 result[0] = new BigInteger();
1188 result[1] = new BigInteger();
1189 divide(this, val, result[0], result[1], TRUNCATE);
1190 result[0].canonicalize();
1191 result[1].canonicalize();
1195 public BigInteger mod(BigInteger m)
1199 int dummy = m.signum; // force NPE check
1200 if (m.compareTo(ZERO) < 1)
1201 throw new ArithmeticException("non-positive modulus");
1203 BigInteger result = new BigInteger();
1204 mpz.modulo(m.mpz, result.mpz);
1208 if (m.isNegative() || m.isZero())
1209 throw new Error/*ArithmeticException*/("non-positive modulus");
1211 BigInteger rem = new BigInteger();
1212 divide(this, m, null, rem, FLOOR);
1213 return rem.canonicalize();
1216 /** Calculate the integral power of a BigInteger.
1217 * @param exponent the exponent (must be non-negative)
1219 public BigInteger pow(int exponent)
1225 throw new Error/*ArithmeticException*/("negative exponent");
1230 BigInteger result = new BigInteger();
1231 mpz.pow(exponent, result.mpz);
1237 int plen = words == null ? 1 : ival; // Length of pow2.
1238 int blen = ((bitLength() * exponent) >> 5) + 2 * plen;
1239 boolean negative = isNegative() && (exponent & 1) != 0;
1240 int[] pow2 = new int [blen];
1241 int[] rwords = new int [blen];
1242 int[] work = new int [blen];
1243 getAbsolute(pow2); // pow2 = abs(this);
1245 rwords[0] = 1; // rwords = 1;
1246 for (;;) // for (i = 0; ; i++)
1248 // pow2 == this**(2**i)
1249 // prod = this**(sum(j=0..i-1, (exponent>>j)&1))
1250 if ((exponent & 1) != 0)
1252 MPN.mul(work, pow2, plen, rwords, rlen);
1253 int[] temp = work; work = rwords; rwords = temp;
1255 while (rwords[rlen - 1] == 0) rlen--;
1261 MPN.mul(work, pow2, plen, pow2, plen);
1262 int[] temp = work; work = pow2; pow2 = temp; // swap to avoid a copy
1264 while (pow2[plen - 1] == 0) plen--;
1266 if (rwords[rlen - 1] < 0)
1269 negate(rwords, rwords, rlen);
1270 return BigInteger.make(rwords, rlen);
1273 private static int[] euclidInv(int a, int b, int prevDiv)
1276 throw new Error/*ArithmeticException*/("not invertible");
1279 // Success: values are indeed invertible!
1280 // Bottom of the recursion reached; start unwinding.
1281 return new int[] { -prevDiv, 1 };
1283 int[] xy = euclidInv(b, a % b, a / b); // Recursion happens here.
1284 a = xy[0]; // use our local copy of 'a' as a work var
1285 xy[0] = a * -prevDiv + xy[1];
1290 private static void euclidInv(BigInteger a, BigInteger b,
1291 BigInteger prevDiv, BigInteger[] xy)
1294 throw new Error/*ArithmeticException*/("not invertible");
1298 // Success: values are indeed invertible!
1299 // Bottom of the recursion reached; start unwinding.
1300 xy[0] = neg(prevDiv);
1305 // Recursion happens in the following conditional!
1307 // If a just contains an int, then use integer math for the rest.
1308 if (a.words == null)
1310 int[] xyInt = euclidInv(b.ival, a.ival % b.ival, a.ival / b.ival);
1311 xy[0] = new BigInteger(xyInt[0]);
1312 xy[1] = new BigInteger(xyInt[1]);
1316 BigInteger rem = new BigInteger();
1317 BigInteger quot = new BigInteger();
1318 divide(a, b, quot, rem, FLOOR);
1319 // quot and rem may not be in canonical form. ensure
1321 quot.canonicalize();
1322 euclidInv(b, rem, quot, xy);
1325 BigInteger t = xy[0];
1326 xy[0] = add(xy[1], times(t, prevDiv), -1);
1330 public BigInteger modInverse(BigInteger y)
1334 int dummy = y.signum; // force NPE check
1335 if (mpz.compare(ZERO.mpz) < 1)
1336 throw new ArithmeticException("non-positive modulo");
1338 BigInteger result = new BigInteger();
1339 mpz.modInverse(y.mpz, result.mpz);
1343 if (y.isNegative() || y.isZero())
1344 throw new Error/*ArithmeticException*/("non-positive modulo");
1346 // Degenerate cases.
1352 // Use Euclid's algorithm as in gcd() but do this recursively
1353 // rather than in a loop so we can use the intermediate results as we
1354 // unwind from the recursion.
1355 // Used http://www.math.nmsu.edu/~crypto/EuclideanAlgo.html as reference.
1356 BigInteger result = new BigInteger();
1357 boolean swapped = false;
1359 if (y.words == null)
1361 // The result is guaranteed to be less than the modulus, y (which is
1362 // an int), so simplify this by working with the int result of this
1363 // modulo y. Also, if this is negative, make it positive via modulo
1364 // math. Note that BigInteger.mod() must be used even if this is
1365 // already an int as the % operator would provide a negative result if
1366 // this is negative, BigInteger.mod() never returns negative values.
1367 int xval = (words != null || isNegative()) ? mod(y).ival : ival;
1370 // Swap values so x > y.
1373 int tmp = xval; xval = yval; yval = tmp;
1376 // Normally, the result is in the 2nd element of the array, but
1377 // if originally x < y, then x and y were swapped and the result
1378 // is in the 1st element of the array.
1380 euclidInv(yval, xval % yval, xval / yval)[swapped ? 0 : 1];
1382 // Result can't be negative, so make it positive by adding the
1383 // original modulus, y.ival (not the possibly "swapped" yval).
1384 if (result.ival < 0)
1385 result.ival += y.ival;
1389 // As above, force this to be a positive value via modulo math.
1390 BigInteger x = isNegative() ? this.mod(y) : this;
1392 // Swap values so x > y.
1393 if (x.compareTo(y) < 0)
1395 result = x; x = y; y = result; // use 'result' as a work var
1398 // As above (for ints), result will be in the 2nd element unless
1399 // the original x and y were swapped.
1400 BigInteger rem = new BigInteger();
1401 BigInteger quot = new BigInteger();
1402 divide(x, y, quot, rem, FLOOR);
1403 // quot and rem may not be in canonical form. ensure
1405 quot.canonicalize();
1406 BigInteger[] xy = new BigInteger[2];
1407 euclidInv(y, rem, quot, xy);
1408 result = swapped ? xy[0] : xy[1];
1410 // Result can't be negative, so make it positive by adding the
1411 // original modulus, y (which is now x if they were swapped).
1412 if (result.isNegative())
1413 result = add(result, swapped ? x : y, 1);
1419 public BigInteger modPow(BigInteger exponent, BigInteger m)
1423 int dummy = exponent.signum; // force NPE check
1424 if (m.mpz.compare(ZERO.mpz) < 1)
1425 throw new ArithmeticException("non-positive modulo");
1427 BigInteger result = new BigInteger();
1428 mpz.modPow(exponent.mpz, m.mpz, result.mpz);
1432 if (m.isNegative() || m.isZero())
1433 throw new Error/*ArithmeticException*/("non-positive modulo");
1435 if (exponent.isNegative())
1436 return modInverse(m).modPow(exponent.negate(), m);
1437 if (exponent.isOne())
1440 // To do this naively by first raising this to the power of exponent
1441 // and then performing modulo m would be extremely expensive, especially
1442 // for very large numbers. The solution is found in Number Theory
1443 // where a combination of partial powers and moduli can be done easily.
1445 // We'll use the algorithm for Additive Chaining which can be found on
1446 // p. 244 of "Applied Cryptography, Second Edition" by Bruce Schneier.
1448 BigInteger t = this;
1449 BigInteger u = exponent;
1453 if (u.and(ONE).isOne())
1454 s = times(s, t).mod(m);
1455 u = u.shiftRight(1);
1456 t = times(t, t).mod(m);
1462 /** Calculate Greatest Common Divisor for non-negative ints. */
1463 private static int gcd(int a, int b)
1465 // Euclid's algorithm, copied from libg++.
1469 tmp = a; a = b; b = tmp;
1483 public BigInteger gcd(BigInteger y)
1487 int dummy = y.signum; // force NPE check
1488 BigInteger result = new BigInteger();
1489 mpz.gcd(y.mpz, result.mpz);
1500 && xval != Integer.MIN_VALUE && yval != Integer.MIN_VALUE)
1506 return valueOf(gcd(xval, yval));
1510 if (y.words == null)
1516 int len = (xval > yval ? xval : yval) + 1;
1517 int[] xwords = new int[len];
1518 int[] ywords = new int[len];
1519 getAbsolute(xwords);
1520 y.getAbsolute(ywords);
1521 len = MPN.gcd(xwords, ywords, len);
1522 BigInteger result = new BigInteger(0);
1524 result.words = xwords;
1525 return result.canonicalize();
1529 * <p>Returns <code>true</code> if this BigInteger is probably prime,
1530 * <code>false</code> if it's definitely composite. If <code>certainty</code>
1531 * is <code><= 0</code>, <code>true</code> is returned.</p>
1533 * @param certainty a measure of the uncertainty that the caller is willing
1534 * to tolerate: if the call returns <code>true</code> the probability that
1535 * this BigInteger is prime exceeds <code>(1 - 1/2<sup>certainty</sup>)</code>.
1536 * The execution time of this method is proportional to the value of this
1538 * @return <code>true</code> if this BigInteger is probably prime,
1539 * <code>false</code> if it's definitely composite.
1541 public boolean isProbablePrime(int certainty)
1547 return mpz.testPrimality(certainty) != 0;*/
1549 /** We'll use the Rabin-Miller algorithm for doing a probabilistic
1550 * primality test. It is fast, easy and has faster decreasing odds of a
1551 * composite passing than with other tests. This means that this
1552 * method will actually have a probability much greater than the
1553 * 1 - .5^certainty specified in the JCL (p. 117), but I don't think
1554 * anyone will complain about better performance with greater certainty.
1556 * The Rabin-Miller algorithm can be found on pp. 259-261 of "Applied
1557 * Cryptography, Second Edition" by Bruce Schneier.
1560 // First rule out small prime factors
1561 BigInteger rem = new BigInteger();
1563 for (i = 0; i < primes.length; i++)
1565 if (words == null && ival == primes[i])
1568 divide(this, smallFixNums[primes[i] - minFixNum], null, rem, TRUNCATE);
1569 if (rem.canonicalize().isZero())
1573 // Now perform the Rabin-Miller test.
1575 // Set b to the number of times 2 evenly divides (this - 1).
1576 // I.e. 2^b is the largest power of 2 that divides (this - 1).
1577 BigInteger pMinus1 = add(this, -1);
1578 int b = pMinus1.getLowestSetBit();
1580 // Set m such that this = 1 + 2^b * m.
1581 BigInteger m = pMinus1.divide(valueOf(2L).pow(b));
1583 // The HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Note
1584 // 4.49 (controlling the error probability) gives the number of trials
1585 // for an error probability of 1/2**80, given the number of bits in the
1586 // number to test. we shall use these numbers as is if/when 'certainty'
1587 // is less or equal to 80, and twice as much if it's greater.
1588 int bits = this.bitLength();
1589 for (i = 0; i < k.length; i++)
1596 for (int t = 0; t < trials; t++)
1598 // The HAC (Handbook of Applied Cryptography), Alfred Menezes & al.
1599 // Remark 4.28 states: "...A strategy that is sometimes employed
1600 // is to fix the bases a to be the first few primes instead of
1601 // choosing them at random.
1602 z = smallFixNums[primes[t] - minFixNum].modPow(m, this);
1603 if (z.isOne() || z.equals(pMinus1))
1604 continue; // Passes the test; may be prime.
1606 for (i = 0; i < b; )
1611 if (z.equals(pMinus1))
1612 break; // Passes the test; may be prime.
1614 z = z.modPow(valueOf(2), this);
1617 if (i == b && !z.equals(pMinus1))
1623 private void setInvert()
1629 for (int i = ival; --i >= 0; )
1630 words[i] = ~words[i];
1634 private void setShiftLeft(BigInteger x, int count)
1638 if (x.words == null)
1642 set((long) x.ival << count);
1645 xwords = new int[1];
1654 int word_count = count >> 5;
1656 int new_len = xlen + word_count;
1660 for (int i = xlen; --i >= 0; )
1661 words[i+word_count] = xwords[i];
1667 int shift_out = MPN.lshift(words, word_count, xwords, xlen, count);
1669 words[new_len-1] = (shift_out << count) >> count; // sign-extend.
1672 for (int i = word_count; --i >= 0; )
1676 private void setShiftRight(BigInteger x, int count)
1678 if (x.words == null)
1679 set(count < 32 ? x.ival >> count : x.ival < 0 ? -1 : 0);
1680 else if (count == 0)
1684 boolean neg = x.isNegative();
1685 int word_count = count >> 5;
1687 int d_len = x.ival - word_count;
1692 if (words == null || words.length < d_len)
1694 MPN.rshift0 (words, x.words, word_count, d_len, count);
1697 words[d_len-1] |= -2 << (31 - count);
1702 private void setShift(BigInteger x, int count)
1705 setShiftLeft(x, count);
1707 setShiftRight(x, -count);
1710 private static BigInteger shift(BigInteger x, int count)
1712 if (x.words == null)
1715 return valueOf(count > -32 ? x.ival >> (-count) : x.ival < 0 ? -1 : 0);
1717 return valueOf((long) x.ival << count);
1721 BigInteger result = new BigInteger(0);
1722 result.setShift(x, count);
1723 return result.canonicalize();
1726 public BigInteger shiftLeft(int n)
1733 BigInteger result = new BigInteger();
1735 mpz.shiftRight(-n, result.mpz);
1737 mpz.shiftLeft(n, result.mpz);
1741 return shift(this, n);
1744 public BigInteger shiftRight(int n)
1751 BigInteger result = new BigInteger();
1753 mpz.shiftLeft(-n, result.mpz);
1755 mpz.shiftRight(n, result.mpz);
1759 return shift(this, -n);
1762 /*private void format(int radix, CPStringBuilder buffer)
1765 buffer.append(Integer.toString(ival, radix));
1767 buffer.append(Long.toString(longValue(), radix));
1770 boolean neg = isNegative();
1772 if (neg || radix != 16)
1774 work = new int[ival];
1785 int buf_start = buffer.length();
1786 for (int i = len; --i >= 0; )
1789 for (int j = 8; --j >= 0; )
1791 int hex_digit = (word >> (4 * j)) & 0xF;
1792 // Suppress leading zeros:
1793 if (hex_digit > 0 || buffer.length() > buf_start)
1794 buffer.append(Character.forDigit(hex_digit, 16));
1800 int i = buffer.length();
1803 int digit = MPN.divmod_1(work, work, len, radix);
1804 buffer.append(Character.forDigit(digit, radix));
1805 while (len > 0 && work[len-1] == 0) len--;
1812 int j = buffer.length() - 1;
1815 char tmp = buffer.charAt(i);
1816 buffer.setCharAt(i, buffer.charAt(j));
1817 buffer.setCharAt(j, tmp);
1824 /*public String toString()
1826 return toString(10);
1829 /*public String toString(int radix)
1832 return mpz.toString(radix);
1835 return Integer.toString(ival, radix);
1837 return Long.toString(longValue(), radix);
1838 int buf_size = ival * (MPN.chars_per_word(radix) + 1);
1839 CPStringBuilder buffer = new CPStringBuilder(buf_size);
1840 format(radix, buffer);
1841 return buffer.toString();
1844 public int intValue()
1848 int result = mpz.absIntValue();
1849 return mpz.compare(ZERO.mpz) < 0 ? - result : result;
1857 public long longValue()
1862 result = (abs().shiftRight(32)).mpz.absIntValue();
1864 result |= mpz.absIntValue() & 0xFFFFFFFFL;
1865 return this.compareTo(ZERO) < 0 ? - result : result;
1872 return ((long)words[1] << 32) + ((long)words[0] & 0xffffffffL);
1875 public int hashCode()
1877 // FIXME: May not match hashcode of JDK.
1880 // TODO: profile to decide whether to make it native
1881 byte[] bytes = this.toByteArray();
1883 for (int i = 0; i < bytes.length; i++)
1884 result ^= (bytes[i] & 0xFF) << (8 * (i % 4));
1888 return words == null ? ival : (words[0] + words[ival - 1]);
1891 /* Assumes x and y are both canonicalized. */
1892 private static boolean equals(BigInteger x, BigInteger y)
1895 return x.mpz.compare(y.mpz) == 0;*/
1897 if (x.words == null && y.words == null)
1898 return x.ival == y.ival;
1899 if (x.words == null || y.words == null || x.ival != y.ival)
1901 for (int i = x.ival; --i >= 0; )
1903 if (x.words[i] != y.words[i])
1909 /* Assumes this and obj are both canonicalized. */
1910 public boolean equals(Object obj)
1912 if (! (obj instanceof BigInteger))
1914 return equals(this, (BigInteger) obj);
1917 private static BigInteger valueOf(byte[] digits, int byte_len,
1918 boolean negative, int radix)
1920 int chars_per_word = MPN.chars_per_word(radix);
1921 int[] words = new int[byte_len / chars_per_word + 1];
1922 int size = MPN.set_str(words, digits, byte_len, radix);
1925 if (words[size-1] < 0)
1928 negate(words, words, size);
1929 return make(words, size);
1932 public double doubleValue()
1935 return mpz.doubleValue();*/
1938 return (double) ival;
1940 return (double) longValue();
1942 return neg(this).roundToDouble(0, true, false);
1943 return roundToDouble(0, false, false);
1946 public float floatValue()
1948 return (float) doubleValue();
1951 /** Return true if any of the lowest n bits are one.
1952 * (false if n is negative). */
1953 private boolean checkBits(int n)
1958 return n > 31 || ((ival & ((1 << n) - 1)) != 0);
1960 for (i = 0; i < (n >> 5) ; i++)
1963 return (n & 31) != 0 && (words[i] & ((1 << (n & 31)) - 1)) != 0;
1966 /** Convert a semi-processed BigInteger to double.
1967 * Number must be non-negative. Multiplies by a power of two, applies sign,
1968 * and converts to double, with the usual java rounding.
1969 * @param exp power of two, positive or negative, by which to multiply
1970 * @param neg true if negative
1971 * @param remainder true if the BigInteger is the result of a truncating
1972 * division that had non-zero remainder. To ensure proper rounding in
1973 * this case, the BigInteger must have at least 54 bits. */
1974 private double roundToDouble(int exp, boolean neg, boolean remainder)
1977 int il = bitLength();
1979 // Exponent when normalized to have decimal point directly after
1980 // leading one. This is stored excess 1023 in the exponent bit field.
1983 // Gross underflow. If exp == -1075, we let the rounding
1984 // computation determine whether it is minval or 0 (which are just
1985 // 0x0000 0000 0000 0001 and 0x0000 0000 0000 0000 as bit
1988 return neg ? -0.0 : 0.0;
1992 return neg ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
1994 // number of bits in mantissa, including the leading one.
1995 // 53 unless it's denormalized
1996 int ml = (exp >= -1022 ? 53 : 53 + exp + 1022);
1998 // Get top ml + 1 bits. The extra one is for rounding.
2000 int excess_bits = il - (ml + 1);
2001 if (excess_bits > 0)
2002 m = ((words == null) ? ival >> excess_bits
2003 : MPN.rshift_long(words, ival, excess_bits));
2005 m = longValue() << (- excess_bits);
2007 // Special rounding for maxval. If the number exceeds maxval by
2008 // any amount, even if it's less than half a step, it overflows.
2009 if (exp == 1023 && ((m >> 1) == (1L << 53) - 1))
2011 if (remainder || checkBits(il - ml))
2012 return neg ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
2014 return neg ? - Double.MAX_VALUE : Double.MAX_VALUE;
2017 // Normal round-to-even rule: round up if the bit dropped is a one, and
2018 // the bit above it or any of the bits below it is a one.
2020 && ((m & 2) == 2 || remainder || checkBits(excess_bits)))
2023 // Check if we overflowed the mantissa
2024 if ((m & (1L << 54)) != 0)
2030 // Check if a denormalized mantissa was just rounded up to a
2032 else if (ml == 52 && (m & (1L << 53)) != 0)
2036 // Discard the rounding bit
2039 long bits_sign = neg ? (1L << 63) : 0;
2041 long bits_exp = (exp <= 0) ? 0 : ((long)exp) << 52;
2042 long bits_mant = m & ~(1L << 52);
2043 return Double.longBitsToDouble(bits_sign | bits_exp | bits_mant);
2046 /** Copy the abolute value of this into an array of words.
2047 * Assumes words.length >= (this.words == null ? 1 : this.ival).
2048 * Result is zero-extended, but need not be a valid 2's complement number.
2050 private void getAbsolute(int[] words)
2053 if (this.words == null)
2056 words[0] = this.ival;
2061 for (int i = len; --i >= 0; )
2062 words[i] = this.words[i];
2064 if (words[len - 1] < 0)
2065 negate(words, words, len);
2066 for (int i = words.length; --i > len; )
2070 /** Set dest[0:len-1] to the negation of src[0:len-1].
2071 * Return true if overflow (i.e. if src is -2**(32*len-1)).
2072 * Ok for src==dest. */
2073 private static boolean negate(int[] dest, int[] src, int len)
2076 boolean negative = src[len-1] < 0;
2077 for (int i = 0; i < len; i++)
2079 carry += ((long) (~src[i]) & 0xffffffffL);
2080 dest[i] = (int) carry;
2083 return (negative && dest[len-1] < 0);
2086 /** Destructively set this to the negative of x.
2087 * It is OK if x==this.*/
2088 private void setNegative(BigInteger x)
2091 if (x.words == null)
2093 if (len == Integer.MIN_VALUE)
2100 if (negate(words, x.words, len))
2105 /** Destructively negate this. */
2106 private void setNegative()
2111 private static BigInteger abs(BigInteger x)
2113 return x.isNegative() ? neg(x) : x;
2116 public BigInteger abs()
2120 BigInteger result = new BigInteger();
2121 mpz.abs(result.mpz);
2128 private static BigInteger neg(BigInteger x)
2130 if (x.words == null && x.ival != Integer.MIN_VALUE)
2131 return valueOf(- x.ival);
2132 BigInteger result = new BigInteger(0);
2133 result.setNegative(x);
2134 return result.canonicalize();
2137 public BigInteger negate()
2141 BigInteger result = new BigInteger();
2142 mpz.negate(result.mpz);
2149 /** Calculates ceiling(log2(this < 0 ? -this : this+1))
2150 * See Common Lisp: the Language, 2nd ed, p. 361.
2152 public int bitLength()
2155 return mpz.bitLength();*/
2158 return MPN.intLength(ival);
2159 return MPN.intLength(words, ival);
2162 public byte[] toByteArray()
2169 // the minimal number of bytes required to represent the MPI is function
2170 // of (a) its bit-length, and (b) its sign. only when this MPI is both
2171 // positive, and its bit-length is a multiple of 8 do we add one zero
2172 // bit for its sign. we do this so if we construct a new MPI from the
2173 // resulting byte array, we wouldn't mistake a positive number, whose
2174 // bit-length is a multiple of 8, for a similar-length negative one.
2175 int bits = bitLength();
2176 if (bits % 8 == 0 || this.signum() == 1)
2178 byte[] bytes = new byte[(bits + 7) / 8];
2179 mpz.toByteArray(bytes);
2183 // Determine number of bytes needed. The method bitlength returns
2184 // the size without the sign bit, so add one bit for that and then
2185 // add 7 more to emulate the ceil function using integer math.
2186 byte[] bytes = new byte[(bitLength() + 1 + 7) / 8];
2187 int nbytes = bytes.length;
2192 // Deal with words array until one word or less is left to process.
2193 // If BigInteger is an int, then it is in ival and nbytes will be <= 4.
2196 word = words[wptr++];
2197 for (int i = 4; i > 0; --i, word >>= 8)
2198 bytes[--nbytes] = (byte) word;
2201 // Deal with the last few bytes. If BigInteger is an int, use ival.
2202 word = (words == null) ? ival : words[wptr];
2203 for ( ; nbytes > 0; word >>= 8)
2204 bytes[--nbytes] = (byte) word;
2209 /** Return the boolean opcode (for bitOp) for swapped operands.
2210 * I.e. bitOp(swappedOp(op), x, y) == bitOp(op, y, x).
2212 private static int swappedOp(int op)
2215 "\000\001\004\005\002\003\006\007\010\011\014\015\012\013\016\017"
2219 /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
2220 private static BigInteger bitOp(int op, BigInteger x, BigInteger y)
2224 case 0: return ZERO;
2225 case 1: return x.and(y);
2228 case 15: return valueOf(-1);
2230 BigInteger result = new BigInteger();
2231 setBitOp(result, op, x, y);
2232 return result.canonicalize();
2235 /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
2236 private static void setBitOp(BigInteger result, int op,
2237 BigInteger x, BigInteger y)
2239 if ((y.words != null) && (x.words == null || x.ival < y.ival))
2241 BigInteger temp = x; x = y; y = temp;
2247 if (y.words == null)
2257 if (x.words == null)
2268 result.realloc(xlen);
2269 int[] w = result.words;
2271 // Code for how to handle the remainder of x.
2272 // 0: Truncate to length of y.
2273 // 1: Copy rest of x.
2274 // 2: Invert rest of x.
2286 if (i+1 >= ylen) break;
2287 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2289 if (yi < 0) finish = 1;
2295 if (i+1 >= ylen) break;
2296 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2298 if (yi >= 0) finish = 1;
2302 finish = 1; // Copy rest
2308 if (i+1 >= ylen) break;
2309 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2311 if (yi < 0) finish = 2;
2317 if (i+1 >= ylen) break;
2318 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2325 if (i+1 >= ylen) break;
2326 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2328 finish = yi < 0 ? 2 : 1;
2334 if (i+1 >= ylen) break;
2335 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2337 if (yi >= 0) finish = 1;
2343 if (i+1 >= ylen) break;
2344 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2346 if (yi >= 0) finish = 2;
2348 case 9: // eqv [exclusive nor]
2352 if (i+1 >= ylen) break;
2353 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2355 finish = yi >= 0 ? 2 : 1;
2361 if (i+1 >= ylen) break;
2362 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2369 if (i+1 >= ylen) break;
2370 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2372 if (yi < 0) finish = 1;
2382 if (i+1 >= ylen) break;
2383 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2385 if (yi >= 0) finish = 2;
2391 if (i+1 >= ylen) break;
2392 w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2394 if (yi < 0) finish = 2;
2401 // Here i==ylen-1; w[0]..w[i-1] have the correct result;
2402 // and ni contains the correct result for w[i+1].
2408 if (i == 0 && w == null)
2415 case 1: w[i] = ni; while (++i < xlen) w[i] = x.words[i]; break;
2416 case 2: w[i] = ni; while (++i < xlen) w[i] = ~x.words[i]; break;
2421 /** Return the logical (bit-wise) "and" of a BigInteger and an int. */
2422 private static BigInteger and(BigInteger x, int y)
2424 if (x.words == null)
2425 return valueOf(x.ival & y);
2427 return valueOf(x.words[0] & y);
2429 int[] words = new int[len];
2430 words[0] = x.words[0] & y;
2432 words[len] = x.words[len];
2433 return make(words, x.ival);
2436 /** Return the logical (bit-wise) "and" of two BigIntegers. */
2437 public BigInteger and(BigInteger y)
2441 int dummy = y.signum; // force NPE check
2442 BigInteger result = new BigInteger();
2443 mpz.and(y.mpz, result.mpz);
2447 if (y.words == null)
2448 return and(this, y.ival);
2449 else if (words == null)
2450 return and(y, ival);
2452 BigInteger x = this;
2455 BigInteger temp = this; x = y; y = temp;
2458 int len = y.isNegative() ? x.ival : y.ival;
2459 int[] words = new int[len];
2460 for (i = 0; i < y.ival; i++)
2461 words[i] = x.words[i] & y.words[i];
2462 for ( ; i < len; i++)
2463 words[i] = x.words[i];
2464 return make(words, len);
2467 /** Return the logical (bit-wise) "(inclusive) or" of two BigIntegers. */
2468 public BigInteger or(BigInteger y)
2472 int dummy = y.signum; // force NPE check
2473 BigInteger result = new BigInteger();
2474 mpz.or(y.mpz, result.mpz);
2478 return bitOp(7, this, y);
2481 /** Return the logical (bit-wise) "exclusive or" of two BigIntegers. */
2482 public BigInteger xor(BigInteger y)
2486 int dummy = y.signum; // force NPE check
2487 BigInteger result = new BigInteger();
2488 mpz.xor(y.mpz, result.mpz);
2492 return bitOp(6, this, y);
2495 /** Return the logical (bit-wise) negation of a BigInteger. */
2496 public BigInteger not()
2500 BigInteger result = new BigInteger();
2501 mpz.not(result.mpz);
2505 return bitOp(12, this, ZERO);
2508 public BigInteger andNot(BigInteger val)
2512 int dummy = val.signum; // force NPE check
2513 BigInteger result = new BigInteger();
2514 mpz.andNot(val.mpz, result.mpz);
2518 return and(val.not());
2521 public BigInteger clearBit(int n)
2524 throw new ArithmeticException();
2528 BigInteger result = new BigInteger();
2529 mpz.setBit(n, false, result.mpz);
2533 return and(ONE.shiftLeft(n).not());
2536 public BigInteger setBit(int n)
2539 throw new ArithmeticException();
2543 BigInteger result = new BigInteger();
2544 mpz.setBit(n, true, result.mpz);
2548 return or(ONE.shiftLeft(n));
2551 public boolean testBit(int n)
2554 throw new Error("Arithmetic Exception")/*ArithmeticException()*/;
2557 return mpz.testBit(n) != 0;*/
2559 return !and(ONE.shiftLeft(n)).isZero();
2562 public BigInteger flipBit(int n)
2565 throw new Error("Arithmetic Exception")/*ArithmeticException()*/;
2569 BigInteger result = new BigInteger();
2570 mpz.flipBit(n, result.mpz);
2574 return xor(ONE.shiftLeft(n));
2577 public int getLowestSetBit()
2580 return mpz.compare(ZERO.mpz) == 0 ? -1 : mpz.lowestSetBit();*/
2586 return MPN.findLowestBit(ival);
2588 return MPN.findLowestBit(words);
2591 // bit4count[I] is number of '1' bits in I.
2592 private static final byte[] bit4_count = { 0, 1, 1, 2, 1, 2, 2, 3,
2593 1, 2, 2, 3, 2, 3, 3, 4};
2595 private static int bitCount(int i)
2600 count += bit4_count[i & 15];
2606 private static int bitCount(int[] x, int len)
2610 count += bitCount(x[len]);
2614 /** Count one bits in a BigInteger.
2615 * If argument is negative, count zero bits instead. */
2616 public int bitCount()
2619 return mpz.bitCount();*/
2622 int[] x_words = words;
2623 if (x_words == null)
2631 i = bitCount(x_words, x_len);
2633 return isNegative() ? x_len * 32 - i : i;
2636 /*private void readObject(ObjectInputStream s)
2637 //throws IOException, ClassNotFoundException
2642 s.defaultReadObject();
2644 mpz.fromByteArray(magnitude);
2645 // else it's zero and we need to do nothing
2649 s.defaultReadObject();
2650 if (magnitude.length == 0 || signum == 0)
2657 words = byteArrayToIntArray(magnitude, signum < 0 ? -1 : 0);
2658 BigInteger result = make(words, words.length);
2659 this.ival = result.ival;
2660 this.words = result.words;
2665 /*private void writeObject(ObjectOutputStream s)
2666 //throws IOException, ClassNotFoundException
2669 magnitude = signum == 0 ? new byte[0] : toByteArray();
2670 s.defaultWriteObject();
2671 magnitude = null; // not needed anymore
2674 // inner class(es) ..........................................................