1 /* java.math.BigInteger -- Arbitary precision integers
2 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2005 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
.java
.math
.MPN
;
43 import java
.io
.IOException
;
44 import java
.io
.ObjectInputStream
;
45 import java
.io
.ObjectOutputStream
;
46 import java
.util
.Random
;
49 * Written using on-line Java Platform 1.2 API Specification, as well
50 * as "The Java Class Libraries", 2nd edition (Addison-Wesley, 1998) and
51 * "Applied Cryptography, Second Edition" by Bruce Schneier (Wiley, 1996).
53 * Based primarily on IntNum.java BitOps.java by Per Bothner (per@bothner.com)
54 * (found in Kawa 1.6.62).
56 * @author Warren Levy (warrenl@cygnus.com)
57 * @date December 20, 1999.
58 * @status believed complete and correct.
60 public class BigInteger
extends Number
implements Comparable
62 /** All integers are stored in 2's-complement form.
63 * If words == null, the ival is the value of this BigInteger.
64 * Otherwise, the first ival elements of words make the value
65 * of this BigInteger, stored in little-endian order, 2's-complement form. */
66 private transient int ival
;
67 private transient int[] words
;
69 // Serialization fields.
70 private int bitCount
= -1;
71 private int bitLength
= -1;
72 private int firstNonzeroByteNum
= -2;
73 private int lowestSetBit
= -2;
74 private byte[] magnitude
;
76 private static final long serialVersionUID
= -8287574255936472291L;
79 /** We pre-allocate integers in the range minFixNum..maxFixNum.
80 * Note that we must at least preallocate 0, 1, and 10. */
81 private static final int minFixNum
= -100;
82 private static final int maxFixNum
= 1024;
83 private static final int numFixNum
= maxFixNum
-minFixNum
+1;
84 private static final BigInteger
[] smallFixNums
= new BigInteger
[numFixNum
];
87 for (int i
= numFixNum
; --i
>= 0; )
88 smallFixNums
[i
] = new BigInteger(i
+ minFixNum
);
92 * The constant zero as a BigInteger.
95 public static final BigInteger ZERO
= smallFixNums
[-minFixNum
];
98 * The constant one as a BigInteger.
101 public static final BigInteger ONE
= smallFixNums
[1 - minFixNum
];
104 * The constant ten as a BigInteger.
107 public static final BigInteger TEN
= smallFixNums
[10 - minFixNum
];
109 /* Rounding modes: */
110 private static final int FLOOR
= 1;
111 private static final int CEILING
= 2;
112 private static final int TRUNCATE
= 3;
113 private static final int ROUND
= 4;
115 /** When checking the probability of primes, it is most efficient to
116 * first check the factoring of small primes, so we'll use this array.
118 private static final int[] primes
=
119 { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
120 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
121 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181,
122 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251 };
124 /** HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Table 4.4. */
125 private static final int[] k
=
126 {100,150,200,250,300,350,400,500,600,800,1250, Integer
.MAX_VALUE
};
127 private static final int[] t
=
128 { 27, 18, 15, 12, 9, 8, 7, 6, 5, 4, 3, 2};
134 /* Create a new (non-shared) BigInteger, and initialize to an int. */
135 private BigInteger(int value
)
140 public BigInteger(String val
, int radix
)
142 BigInteger result
= valueOf(val
, radix
);
143 this.ival
= result
.ival
;
144 this.words
= result
.words
;
147 public BigInteger(String val
)
152 /* Create a new (non-shared) BigInteger, and initialize from a byte array. */
153 public BigInteger(byte[] val
)
155 if (val
== null || val
.length
< 1)
156 throw new NumberFormatException();
158 words
= byteArrayToIntArray(val
, val
[0] < 0 ?
-1 : 0);
159 BigInteger result
= make(words
, words
.length
);
160 this.ival
= result
.ival
;
161 this.words
= result
.words
;
164 public BigInteger(int signum
, byte[] magnitude
)
166 if (magnitude
== null || signum
> 1 || signum
< -1)
167 throw new NumberFormatException();
172 for (i
= magnitude
.length
- 1; i
>= 0 && magnitude
[i
] == 0; --i
)
175 throw new NumberFormatException();
179 // Magnitude is always positive, so don't ever pass a sign of -1.
180 words
= byteArrayToIntArray(magnitude
, 0);
181 BigInteger result
= make(words
, words
.length
);
182 this.ival
= result
.ival
;
183 this.words
= result
.words
;
189 public BigInteger(int numBits
, Random rnd
)
192 throw new IllegalArgumentException();
197 private void init(int numBits
, Random rnd
)
199 int highbits
= numBits
& 31;
201 highbits
= rnd
.nextInt() >>> (32 - highbits
);
202 int nwords
= numBits
/ 32;
204 while (highbits
== 0 && nwords
> 0)
206 highbits
= rnd
.nextInt();
209 if (nwords
== 0 && highbits
>= 0)
215 ival
= highbits
< 0 ? nwords
+ 2 : nwords
+ 1;
216 words
= new int[ival
];
217 words
[nwords
] = highbits
;
218 while (--nwords
>= 0)
219 words
[nwords
] = rnd
.nextInt();
223 public BigInteger(int bitLength
, int certainty
, Random rnd
)
225 this(bitLength
, rnd
);
227 // Keep going until we find a probable prime.
230 if (isProbablePrime(certainty
))
233 init(bitLength
, rnd
);
238 * Return a BigInteger that is bitLength bits long with a
239 * probability < 2^-100 of being composite.
241 * @param bitLength length in bits of resulting number
242 * @param rnd random number generator to use
243 * @throws ArithmeticException if bitLength < 2
246 public static BigInteger
probablePrime(int bitLength
, Random rnd
)
249 throw new ArithmeticException();
251 return new BigInteger(bitLength
, 100, rnd
);
254 /** Return a (possibly-shared) BigInteger with a given long value. */
255 public static BigInteger
valueOf(long val
)
257 if (val
>= minFixNum
&& val
<= maxFixNum
)
258 return smallFixNums
[(int) val
- minFixNum
];
261 return new BigInteger(i
);
262 BigInteger result
= alloc(2);
265 result
.words
[1] = (int)(val
>> 32);
269 /** Make a canonicalized BigInteger from an array of words.
270 * The array may be reused (without copying). */
271 private static BigInteger
make(int[] words
, int len
)
275 len
= BigInteger
.wordsNeeded(words
, len
);
277 return len
== 0 ? ZERO
: valueOf(words
[0]);
278 BigInteger num
= new BigInteger();
284 /** Convert a big-endian byte array to a little-endian array of words. */
285 private static int[] byteArrayToIntArray(byte[] bytes
, int sign
)
287 // Determine number of words needed.
288 int[] words
= new int[bytes
.length
/4 + 1];
289 int nwords
= words
.length
;
291 // Create a int out of modulo 4 high order bytes.
294 for (int i
= bytes
.length
% 4; i
> 0; --i
, bptr
++)
295 word
= (word
<< 8) | (bytes
[bptr
] & 0xff);
296 words
[--nwords
] = word
;
298 // Elements remaining in byte[] are a multiple of 4.
300 words
[--nwords
] = bytes
[bptr
++] << 24 |
301 (bytes
[bptr
++] & 0xff) << 16 |
302 (bytes
[bptr
++] & 0xff) << 8 |
303 (bytes
[bptr
++] & 0xff);
307 /** Allocate a new non-shared BigInteger.
308 * @param nwords number of words to allocate
310 private static BigInteger
alloc(int nwords
)
312 BigInteger result
= new BigInteger();
314 result
.words
= new int[nwords
];
318 /** Change words.length to nwords.
319 * We allow words.length to be upto nwords+2 without reallocating.
321 private void realloc(int nwords
)
332 else if (words
== null
333 || words
.length
< nwords
334 || words
.length
> nwords
+ 2)
336 int[] new_words
= new int [nwords
];
346 System
.arraycopy(words
, 0, new_words
, 0, ival
);
352 private boolean isNegative()
354 return (words
== null ? ival
: words
[ival
- 1]) < 0;
359 if (ival
== 0 && words
== null)
361 int top
= words
== null ? ival
: words
[ival
-1];
362 return top
< 0 ?
-1 : 1;
365 private static int compareTo(BigInteger x
, BigInteger y
)
367 if (x
.words
== null && y
.words
== null)
368 return x
.ival
< y
.ival ?
-1 : x
.ival
> y
.ival ?
1 : 0;
369 boolean x_negative
= x
.isNegative();
370 boolean y_negative
= y
.isNegative();
371 if (x_negative
!= y_negative
)
372 return x_negative ?
-1 : 1;
373 int x_len
= x
.words
== null ?
1 : x
.ival
;
374 int y_len
= y
.words
== null ?
1 : y
.ival
;
376 return (x_len
> y_len
) != x_negative ?
1 : -1;
377 return MPN
.cmp(x
.words
, y
.words
, x_len
);
381 public int compareTo(Object obj
)
383 if (obj
instanceof BigInteger
)
384 return compareTo(this, (BigInteger
) obj
);
385 throw new ClassCastException();
388 public int compareTo(BigInteger val
)
390 return compareTo(this, val
);
393 public BigInteger
min(BigInteger val
)
395 return compareTo(this, val
) < 0 ?
this : val
;
398 public BigInteger
max(BigInteger val
)
400 return compareTo(this, val
) > 0 ?
this : val
;
403 private boolean isZero()
405 return words
== null && ival
== 0;
408 private boolean isOne()
410 return words
== null && ival
== 1;
413 /** Calculate how many words are significant in words[0:len-1].
414 * Returns the least value x such that x>0 && words[0:x-1]==words[0:len-1],
415 * when words is viewed as a 2's complement integer.
417 private static int wordsNeeded(int[] words
, int len
)
422 int word
= words
[--i
];
425 while (i
> 0 && (word
= words
[i
- 1]) < 0)
428 if (word
!= -1) break;
433 while (word
== 0 && i
> 0 && (word
= words
[i
- 1]) >= 0) i
--;
439 private BigInteger
canonicalize()
442 && (ival
= BigInteger
.wordsNeeded(words
, ival
)) <= 1)
448 if (words
== null && ival
>= minFixNum
&& ival
<= maxFixNum
)
449 return smallFixNums
[ival
- minFixNum
];
453 /** Add two ints, yielding a BigInteger. */
454 private static BigInteger
add(int x
, int y
)
456 return valueOf((long) x
+ (long) y
);
459 /** Add a BigInteger and an int, yielding a new BigInteger. */
460 private static BigInteger
add(BigInteger x
, int y
)
463 return BigInteger
.add(x
.ival
, y
);
464 BigInteger result
= new BigInteger(0);
466 return result
.canonicalize();
469 /** Set this to the sum of x and y.
471 private void setAdd(BigInteger x
, int y
)
475 set((long) x
.ival
+ (long) y
);
481 for (int i
= 0; i
< len
; i
++)
483 carry
+= ((long) x
.words
[i
] & 0xffffffffL
);
484 words
[i
] = (int) carry
;
487 if (x
.words
[len
- 1] < 0)
489 words
[len
] = (int) carry
;
490 ival
= wordsNeeded(words
, len
+ 1);
493 /** Destructively add an int to this. */
494 private void setAdd(int y
)
499 /** Destructively set the value of this to a long. */
500 private void set(long y
)
512 words
[1] = (int) (y
>> 32);
517 /** Destructively set the value of this to the given words.
518 * The words array is reused, not copied. */
519 private void set(int[] words
, int length
)
525 /** Destructively set the value of this to that of y. */
526 private void set(BigInteger y
)
533 System
.arraycopy(y
.words
, 0, words
, 0, y
.ival
);
538 /** Add two BigIntegers, yielding their sum as another BigInteger. */
539 private static BigInteger
add(BigInteger x
, BigInteger y
, int k
)
541 if (x
.words
== null && y
.words
== null)
542 return valueOf((long) k
* (long) y
.ival
+ (long) x
.ival
);
546 y
= BigInteger
.neg(y
);
548 y
= BigInteger
.times(y
, valueOf(k
));
551 return BigInteger
.add(y
, x
.ival
);
553 return BigInteger
.add(x
, y
.ival
);
556 { // Swap so x is longer then y.
557 BigInteger tmp
= x
; x
= y
; y
= tmp
;
559 BigInteger result
= alloc(x
.ival
+ 1);
561 long carry
= MPN
.add_n(result
.words
, x
.words
, y
.words
, i
);
562 long y_ext
= y
.words
[i
- 1] < 0 ?
0xffffffffL
: 0;
563 for (; i
< x
.ival
; i
++)
565 carry
+= ((long) x
.words
[i
] & 0xffffffffL
) + y_ext
;;
566 result
.words
[i
] = (int) carry
;
569 if (x
.words
[i
- 1] < 0)
571 result
.words
[i
] = (int) (carry
+ y_ext
);
573 return result
.canonicalize();
576 public BigInteger
add(BigInteger val
)
578 return add(this, val
, 1);
581 public BigInteger
subtract(BigInteger val
)
583 return add(this, val
, -1);
586 private static BigInteger
times(BigInteger x
, int y
)
592 int[] xwords
= x
.words
;
595 return valueOf((long) xlen
* (long) y
);
597 BigInteger result
= BigInteger
.alloc(xlen
+ 1);
598 if (xwords
[xlen
- 1] < 0)
601 negate(result
.words
, xwords
, xlen
);
602 xwords
= result
.words
;
608 negative
= !negative
;
611 result
.words
[xlen
] = MPN
.mul_1(result
.words
, xwords
, xlen
, y
);
612 result
.ival
= xlen
+ 1;
614 result
.setNegative();
615 return result
.canonicalize();
618 private static BigInteger
times(BigInteger x
, BigInteger y
)
621 return times(x
, y
.ival
);
623 return times(y
, x
.ival
);
624 boolean negative
= false;
632 xwords
= new int[xlen
];
633 negate(xwords
, x
.words
, xlen
);
642 negative
= !negative
;
643 ywords
= new int[ylen
];
644 negate(ywords
, y
.words
, ylen
);
648 // Swap if x is shorter then y.
651 int[] twords
= xwords
; xwords
= ywords
; ywords
= twords
;
652 int tlen
= xlen
; xlen
= ylen
; ylen
= tlen
;
654 BigInteger result
= BigInteger
.alloc(xlen
+ylen
);
655 MPN
.mul(result
.words
, xwords
, xlen
, ywords
, ylen
);
656 result
.ival
= xlen
+ylen
;
658 result
.setNegative();
659 return result
.canonicalize();
662 public BigInteger
multiply(BigInteger y
)
664 return times(this, y
);
667 private static void divide(long x
, long y
,
668 BigInteger quotient
, BigInteger remainder
,
671 boolean xNegative
, yNegative
;
675 if (x
== Long
.MIN_VALUE
)
677 divide(valueOf(x
), valueOf(y
),
678 quotient
, remainder
, rounding_mode
);
689 if (y
== Long
.MIN_VALUE
)
691 if (rounding_mode
== TRUNCATE
)
692 { // x != Long.Min_VALUE implies abs(x) < abs(y)
693 if (quotient
!= null)
695 if (remainder
!= null)
699 divide(valueOf(x
), valueOf(y
),
700 quotient
, remainder
, rounding_mode
);
710 boolean qNegative
= xNegative ^ yNegative
;
712 boolean add_one
= false;
715 switch (rounding_mode
)
721 if (qNegative
== (rounding_mode
== FLOOR
))
725 add_one
= r
> ((y
- (q
& 1)) >> 1);
729 if (quotient
!= null)
737 if (remainder
!= null)
739 // The remainder is by definition: X-Q*Y
742 // Subtract the remainder from Y.
744 // In this case, abs(Q*Y) > abs(X).
745 // So sign(remainder) = -sign(X).
746 xNegative
= ! xNegative
;
750 // If !add_one, then: abs(Q*Y) <= abs(X).
751 // So sign(remainder) = sign(X).
759 /** Divide two integers, yielding quotient and remainder.
760 * @param x the numerator in the division
761 * @param y the denominator in the division
762 * @param quotient is set to the quotient of the result (iff quotient!=null)
763 * @param remainder is set to the remainder of the result
764 * (iff remainder!=null)
765 * @param rounding_mode one of FLOOR, CEILING, TRUNCATE, or ROUND.
767 private static void divide(BigInteger x
, BigInteger y
,
768 BigInteger quotient
, BigInteger remainder
,
771 if ((x
.words
== null || x
.ival
<= 2)
772 && (y
.words
== null || y
.ival
<= 2))
774 long x_l
= x
.longValue();
775 long y_l
= y
.longValue();
776 if (x_l
!= Long
.MIN_VALUE
&& y_l
!= Long
.MIN_VALUE
)
778 divide(x_l
, y_l
, quotient
, remainder
, rounding_mode
);
783 boolean xNegative
= x
.isNegative();
784 boolean yNegative
= y
.isNegative();
785 boolean qNegative
= xNegative ^ yNegative
;
787 int ylen
= y
.words
== null ?
1 : y
.ival
;
788 int[] ywords
= new int[ylen
];
789 y
.getAbsolute(ywords
);
790 while (ylen
> 1 && ywords
[ylen
- 1] == 0) ylen
--;
792 int xlen
= x
.words
== null ?
1 : x
.ival
;
793 int[] xwords
= new int[xlen
+2];
794 x
.getAbsolute(xwords
);
795 while (xlen
> 1 && xwords
[xlen
-1] == 0) xlen
--;
799 int cmpval
= MPN
.cmp(xwords
, xlen
, ywords
, ylen
);
800 if (cmpval
< 0) // abs(x) < abs(y)
801 { // quotient = 0; remainder = num.
802 int[] rwords
= xwords
; xwords
= ywords
; ywords
= rwords
;
803 rlen
= xlen
; qlen
= 1; xwords
[0] = 0;
805 else if (cmpval
== 0) // abs(x) == abs(y)
807 xwords
[0] = 1; qlen
= 1; // quotient = 1
808 ywords
[0] = 0; rlen
= 1; // remainder = 0;
813 // Need to leave room for a word of leading zeros if dividing by 1
814 // and the dividend has the high bit set. It might be safe to
815 // increment qlen in all cases, but it certainly is only necessary
816 // in the following case.
817 if (ywords
[0] == 1 && xwords
[xlen
-1] < 0)
820 ywords
[0] = MPN
.divmod_1(xwords
, xwords
, xlen
, ywords
[0]);
822 else // abs(x) > abs(y)
824 // Normalize the denominator, i.e. make its most significant bit set by
825 // shifting it normalization_steps bits to the left. Also shift the
826 // numerator the same number of steps (to keep the quotient the same!).
828 int nshift
= MPN
.count_leading_zeros(ywords
[ylen
- 1]);
831 // Shift up the denominator setting the most significant bit of
832 // the most significant word.
833 MPN
.lshift(ywords
, 0, ywords
, ylen
, nshift
);
835 // Shift up the numerator, possibly introducing a new most
837 int x_high
= MPN
.lshift(xwords
, 0, xwords
, xlen
, nshift
);
838 xwords
[xlen
++] = x_high
;
843 MPN
.divide(xwords
, xlen
, ywords
, ylen
);
845 MPN
.rshift0 (ywords
, xwords
, 0, rlen
, nshift
);
847 qlen
= xlen
+ 1 - ylen
;
848 if (quotient
!= null)
850 for (int i
= 0; i
< qlen
; i
++)
851 xwords
[i
] = xwords
[i
+ylen
];
855 if (ywords
[rlen
-1] < 0)
861 // Now the quotient is in xwords, and the remainder is in ywords.
863 boolean add_one
= false;
864 if (rlen
> 1 || ywords
[0] != 0)
865 { // Non-zero remainder i.e. in-exact quotient.
866 switch (rounding_mode
)
872 if (qNegative
== (rounding_mode
== FLOOR
))
876 // int cmp = compareTo(remainder<<1, abs(y));
877 BigInteger tmp
= remainder
== null ?
new BigInteger() : remainder
;
878 tmp
.set(ywords
, rlen
);
882 int cmp
= compareTo(tmp
, y
);
883 // Now cmp == compareTo(sign(y)*(remainder<<1), y)
886 add_one
= (cmp
== 1) || (cmp
== 0 && (xwords
[0]&1) != 0);
889 if (quotient
!= null)
891 quotient
.set(xwords
, qlen
);
894 if (add_one
) // -(quotient + 1) == ~(quotient)
895 quotient
.setInvert();
897 quotient
.setNegative();
902 if (remainder
!= null)
904 // The remainder is by definition: X-Q*Y
905 remainder
.set(ywords
, rlen
);
908 // Subtract the remainder from Y:
909 // abs(R) = abs(Y) - abs(orig_rem) = -(abs(orig_rem) - abs(Y)).
914 tmp
.set(yNegative ? ywords
[0] + y
.ival
: ywords
[0] - y
.ival
);
917 tmp
= BigInteger
.add(remainder
, y
, yNegative ?
1 : -1);
919 // In this case, abs(Q) = 1 + floor(abs(X)/abs(Y)).
920 // Hence, abs(Q*Y) > abs(X).
921 // So sign(remainder) = -sign(X).
923 remainder
.setNegative(tmp
);
929 // If !add_one, then: abs(Q*Y) <= abs(X).
930 // So sign(remainder) = sign(X).
932 remainder
.setNegative();
937 public BigInteger
divide(BigInteger val
)
940 throw new ArithmeticException("divisor is zero");
942 BigInteger quot
= new BigInteger();
943 divide(this, val
, quot
, null, TRUNCATE
);
944 return quot
.canonicalize();
947 public BigInteger
remainder(BigInteger val
)
950 throw new ArithmeticException("divisor is zero");
952 BigInteger rem
= new BigInteger();
953 divide(this, val
, null, rem
, TRUNCATE
);
954 return rem
.canonicalize();
957 public BigInteger
[] divideAndRemainder(BigInteger val
)
960 throw new ArithmeticException("divisor is zero");
962 BigInteger
[] result
= new BigInteger
[2];
963 result
[0] = new BigInteger();
964 result
[1] = new BigInteger();
965 divide(this, val
, result
[0], result
[1], TRUNCATE
);
966 result
[0].canonicalize();
967 result
[1].canonicalize();
971 public BigInteger
mod(BigInteger m
)
973 if (m
.isNegative() || m
.isZero())
974 throw new ArithmeticException("non-positive modulus");
976 BigInteger rem
= new BigInteger();
977 divide(this, m
, null, rem
, FLOOR
);
978 return rem
.canonicalize();
981 /** Calculate the integral power of a BigInteger.
982 * @param exponent the exponent (must be non-negative)
984 public BigInteger
pow(int exponent
)
990 throw new ArithmeticException("negative exponent");
994 int plen
= words
== null ?
1 : ival
; // Length of pow2.
995 int blen
= ((bitLength() * exponent
) >> 5) + 2 * plen
;
996 boolean negative
= isNegative() && (exponent
& 1) != 0;
997 int[] pow2
= new int [blen
];
998 int[] rwords
= new int [blen
];
999 int[] work
= new int [blen
];
1000 getAbsolute(pow2
); // pow2 = abs(this);
1002 rwords
[0] = 1; // rwords = 1;
1003 for (;;) // for (i = 0; ; i++)
1005 // pow2 == this**(2**i)
1006 // prod = this**(sum(j=0..i-1, (exponent>>j)&1))
1007 if ((exponent
& 1) != 0)
1009 MPN
.mul(work
, pow2
, plen
, rwords
, rlen
);
1010 int[] temp
= work
; work
= rwords
; rwords
= temp
;
1012 while (rwords
[rlen
- 1] == 0) rlen
--;
1018 MPN
.mul(work
, pow2
, plen
, pow2
, plen
);
1019 int[] temp
= work
; work
= pow2
; pow2
= temp
; // swap to avoid a copy
1021 while (pow2
[plen
- 1] == 0) plen
--;
1023 if (rwords
[rlen
- 1] < 0)
1026 negate(rwords
, rwords
, rlen
);
1027 return BigInteger
.make(rwords
, rlen
);
1030 private static int[] euclidInv(int a
, int b
, int prevDiv
)
1033 throw new ArithmeticException("not invertible");
1036 // Success: values are indeed invertible!
1037 // Bottom of the recursion reached; start unwinding.
1038 return new int[] { -prevDiv
, 1 };
1040 int[] xy
= euclidInv(b
, a
% b
, a
/ b
); // Recursion happens here.
1041 a
= xy
[0]; // use our local copy of 'a' as a work var
1042 xy
[0] = a
* -prevDiv
+ xy
[1];
1047 private static void euclidInv(BigInteger a
, BigInteger b
,
1048 BigInteger prevDiv
, BigInteger
[] xy
)
1051 throw new ArithmeticException("not invertible");
1055 // Success: values are indeed invertible!
1056 // Bottom of the recursion reached; start unwinding.
1057 xy
[0] = neg(prevDiv
);
1062 // Recursion happens in the following conditional!
1064 // If a just contains an int, then use integer math for the rest.
1065 if (a
.words
== null)
1067 int[] xyInt
= euclidInv(b
.ival
, a
.ival
% b
.ival
, a
.ival
/ b
.ival
);
1068 xy
[0] = new BigInteger(xyInt
[0]);
1069 xy
[1] = new BigInteger(xyInt
[1]);
1073 BigInteger rem
= new BigInteger();
1074 BigInteger quot
= new BigInteger();
1075 divide(a
, b
, quot
, rem
, FLOOR
);
1076 // quot and rem may not be in canonical form. ensure
1078 quot
.canonicalize();
1079 euclidInv(b
, rem
, quot
, xy
);
1082 BigInteger t
= xy
[0];
1083 xy
[0] = add(xy
[1], times(t
, prevDiv
), -1);
1087 public BigInteger
modInverse(BigInteger y
)
1089 if (y
.isNegative() || y
.isZero())
1090 throw new ArithmeticException("non-positive modulo");
1092 // Degenerate cases.
1098 // Use Euclid's algorithm as in gcd() but do this recursively
1099 // rather than in a loop so we can use the intermediate results as we
1100 // unwind from the recursion.
1101 // Used http://www.math.nmsu.edu/~crypto/EuclideanAlgo.html as reference.
1102 BigInteger result
= new BigInteger();
1103 boolean swapped
= false;
1105 if (y
.words
== null)
1107 // The result is guaranteed to be less than the modulus, y (which is
1108 // an int), so simplify this by working with the int result of this
1109 // modulo y. Also, if this is negative, make it positive via modulo
1110 // math. Note that BigInteger.mod() must be used even if this is
1111 // already an int as the % operator would provide a negative result if
1112 // this is negative, BigInteger.mod() never returns negative values.
1113 int xval
= (words
!= null || isNegative()) ?
mod(y
).ival
: ival
;
1116 // Swap values so x > y.
1119 int tmp
= xval
; xval
= yval
; yval
= tmp
;
1122 // Normally, the result is in the 2nd element of the array, but
1123 // if originally x < y, then x and y were swapped and the result
1124 // is in the 1st element of the array.
1126 euclidInv(yval
, xval
% yval
, xval
/ yval
)[swapped ?
0 : 1];
1128 // Result can't be negative, so make it positive by adding the
1129 // original modulus, y.ival (not the possibly "swapped" yval).
1130 if (result
.ival
< 0)
1131 result
.ival
+= y
.ival
;
1135 // As above, force this to be a positive value via modulo math.
1136 BigInteger x
= isNegative() ?
this.mod(y
) : this;
1138 // Swap values so x > y.
1139 if (x
.compareTo(y
) < 0)
1141 result
= x
; x
= y
; y
= result
; // use 'result' as a work var
1144 // As above (for ints), result will be in the 2nd element unless
1145 // the original x and y were swapped.
1146 BigInteger rem
= new BigInteger();
1147 BigInteger quot
= new BigInteger();
1148 divide(x
, y
, quot
, rem
, FLOOR
);
1149 // quot and rem may not be in canonical form. ensure
1151 quot
.canonicalize();
1152 BigInteger
[] xy
= new BigInteger
[2];
1153 euclidInv(y
, rem
, quot
, xy
);
1154 result
= swapped ? xy
[0] : xy
[1];
1156 // Result can't be negative, so make it positive by adding the
1157 // original modulus, y (which is now x if they were swapped).
1158 if (result
.isNegative())
1159 result
= add(result
, swapped ? x
: y
, 1);
1165 public BigInteger
modPow(BigInteger exponent
, BigInteger m
)
1167 if (m
.isNegative() || m
.isZero())
1168 throw new ArithmeticException("non-positive modulo");
1170 if (exponent
.isNegative())
1171 return modInverse(m
).modPow(exponent
.negate(), m
);
1172 if (exponent
.isOne())
1175 // To do this naively by first raising this to the power of exponent
1176 // and then performing modulo m would be extremely expensive, especially
1177 // for very large numbers. The solution is found in Number Theory
1178 // where a combination of partial powers and moduli can be done easily.
1180 // We'll use the algorithm for Additive Chaining which can be found on
1181 // p. 244 of "Applied Cryptography, Second Edition" by Bruce Schneier.
1183 BigInteger t
= this;
1184 BigInteger u
= exponent
;
1188 if (u
.and(ONE
).isOne())
1189 s
= times(s
, t
).mod(m
);
1190 u
= u
.shiftRight(1);
1191 t
= times(t
, t
).mod(m
);
1197 /** Calculate Greatest Common Divisor for non-negative ints. */
1198 private static int gcd(int a
, int b
)
1200 // Euclid's algorithm, copied from libg++.
1204 tmp
= a
; a
= b
; b
= tmp
;
1218 public BigInteger
gcd(BigInteger y
)
1227 && xval
!= Integer
.MIN_VALUE
&& yval
!= Integer
.MIN_VALUE
)
1233 return valueOf(gcd(xval
, yval
));
1237 if (y
.words
== null)
1243 int len
= (xval
> yval ? xval
: yval
) + 1;
1244 int[] xwords
= new int[len
];
1245 int[] ywords
= new int[len
];
1246 getAbsolute(xwords
);
1247 y
.getAbsolute(ywords
);
1248 len
= MPN
.gcd(xwords
, ywords
, len
);
1249 BigInteger result
= new BigInteger(0);
1251 result
.words
= xwords
;
1252 return result
.canonicalize();
1256 * <p>Returns <code>true</code> if this BigInteger is probably prime,
1257 * <code>false</code> if it's definitely composite. If <code>certainty</code>
1258 * is <code><= 0</code>, <code>true</code> is returned.</p>
1260 * @param certainty a measure of the uncertainty that the caller is willing
1261 * to tolerate: if the call returns <code>true</code> the probability that
1262 * this BigInteger is prime exceeds <code>(1 - 1/2<sup>certainty</sup>)</code>.
1263 * The execution time of this method is proportional to the value of this
1265 * @return <code>true</code> if this BigInteger is probably prime,
1266 * <code>false</code> if it's definitely composite.
1268 public boolean isProbablePrime(int certainty
)
1273 /** We'll use the Rabin-Miller algorithm for doing a probabilistic
1274 * primality test. It is fast, easy and has faster decreasing odds of a
1275 * composite passing than with other tests. This means that this
1276 * method will actually have a probability much greater than the
1277 * 1 - .5^certainty specified in the JCL (p. 117), but I don't think
1278 * anyone will complain about better performance with greater certainty.
1280 * The Rabin-Miller algorithm can be found on pp. 259-261 of "Applied
1281 * Cryptography, Second Edition" by Bruce Schneier.
1284 // First rule out small prime factors
1285 BigInteger rem
= new BigInteger();
1287 for (i
= 0; i
< primes
.length
; i
++)
1289 if (words
== null && ival
== primes
[i
])
1292 divide(this, smallFixNums
[primes
[i
] - minFixNum
], null, rem
, TRUNCATE
);
1293 if (rem
.canonicalize().isZero())
1297 // Now perform the Rabin-Miller test.
1299 // Set b to the number of times 2 evenly divides (this - 1).
1300 // I.e. 2^b is the largest power of 2 that divides (this - 1).
1301 BigInteger pMinus1
= add(this, -1);
1302 int b
= pMinus1
.getLowestSetBit();
1304 // Set m such that this = 1 + 2^b * m.
1305 BigInteger m
= pMinus1
.divide(valueOf(2L << b
- 1));
1307 // The HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Note
1308 // 4.49 (controlling the error probability) gives the number of trials
1309 // for an error probability of 1/2**80, given the number of bits in the
1310 // number to test. we shall use these numbers as is if/when 'certainty'
1311 // is less or equal to 80, and twice as much if it's greater.
1312 int bits
= this.bitLength();
1313 for (i
= 0; i
< k
.length
; i
++)
1320 for (int t
= 0; t
< trials
; t
++)
1322 // The HAC (Handbook of Applied Cryptography), Alfred Menezes & al.
1323 // Remark 4.28 states: "...A strategy that is sometimes employed
1324 // is to fix the bases a to be the first few primes instead of
1325 // choosing them at random.
1326 z
= smallFixNums
[primes
[t
] - minFixNum
].modPow(m
, this);
1327 if (z
.isOne() || z
.equals(pMinus1
))
1328 continue; // Passes the test; may be prime.
1330 for (i
= 0; i
< b
; )
1335 if (z
.equals(pMinus1
))
1336 break; // Passes the test; may be prime.
1338 z
= z
.modPow(valueOf(2), this);
1341 if (i
== b
&& !z
.equals(pMinus1
))
1347 private void setInvert()
1353 for (int i
= ival
; --i
>= 0; )
1354 words
[i
] = ~words
[i
];
1358 private void setShiftLeft(BigInteger x
, int count
)
1362 if (x
.words
== null)
1366 set((long) x
.ival
<< count
);
1369 xwords
= new int[1];
1378 int word_count
= count
>> 5;
1380 int new_len
= xlen
+ word_count
;
1384 for (int i
= xlen
; --i
>= 0; )
1385 words
[i
+word_count
] = xwords
[i
];
1391 int shift_out
= MPN
.lshift(words
, word_count
, xwords
, xlen
, count
);
1393 words
[new_len
-1] = (shift_out
<< count
) >> count
; // sign-extend.
1396 for (int i
= word_count
; --i
>= 0; )
1400 private void setShiftRight(BigInteger x
, int count
)
1402 if (x
.words
== null)
1403 set(count
< 32 ? x
.ival
>> count
: x
.ival
< 0 ?
-1 : 0);
1404 else if (count
== 0)
1408 boolean neg
= x
.isNegative();
1409 int word_count
= count
>> 5;
1411 int d_len
= x
.ival
- word_count
;
1416 if (words
== null || words
.length
< d_len
)
1418 MPN
.rshift0 (words
, x
.words
, word_count
, d_len
, count
);
1421 words
[d_len
-1] |= -2 << (31 - count
);
1426 private void setShift(BigInteger x
, int count
)
1429 setShiftLeft(x
, count
);
1431 setShiftRight(x
, -count
);
1434 private static BigInteger
shift(BigInteger x
, int count
)
1436 if (x
.words
== null)
1439 return valueOf(count
> -32 ? x
.ival
>> (-count
) : x
.ival
< 0 ?
-1 : 0);
1441 return valueOf((long) x
.ival
<< count
);
1445 BigInteger result
= new BigInteger(0);
1446 result
.setShift(x
, count
);
1447 return result
.canonicalize();
1450 public BigInteger
shiftLeft(int n
)
1452 return shift(this, n
);
1455 public BigInteger
shiftRight(int n
)
1457 return shift(this, -n
);
1460 private void format(int radix
, StringBuffer buffer
)
1463 buffer
.append(Integer
.toString(ival
, radix
));
1465 buffer
.append(Long
.toString(longValue(), radix
));
1468 boolean neg
= isNegative();
1470 if (neg
|| radix
!= 16)
1472 work
= new int[ival
];
1483 int buf_start
= buffer
.length();
1484 for (int i
= len
; --i
>= 0; )
1487 for (int j
= 8; --j
>= 0; )
1489 int hex_digit
= (word
>> (4 * j
)) & 0xF;
1490 // Suppress leading zeros:
1491 if (hex_digit
> 0 || buffer
.length() > buf_start
)
1492 buffer
.append(Character
.forDigit(hex_digit
, 16));
1498 int i
= buffer
.length();
1501 int digit
= MPN
.divmod_1(work
, work
, len
, radix
);
1502 buffer
.append(Character
.forDigit(digit
, radix
));
1503 while (len
> 0 && work
[len
-1] == 0) len
--;
1509 /* Reverse buffer. */
1510 int j
= buffer
.length() - 1;
1513 char tmp
= buffer
.charAt(i
);
1514 buffer
.setCharAt(i
, buffer
.charAt(j
));
1515 buffer
.setCharAt(j
, tmp
);
1522 public String
toString()
1524 return toString(10);
1527 public String
toString(int radix
)
1530 return Integer
.toString(ival
, radix
);
1532 return Long
.toString(longValue(), radix
);
1533 int buf_size
= ival
* (MPN
.chars_per_word(radix
) + 1);
1534 StringBuffer buffer
= new StringBuffer(buf_size
);
1535 format(radix
, buffer
);
1536 return buffer
.toString();
1539 public int intValue()
1546 public long longValue()
1552 return ((long)words
[1] << 32) + ((long)words
[0] & 0xffffffffL
);
1555 public int hashCode()
1557 // FIXME: May not match hashcode of JDK.
1558 return words
== null ? ival
: (words
[0] + words
[ival
- 1]);
1561 /* Assumes x and y are both canonicalized. */
1562 private static boolean equals(BigInteger x
, BigInteger y
)
1564 if (x
.words
== null && y
.words
== null)
1565 return x
.ival
== y
.ival
;
1566 if (x
.words
== null || y
.words
== null || x
.ival
!= y
.ival
)
1568 for (int i
= x
.ival
; --i
>= 0; )
1570 if (x
.words
[i
] != y
.words
[i
])
1576 /* Assumes this and obj are both canonicalized. */
1577 public boolean equals(Object obj
)
1579 if (! (obj
instanceof BigInteger
))
1581 return equals(this, (BigInteger
) obj
);
1584 private static BigInteger
valueOf(String s
, int radix
)
1585 throws NumberFormatException
1587 int len
= s
.length();
1588 // Testing (len < MPN.chars_per_word(radix)) would be more accurate,
1589 // but slightly more expensive, for little practical gain.
1590 if (len
<= 15 && radix
<= 16)
1591 return valueOf(Long
.parseLong(s
, radix
));
1594 byte[] bytes
= new byte[len
];
1595 boolean negative
= false;
1596 for (int i
= 0; i
< len
; i
++)
1598 char ch
= s
.charAt(i
);
1601 else if (ch
== '_' || (byte_len
== 0 && (ch
== ' ' || ch
== '\t')))
1605 int digit
= Character
.digit(ch
, radix
);
1608 bytes
[byte_len
++] = (byte) digit
;
1611 return valueOf(bytes
, byte_len
, negative
, radix
);
1614 private static BigInteger
valueOf(byte[] digits
, int byte_len
,
1615 boolean negative
, int radix
)
1617 int chars_per_word
= MPN
.chars_per_word(radix
);
1618 int[] words
= new int[byte_len
/ chars_per_word
+ 1];
1619 int size
= MPN
.set_str(words
, digits
, byte_len
, radix
);
1622 if (words
[size
-1] < 0)
1625 negate(words
, words
, size
);
1626 return make(words
, size
);
1629 public double doubleValue()
1632 return (double) ival
;
1634 return (double) longValue();
1636 return neg(this).roundToDouble(0, true, false);
1637 return roundToDouble(0, false, false);
1640 public float floatValue()
1642 return (float) doubleValue();
1645 /** Return true if any of the lowest n bits are one.
1646 * (false if n is negative). */
1647 private boolean checkBits(int n
)
1652 return n
> 31 || ((ival
& ((1 << n
) - 1)) != 0);
1654 for (i
= 0; i
< (n
>> 5) ; i
++)
1657 return (n
& 31) != 0 && (words
[i
] & ((1 << (n
& 31)) - 1)) != 0;
1660 /** Convert a semi-processed BigInteger to double.
1661 * Number must be non-negative. Multiplies by a power of two, applies sign,
1662 * and converts to double, with the usual java rounding.
1663 * @param exp power of two, positive or negative, by which to multiply
1664 * @param neg true if negative
1665 * @param remainder true if the BigInteger is the result of a truncating
1666 * division that had non-zero remainder. To ensure proper rounding in
1667 * this case, the BigInteger must have at least 54 bits. */
1668 private double roundToDouble(int exp
, boolean neg
, boolean remainder
)
1671 int il
= bitLength();
1673 // Exponent when normalized to have decimal point directly after
1674 // leading one. This is stored excess 1023 in the exponent bit field.
1677 // Gross underflow. If exp == -1075, we let the rounding
1678 // computation determine whether it is minval or 0 (which are just
1679 // 0x0000 0000 0000 0001 and 0x0000 0000 0000 0000 as bit
1682 return neg ?
-0.0 : 0.0;
1686 return neg ? Double
.NEGATIVE_INFINITY
: Double
.POSITIVE_INFINITY
;
1688 // number of bits in mantissa, including the leading one.
1689 // 53 unless it's denormalized
1690 int ml
= (exp
>= -1022 ?
53 : 53 + exp
+ 1022);
1692 // Get top ml + 1 bits. The extra one is for rounding.
1694 int excess_bits
= il
- (ml
+ 1);
1695 if (excess_bits
> 0)
1696 m
= ((words
== null) ? ival
>> excess_bits
1697 : MPN
.rshift_long(words
, ival
, excess_bits
));
1699 m
= longValue() << (- excess_bits
);
1701 // Special rounding for maxval. If the number exceeds maxval by
1702 // any amount, even if it's less than half a step, it overflows.
1703 if (exp
== 1023 && ((m
>> 1) == (1L << 53) - 1))
1705 if (remainder
|| checkBits(il
- ml
))
1706 return neg ? Double
.NEGATIVE_INFINITY
: Double
.POSITIVE_INFINITY
;
1708 return neg ?
- Double
.MAX_VALUE
: Double
.MAX_VALUE
;
1711 // Normal round-to-even rule: round up if the bit dropped is a one, and
1712 // the bit above it or any of the bits below it is a one.
1714 && ((m
& 2) == 2 || remainder
|| checkBits(excess_bits
)))
1717 // Check if we overflowed the mantissa
1718 if ((m
& (1L << 54)) != 0)
1724 // Check if a denormalized mantissa was just rounded up to a
1726 else if (ml
== 52 && (m
& (1L << 53)) != 0)
1730 // Discard the rounding bit
1733 long bits_sign
= neg ?
(1L << 63) : 0;
1735 long bits_exp
= (exp
<= 0) ?
0 : ((long)exp
) << 52;
1736 long bits_mant
= m
& ~
(1L << 52);
1737 return Double
.longBitsToDouble(bits_sign
| bits_exp
| bits_mant
);
1740 /** Copy the abolute value of this into an array of words.
1741 * Assumes words.length >= (this.words == null ? 1 : this.ival).
1742 * Result is zero-extended, but need not be a valid 2's complement number.
1744 private void getAbsolute(int[] words
)
1747 if (this.words
== null)
1750 words
[0] = this.ival
;
1755 for (int i
= len
; --i
>= 0; )
1756 words
[i
] = this.words
[i
];
1758 if (words
[len
- 1] < 0)
1759 negate(words
, words
, len
);
1760 for (int i
= words
.length
; --i
> len
; )
1764 /** Set dest[0:len-1] to the negation of src[0:len-1].
1765 * Return true if overflow (i.e. if src is -2**(32*len-1)).
1766 * Ok for src==dest. */
1767 private static boolean negate(int[] dest
, int[] src
, int len
)
1770 boolean negative
= src
[len
-1] < 0;
1771 for (int i
= 0; i
< len
; i
++)
1773 carry
+= ((long) (~src
[i
]) & 0xffffffffL
);
1774 dest
[i
] = (int) carry
;
1777 return (negative
&& dest
[len
-1] < 0);
1780 /** Destructively set this to the negative of x.
1781 * It is OK if x==this.*/
1782 private void setNegative(BigInteger x
)
1785 if (x
.words
== null)
1787 if (len
== Integer
.MIN_VALUE
)
1794 if (negate(words
, x
.words
, len
))
1799 /** Destructively negate this. */
1800 private void setNegative()
1805 private static BigInteger
abs(BigInteger x
)
1807 return x
.isNegative() ?
neg(x
) : x
;
1810 public BigInteger
abs()
1815 private static BigInteger
neg(BigInteger x
)
1817 if (x
.words
== null && x
.ival
!= Integer
.MIN_VALUE
)
1818 return valueOf(- x
.ival
);
1819 BigInteger result
= new BigInteger(0);
1820 result
.setNegative(x
);
1821 return result
.canonicalize();
1824 public BigInteger
negate()
1829 /** Calculates ceiling(log2(this < 0 ? -this : this+1))
1830 * See Common Lisp: the Language, 2nd ed, p. 361.
1832 public int bitLength()
1835 return MPN
.intLength(ival
);
1836 return MPN
.intLength(words
, ival
);
1839 public byte[] toByteArray()
1841 // Determine number of bytes needed. The method bitlength returns
1842 // the size without the sign bit, so add one bit for that and then
1843 // add 7 more to emulate the ceil function using integer math.
1844 byte[] bytes
= new byte[(bitLength() + 1 + 7) / 8];
1845 int nbytes
= bytes
.length
;
1850 // Deal with words array until one word or less is left to process.
1851 // If BigInteger is an int, then it is in ival and nbytes will be <= 4.
1854 word
= words
[wptr
++];
1855 for (int i
= 4; i
> 0; --i
, word
>>= 8)
1856 bytes
[--nbytes
] = (byte) word
;
1859 // Deal with the last few bytes. If BigInteger is an int, use ival.
1860 word
= (words
== null) ? ival
: words
[wptr
];
1861 for ( ; nbytes
> 0; word
>>= 8)
1862 bytes
[--nbytes
] = (byte) word
;
1867 /** Return the boolean opcode (for bitOp) for swapped operands.
1868 * I.e. bitOp(swappedOp(op), x, y) == bitOp(op, y, x).
1870 private static int swappedOp(int op
)
1873 "\000\001\004\005\002\003\006\007\010\011\014\015\012\013\016\017"
1877 /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
1878 private static BigInteger
bitOp(int op
, BigInteger x
, BigInteger y
)
1882 case 0: return ZERO
;
1883 case 1: return x
.and(y
);
1886 case 15: return valueOf(-1);
1888 BigInteger result
= new BigInteger();
1889 setBitOp(result
, op
, x
, y
);
1890 return result
.canonicalize();
1893 /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
1894 private static void setBitOp(BigInteger result
, int op
,
1895 BigInteger x
, BigInteger y
)
1897 if (y
.words
== null) ;
1898 else if (x
.words
== null || x
.ival
< y
.ival
)
1900 BigInteger temp
= x
; x
= y
; y
= temp
;
1906 if (y
.words
== null)
1916 if (x
.words
== null)
1927 result
.realloc(xlen
);
1928 int[] w
= result
.words
;
1930 // Code for how to handle the remainder of x.
1931 // 0: Truncate to length of y.
1932 // 1: Copy rest of x.
1933 // 2: Invert rest of x.
1945 if (i
+1 >= ylen
) break;
1946 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
1948 if (yi
< 0) finish
= 1;
1954 if (i
+1 >= ylen
) break;
1955 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
1957 if (yi
>= 0) finish
= 1;
1961 finish
= 1; // Copy rest
1967 if (i
+1 >= ylen
) break;
1968 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
1970 if (yi
< 0) finish
= 2;
1976 if (i
+1 >= ylen
) break;
1977 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
1984 if (i
+1 >= ylen
) break;
1985 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
1987 finish
= yi
< 0 ?
2 : 1;
1993 if (i
+1 >= ylen
) break;
1994 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
1996 if (yi
>= 0) finish
= 1;
2002 if (i
+1 >= ylen
) break;
2003 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
2005 if (yi
>= 0) finish
= 2;
2007 case 9: // eqv [exclusive nor]
2011 if (i
+1 >= ylen
) break;
2012 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
2014 finish
= yi
>= 0 ?
2 : 1;
2020 if (i
+1 >= ylen
) break;
2021 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
2028 if (i
+1 >= ylen
) break;
2029 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
2031 if (yi
< 0) finish
= 1;
2041 if (i
+1 >= ylen
) break;
2042 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
2044 if (yi
>= 0) finish
= 2;
2050 if (i
+1 >= ylen
) break;
2051 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
2053 if (yi
< 0) finish
= 2;
2060 // Here i==ylen-1; w[0]..w[i-1] have the correct result;
2061 // and ni contains the correct result for w[i+1].
2067 if (i
== 0 && w
== null)
2074 case 1: w
[i
] = ni
; while (++i
< xlen
) w
[i
] = x
.words
[i
]; break;
2075 case 2: w
[i
] = ni
; while (++i
< xlen
) w
[i
] = ~x
.words
[i
]; break;
2080 /** Return the logical (bit-wise) "and" of a BigInteger and an int. */
2081 private static BigInteger
and(BigInteger x
, int y
)
2083 if (x
.words
== null)
2084 return valueOf(x
.ival
& y
);
2086 return valueOf(x
.words
[0] & y
);
2088 int[] words
= new int[len
];
2089 words
[0] = x
.words
[0] & y
;
2091 words
[len
] = x
.words
[len
];
2092 return make(words
, x
.ival
);
2095 /** Return the logical (bit-wise) "and" of two BigIntegers. */
2096 public BigInteger
and(BigInteger y
)
2098 if (y
.words
== null)
2099 return and(this, y
.ival
);
2100 else if (words
== null)
2101 return and(y
, ival
);
2103 BigInteger x
= this;
2106 BigInteger temp
= this; x
= y
; y
= temp
;
2109 int len
= y
.isNegative() ? x
.ival
: y
.ival
;
2110 int[] words
= new int[len
];
2111 for (i
= 0; i
< y
.ival
; i
++)
2112 words
[i
] = x
.words
[i
] & y
.words
[i
];
2113 for ( ; i
< len
; i
++)
2114 words
[i
] = x
.words
[i
];
2115 return make(words
, len
);
2118 /** Return the logical (bit-wise) "(inclusive) or" of two BigIntegers. */
2119 public BigInteger
or(BigInteger y
)
2121 return bitOp(7, this, y
);
2124 /** Return the logical (bit-wise) "exclusive or" of two BigIntegers. */
2125 public BigInteger
xor(BigInteger y
)
2127 return bitOp(6, this, y
);
2130 /** Return the logical (bit-wise) negation of a BigInteger. */
2131 public BigInteger
not()
2133 return bitOp(12, this, ZERO
);
2136 public BigInteger
andNot(BigInteger val
)
2138 return and(val
.not());
2141 public BigInteger
clearBit(int n
)
2144 throw new ArithmeticException();
2146 return and(ONE
.shiftLeft(n
).not());
2149 public BigInteger
setBit(int n
)
2152 throw new ArithmeticException();
2154 return or(ONE
.shiftLeft(n
));
2157 public boolean testBit(int n
)
2160 throw new ArithmeticException();
2162 return !and(ONE
.shiftLeft(n
)).isZero();
2165 public BigInteger
flipBit(int n
)
2168 throw new ArithmeticException();
2170 return xor(ONE
.shiftLeft(n
));
2173 public int getLowestSetBit()
2179 return MPN
.findLowestBit(ival
);
2181 return MPN
.findLowestBit(words
);
2184 // bit4count[I] is number of '1' bits in I.
2185 private static final byte[] bit4_count
= { 0, 1, 1, 2, 1, 2, 2, 3,
2186 1, 2, 2, 3, 2, 3, 3, 4};
2188 private static int bitCount(int i
)
2193 count
+= bit4_count
[i
& 15];
2199 private static int bitCount(int[] x
, int len
)
2203 count
+= bitCount(x
[len
]);
2207 /** Count one bits in a BigInteger.
2208 * If argument is negative, count zero bits instead. */
2209 public int bitCount()
2212 int[] x_words
= words
;
2213 if (x_words
== null)
2221 i
= bitCount(x_words
, x_len
);
2223 return isNegative() ? x_len
* 32 - i
: i
;
2226 private void readObject(ObjectInputStream s
)
2227 throws IOException
, ClassNotFoundException
2229 s
.defaultReadObject();
2230 if (magnitude
.length
== 0 || signum
== 0)
2237 words
= byteArrayToIntArray(magnitude
, signum
< 0 ?
-1 : 0);
2238 BigInteger result
= make(words
, words
.length
);
2239 this.ival
= result
.ival
;
2240 this.words
= result
.words
;
2244 private void writeObject(ObjectOutputStream s
)
2245 throws IOException
, ClassNotFoundException
2248 magnitude
= signum
== 0 ?
new byte[0] : toByteArray();
2249 s
.defaultWriteObject();