1 /* java.math.BigInteger -- Arbitary precision integers
2 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003 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., 59 Temple Place, Suite 330, 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. */
40 import gnu
.java
.math
.MPN
;
41 import java
.util
.Random
;
42 import java
.io
.ObjectInputStream
;
43 import java
.io
.ObjectOutputStream
;
44 import java
.io
.IOException
;
47 * @author Warren Levy <warrenl@cygnus.com>
48 * @date December 20, 1999.
52 * Written using on-line Java Platform 1.2 API Specification, as well
53 * as "The Java Class Libraries", 2nd edition (Addison-Wesley, 1998) and
54 * "Applied Cryptography, Second Edition" by Bruce Schneier (Wiley, 1996).
56 * Based primarily on IntNum.java BitOps.java by Per Bothner <per@bothner.com>
57 * (found in Kawa 1.6.62).
59 * Status: Believed complete and correct.
62 public class BigInteger
extends Number
implements Comparable
64 /** All integers are stored in 2's-complement form.
65 * If words == null, the ival is the value of this BigInteger.
66 * Otherwise, the first ival elements of words make the value
67 * of this BigInteger, stored in little-endian order, 2's-complement form. */
68 transient private int ival
;
69 transient private int[] words
;
71 // Serialization fields.
72 private int bitCount
= -1;
73 private int bitLength
= -1;
74 private int firstNonzeroByteNum
= -2;
75 private int lowestSetBit
= -2;
76 private byte[] magnitude
;
78 private static final long serialVersionUID
= -8287574255936472291L;
81 /** We pre-allocate integers in the range minFixNum..maxFixNum. */
82 private static final int minFixNum
= -100;
83 private static final int maxFixNum
= 1024;
84 private static final int numFixNum
= maxFixNum
-minFixNum
+1;
85 private static final BigInteger
[] smallFixNums
= new BigInteger
[numFixNum
];
88 for (int i
= numFixNum
; --i
>= 0; )
89 smallFixNums
[i
] = new BigInteger(i
+ minFixNum
);
93 public static final BigInteger ZERO
= smallFixNums
[-minFixNum
];
96 public static final BigInteger ONE
= smallFixNums
[1 - minFixNum
];
99 private static final int FLOOR
= 1;
100 private static final int CEILING
= 2;
101 private static final int TRUNCATE
= 3;
102 private static final int ROUND
= 4;
104 /** When checking the probability of primes, it is most efficient to
105 * first check the factoring of small primes, so we'll use this array.
107 private static final int[] primes
=
108 { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
109 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
110 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181,
111 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251 };
113 /** HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Table 4.4. */
114 private static final int[] k
=
115 {100,150,200,250,300,350,400,500,600,800,1250, Integer
.MAX_VALUE
};
116 private static final int[] t
=
117 { 27, 18, 15, 12, 9, 8, 7, 6, 5, 4, 3, 2};
123 /* Create a new (non-shared) BigInteger, and initialize to an int. */
124 private BigInteger(int value
)
129 public BigInteger(String val
, int radix
)
131 BigInteger result
= valueOf(val
, radix
);
132 this.ival
= result
.ival
;
133 this.words
= result
.words
;
136 public BigInteger(String val
)
141 /* Create a new (non-shared) BigInteger, and initialize from a byte array. */
142 public BigInteger(byte[] val
)
144 if (val
== null || val
.length
< 1)
145 throw new NumberFormatException();
147 words
= byteArrayToIntArray(val
, val
[0] < 0 ?
-1 : 0);
148 BigInteger result
= make(words
, words
.length
);
149 this.ival
= result
.ival
;
150 this.words
= result
.words
;
153 public BigInteger(int signum
, byte[] magnitude
)
155 if (magnitude
== null || signum
> 1 || signum
< -1)
156 throw new NumberFormatException();
161 for (i
= magnitude
.length
- 1; i
>= 0 && magnitude
[i
] == 0; --i
)
164 throw new NumberFormatException();
168 // Magnitude is always positive, so don't ever pass a sign of -1.
169 words
= byteArrayToIntArray(magnitude
, 0);
170 BigInteger result
= make(words
, words
.length
);
171 this.ival
= result
.ival
;
172 this.words
= result
.words
;
178 public BigInteger(int numBits
, Random rnd
)
181 throw new IllegalArgumentException();
186 private void init(int numBits
, Random rnd
)
188 int highbits
= numBits
& 31;
190 highbits
= rnd
.nextInt() >>> (32 - highbits
);
191 int nwords
= numBits
/ 32;
193 while (highbits
== 0 && nwords
> 0)
195 highbits
= rnd
.nextInt();
198 if (nwords
== 0 && highbits
>= 0)
204 ival
= highbits
< 0 ? nwords
+ 2 : nwords
+ 1;
205 words
= new int[ival
];
206 words
[nwords
] = highbits
;
207 while (--nwords
>= 0)
208 words
[nwords
] = rnd
.nextInt();
212 public BigInteger(int bitLength
, int certainty
, Random rnd
)
214 this(bitLength
, rnd
);
216 // Keep going until we find a probable prime.
219 if (isProbablePrime(certainty
))
222 init(bitLength
, rnd
);
227 * Return a BigInteger that is bitLength bits long with a
228 * probability < 2^-100 of being composite.
230 * @param bitLength length in bits of resulting number
231 * @param rnd random number generator to use
232 * @throws ArithmeticException if bitLength < 2
235 public static BigInteger
probablePrime(int bitLength
, Random rnd
)
238 throw new ArithmeticException();
240 return new BigInteger(bitLength
, 100, rnd
);
243 /** Return a (possibly-shared) BigInteger with a given long value. */
244 public static BigInteger
valueOf(long val
)
246 if (val
>= minFixNum
&& val
<= maxFixNum
)
247 return smallFixNums
[(int) val
- minFixNum
];
250 return new BigInteger(i
);
251 BigInteger result
= alloc(2);
254 result
.words
[1] = (int)(val
>> 32);
258 /** Make a canonicalized BigInteger from an array of words.
259 * The array may be reused (without copying). */
260 private static BigInteger
make(int[] words
, int len
)
264 len
= BigInteger
.wordsNeeded(words
, len
);
266 return len
== 0 ? ZERO
: valueOf(words
[0]);
267 BigInteger num
= new BigInteger();
273 /** Convert a big-endian byte array to a little-endian array of words. */
274 private static int[] byteArrayToIntArray(byte[] bytes
, int sign
)
276 // Determine number of words needed.
277 int[] words
= new int[bytes
.length
/4 + 1];
278 int nwords
= words
.length
;
280 // Create a int out of modulo 4 high order bytes.
283 for (int i
= bytes
.length
% 4; i
> 0; --i
, bptr
++)
284 word
= (word
<< 8) | (bytes
[bptr
] & 0xff);
285 words
[--nwords
] = word
;
287 // Elements remaining in byte[] are a multiple of 4.
289 words
[--nwords
] = bytes
[bptr
++] << 24 |
290 (bytes
[bptr
++] & 0xff) << 16 |
291 (bytes
[bptr
++] & 0xff) << 8 |
292 (bytes
[bptr
++] & 0xff);
296 /** Allocate a new non-shared BigInteger.
297 * @param nwords number of words to allocate
299 private static BigInteger
alloc(int nwords
)
301 BigInteger result
= new BigInteger();
303 result
.words
= new int[nwords
];
307 /** Change words.length to nwords.
308 * We allow words.length to be upto nwords+2 without reallocating.
310 private void realloc(int nwords
)
321 else if (words
== null
322 || words
.length
< nwords
323 || words
.length
> nwords
+ 2)
325 int[] new_words
= new int [nwords
];
335 System
.arraycopy(words
, 0, new_words
, 0, ival
);
341 private final boolean isNegative()
343 return (words
== null ? ival
: words
[ival
- 1]) < 0;
348 int top
= words
== null ? ival
: words
[ival
-1];
349 if (top
== 0 && words
== null)
351 return top
< 0 ?
-1 : 1;
354 private static int compareTo(BigInteger x
, BigInteger y
)
356 if (x
.words
== null && y
.words
== null)
357 return x
.ival
< y
.ival ?
-1 : x
.ival
> y
.ival ?
1 : 0;
358 boolean x_negative
= x
.isNegative();
359 boolean y_negative
= y
.isNegative();
360 if (x_negative
!= y_negative
)
361 return x_negative ?
-1 : 1;
362 int x_len
= x
.words
== null ?
1 : x
.ival
;
363 int y_len
= y
.words
== null ?
1 : y
.ival
;
365 return (x_len
> y_len
) != x_negative ?
1 : -1;
366 return MPN
.cmp(x
.words
, y
.words
, x_len
);
370 public int compareTo(Object obj
)
372 if (obj
instanceof BigInteger
)
373 return compareTo(this, (BigInteger
) obj
);
374 throw new ClassCastException();
377 public int compareTo(BigInteger val
)
379 return compareTo(this, val
);
382 public BigInteger
min(BigInteger val
)
384 return compareTo(this, val
) < 0 ?
this : val
;
387 public BigInteger
max(BigInteger val
)
389 return compareTo(this, val
) > 0 ?
this : val
;
392 private final boolean isZero()
394 return words
== null && ival
== 0;
397 private final boolean isOne()
399 return words
== null && ival
== 1;
402 /** Calculate how many words are significant in words[0:len-1].
403 * Returns the least value x such that x>0 && words[0:x-1]==words[0:len-1],
404 * when words is viewed as a 2's complement integer.
406 private static int wordsNeeded(int[] words
, int len
)
411 int word
= words
[--i
];
414 while (i
> 0 && (word
= words
[i
- 1]) < 0)
417 if (word
!= -1) break;
422 while (word
== 0 && i
> 0 && (word
= words
[i
- 1]) >= 0) i
--;
428 private BigInteger
canonicalize()
431 && (ival
= BigInteger
.wordsNeeded(words
, ival
)) <= 1)
437 if (words
== null && ival
>= minFixNum
&& ival
<= maxFixNum
)
438 return smallFixNums
[ival
- minFixNum
];
442 /** Add two ints, yielding a BigInteger. */
443 private static final BigInteger
add(int x
, int y
)
445 return valueOf((long) x
+ (long) y
);
448 /** Add a BigInteger and an int, yielding a new BigInteger. */
449 private static BigInteger
add(BigInteger x
, int y
)
452 return BigInteger
.add(x
.ival
, y
);
453 BigInteger result
= new BigInteger(0);
455 return result
.canonicalize();
458 /** Set this to the sum of x and y.
460 private void setAdd(BigInteger x
, int y
)
464 set((long) x
.ival
+ (long) y
);
470 for (int i
= 0; i
< len
; i
++)
472 carry
+= ((long) x
.words
[i
] & 0xffffffffL
);
473 words
[i
] = (int) carry
;
476 if (x
.words
[len
- 1] < 0)
478 words
[len
] = (int) carry
;
479 ival
= wordsNeeded(words
, len
+ 1);
482 /** Destructively add an int to this. */
483 private final void setAdd(int y
)
488 /** Destructively set the value of this to a long. */
489 private final void set(long y
)
501 words
[1] = (int) (y
>> 32);
506 /** Destructively set the value of this to the given words.
507 * The words array is reused, not copied. */
508 private final void set(int[] words
, int length
)
514 /** Destructively set the value of this to that of y. */
515 private final void set(BigInteger y
)
522 System
.arraycopy(y
.words
, 0, words
, 0, y
.ival
);
527 /** Add two BigIntegers, yielding their sum as another BigInteger. */
528 private static BigInteger
add(BigInteger x
, BigInteger y
, int k
)
530 if (x
.words
== null && y
.words
== null)
531 return valueOf((long) k
* (long) y
.ival
+ (long) x
.ival
);
535 y
= BigInteger
.neg(y
);
537 y
= BigInteger
.times(y
, valueOf(k
));
540 return BigInteger
.add(y
, x
.ival
);
542 return BigInteger
.add(x
, y
.ival
);
545 { // Swap so x is longer then y.
546 BigInteger tmp
= x
; x
= y
; y
= tmp
;
548 BigInteger result
= alloc(x
.ival
+ 1);
550 long carry
= MPN
.add_n(result
.words
, x
.words
, y
.words
, i
);
551 long y_ext
= y
.words
[i
- 1] < 0 ?
0xffffffffL
: 0;
552 for (; i
< x
.ival
; i
++)
554 carry
+= ((long) x
.words
[i
] & 0xffffffffL
) + y_ext
;;
555 result
.words
[i
] = (int) carry
;
558 if (x
.words
[i
- 1] < 0)
560 result
.words
[i
] = (int) (carry
+ y_ext
);
562 return result
.canonicalize();
565 public BigInteger
add(BigInteger val
)
567 return add(this, val
, 1);
570 public BigInteger
subtract(BigInteger val
)
572 return add(this, val
, -1);
575 private static final BigInteger
times(BigInteger x
, int y
)
581 int[] xwords
= x
.words
;
584 return valueOf((long) xlen
* (long) y
);
586 BigInteger result
= BigInteger
.alloc(xlen
+ 1);
587 if (xwords
[xlen
- 1] < 0)
590 negate(result
.words
, xwords
, xlen
);
591 xwords
= result
.words
;
597 negative
= !negative
;
600 result
.words
[xlen
] = MPN
.mul_1(result
.words
, xwords
, xlen
, y
);
601 result
.ival
= xlen
+ 1;
603 result
.setNegative();
604 return result
.canonicalize();
607 private static final BigInteger
times(BigInteger x
, BigInteger y
)
610 return times(x
, y
.ival
);
612 return times(y
, x
.ival
);
613 boolean negative
= false;
621 xwords
= new int[xlen
];
622 negate(xwords
, x
.words
, xlen
);
631 negative
= !negative
;
632 ywords
= new int[ylen
];
633 negate(ywords
, y
.words
, ylen
);
637 // Swap if x is shorter then y.
640 int[] twords
= xwords
; xwords
= ywords
; ywords
= twords
;
641 int tlen
= xlen
; xlen
= ylen
; ylen
= tlen
;
643 BigInteger result
= BigInteger
.alloc(xlen
+ylen
);
644 MPN
.mul(result
.words
, xwords
, xlen
, ywords
, ylen
);
645 result
.ival
= xlen
+ylen
;
647 result
.setNegative();
648 return result
.canonicalize();
651 public BigInteger
multiply(BigInteger y
)
653 return times(this, y
);
656 private static void divide(long x
, long y
,
657 BigInteger quotient
, BigInteger remainder
,
660 boolean xNegative
, yNegative
;
664 if (x
== Long
.MIN_VALUE
)
666 divide(valueOf(x
), valueOf(y
),
667 quotient
, remainder
, rounding_mode
);
678 if (y
== Long
.MIN_VALUE
)
680 if (rounding_mode
== TRUNCATE
)
681 { // x != Long.Min_VALUE implies abs(x) < abs(y)
682 if (quotient
!= null)
684 if (remainder
!= null)
688 divide(valueOf(x
), valueOf(y
),
689 quotient
, remainder
, rounding_mode
);
699 boolean qNegative
= xNegative ^ yNegative
;
701 boolean add_one
= false;
704 switch (rounding_mode
)
710 if (qNegative
== (rounding_mode
== FLOOR
))
714 add_one
= r
> ((y
- (q
& 1)) >> 1);
718 if (quotient
!= null)
726 if (remainder
!= null)
728 // The remainder is by definition: X-Q*Y
731 // Subtract the remainder from Y.
733 // In this case, abs(Q*Y) > abs(X).
734 // So sign(remainder) = -sign(X).
735 xNegative
= ! xNegative
;
739 // If !add_one, then: abs(Q*Y) <= abs(X).
740 // So sign(remainder) = sign(X).
748 /** Divide two integers, yielding quotient and remainder.
749 * @param x the numerator in the division
750 * @param y the denominator in the division
751 * @param quotient is set to the quotient of the result (iff quotient!=null)
752 * @param remainder is set to the remainder of the result
753 * (iff remainder!=null)
754 * @param rounding_mode one of FLOOR, CEILING, TRUNCATE, or ROUND.
756 private static void divide(BigInteger x
, BigInteger y
,
757 BigInteger quotient
, BigInteger remainder
,
760 if ((x
.words
== null || x
.ival
<= 2)
761 && (y
.words
== null || y
.ival
<= 2))
763 long x_l
= x
.longValue();
764 long y_l
= y
.longValue();
765 if (x_l
!= Long
.MIN_VALUE
&& y_l
!= Long
.MIN_VALUE
)
767 divide(x_l
, y_l
, quotient
, remainder
, rounding_mode
);
772 boolean xNegative
= x
.isNegative();
773 boolean yNegative
= y
.isNegative();
774 boolean qNegative
= xNegative ^ yNegative
;
776 int ylen
= y
.words
== null ?
1 : y
.ival
;
777 int[] ywords
= new int[ylen
];
778 y
.getAbsolute(ywords
);
779 while (ylen
> 1 && ywords
[ylen
- 1] == 0) ylen
--;
781 int xlen
= x
.words
== null ?
1 : x
.ival
;
782 int[] xwords
= new int[xlen
+2];
783 x
.getAbsolute(xwords
);
784 while (xlen
> 1 && xwords
[xlen
-1] == 0) xlen
--;
788 int cmpval
= MPN
.cmp(xwords
, xlen
, ywords
, ylen
);
789 if (cmpval
< 0) // abs(x) < abs(y)
790 { // quotient = 0; remainder = num.
791 int[] rwords
= xwords
; xwords
= ywords
; ywords
= rwords
;
792 rlen
= xlen
; qlen
= 1; xwords
[0] = 0;
794 else if (cmpval
== 0) // abs(x) == abs(y)
796 xwords
[0] = 1; qlen
= 1; // quotient = 1
797 ywords
[0] = 0; rlen
= 1; // remainder = 0;
802 // Need to leave room for a word of leading zeros if dividing by 1
803 // and the dividend has the high bit set. It might be safe to
804 // increment qlen in all cases, but it certainly is only necessary
805 // in the following case.
806 if (ywords
[0] == 1 && xwords
[xlen
-1] < 0)
809 ywords
[0] = MPN
.divmod_1(xwords
, xwords
, xlen
, ywords
[0]);
811 else // abs(x) > abs(y)
813 // Normalize the denominator, i.e. make its most significant bit set by
814 // shifting it normalization_steps bits to the left. Also shift the
815 // numerator the same number of steps (to keep the quotient the same!).
817 int nshift
= MPN
.count_leading_zeros(ywords
[ylen
- 1]);
820 // Shift up the denominator setting the most significant bit of
821 // the most significant word.
822 MPN
.lshift(ywords
, 0, ywords
, ylen
, nshift
);
824 // Shift up the numerator, possibly introducing a new most
826 int x_high
= MPN
.lshift(xwords
, 0, xwords
, xlen
, nshift
);
827 xwords
[xlen
++] = x_high
;
832 MPN
.divide(xwords
, xlen
, ywords
, ylen
);
834 MPN
.rshift0 (ywords
, xwords
, 0, rlen
, nshift
);
836 qlen
= xlen
+ 1 - ylen
;
837 if (quotient
!= null)
839 for (int i
= 0; i
< qlen
; i
++)
840 xwords
[i
] = xwords
[i
+ylen
];
844 if (ywords
[rlen
-1] < 0)
850 // Now the quotient is in xwords, and the remainder is in ywords.
852 boolean add_one
= false;
853 if (rlen
> 1 || ywords
[0] != 0)
854 { // Non-zero remainder i.e. in-exact quotient.
855 switch (rounding_mode
)
861 if (qNegative
== (rounding_mode
== FLOOR
))
865 // int cmp = compareTo(remainder<<1, abs(y));
866 BigInteger tmp
= remainder
== null ?
new BigInteger() : remainder
;
867 tmp
.set(ywords
, rlen
);
871 int cmp
= compareTo(tmp
, y
);
872 // Now cmp == compareTo(sign(y)*(remainder<<1), y)
875 add_one
= (cmp
== 1) || (cmp
== 0 && (xwords
[0]&1) != 0);
878 if (quotient
!= null)
880 quotient
.set(xwords
, qlen
);
883 if (add_one
) // -(quotient + 1) == ~(quotient)
884 quotient
.setInvert();
886 quotient
.setNegative();
891 if (remainder
!= null)
893 // The remainder is by definition: X-Q*Y
894 remainder
.set(ywords
, rlen
);
897 // Subtract the remainder from Y:
898 // abs(R) = abs(Y) - abs(orig_rem) = -(abs(orig_rem) - abs(Y)).
903 tmp
.set(yNegative ? ywords
[0] + y
.ival
: ywords
[0] - y
.ival
);
906 tmp
= BigInteger
.add(remainder
, y
, yNegative ?
1 : -1);
908 // In this case, abs(Q) = 1 + floor(abs(X)/abs(Y)).
909 // Hence, abs(Q*Y) > abs(X).
910 // So sign(remainder) = -sign(X).
912 remainder
.setNegative(tmp
);
918 // If !add_one, then: abs(Q*Y) <= abs(X).
919 // So sign(remainder) = sign(X).
921 remainder
.setNegative();
926 public BigInteger
divide(BigInteger val
)
929 throw new ArithmeticException("divisor is zero");
931 BigInteger quot
= new BigInteger();
932 divide(this, val
, quot
, null, TRUNCATE
);
933 return quot
.canonicalize();
936 public BigInteger
remainder(BigInteger val
)
939 throw new ArithmeticException("divisor is zero");
941 BigInteger rem
= new BigInteger();
942 divide(this, val
, null, rem
, TRUNCATE
);
943 return rem
.canonicalize();
946 public BigInteger
[] divideAndRemainder(BigInteger val
)
949 throw new ArithmeticException("divisor is zero");
951 BigInteger
[] result
= new BigInteger
[2];
952 result
[0] = new BigInteger();
953 result
[1] = new BigInteger();
954 divide(this, val
, result
[0], result
[1], TRUNCATE
);
955 result
[0].canonicalize();
956 result
[1].canonicalize();
960 public BigInteger
mod(BigInteger m
)
962 if (m
.isNegative() || m
.isZero())
963 throw new ArithmeticException("non-positive modulus");
965 BigInteger rem
= new BigInteger();
966 divide(this, m
, null, rem
, FLOOR
);
967 return rem
.canonicalize();
970 /** Calculate the integral power of a BigInteger.
971 * @param exponent the exponent (must be non-negative)
973 public BigInteger
pow(int exponent
)
979 throw new ArithmeticException("negative exponent");
983 int plen
= words
== null ?
1 : ival
; // Length of pow2.
984 int blen
= ((bitLength() * exponent
) >> 5) + 2 * plen
;
985 boolean negative
= isNegative() && (exponent
& 1) != 0;
986 int[] pow2
= new int [blen
];
987 int[] rwords
= new int [blen
];
988 int[] work
= new int [blen
];
989 getAbsolute(pow2
); // pow2 = abs(this);
991 rwords
[0] = 1; // rwords = 1;
992 for (;;) // for (i = 0; ; i++)
994 // pow2 == this**(2**i)
995 // prod = this**(sum(j=0..i-1, (exponent>>j)&1))
996 if ((exponent
& 1) != 0)
998 MPN
.mul(work
, pow2
, plen
, rwords
, rlen
);
999 int[] temp
= work
; work
= rwords
; rwords
= temp
;
1001 while (rwords
[rlen
- 1] == 0) rlen
--;
1007 MPN
.mul(work
, pow2
, plen
, pow2
, plen
);
1008 int[] temp
= work
; work
= pow2
; pow2
= temp
; // swap to avoid a copy
1010 while (pow2
[plen
- 1] == 0) plen
--;
1012 if (rwords
[rlen
- 1] < 0)
1015 negate(rwords
, rwords
, rlen
);
1016 return BigInteger
.make(rwords
, rlen
);
1019 private static final int[] euclidInv(int a
, int b
, int prevDiv
)
1022 throw new ArithmeticException("not invertible");
1025 // Success: values are indeed invertible!
1026 // Bottom of the recursion reached; start unwinding.
1027 return new int[] { -prevDiv
, 1 };
1029 int[] xy
= euclidInv(b
, a
% b
, a
/ b
); // Recursion happens here.
1030 a
= xy
[0]; // use our local copy of 'a' as a work var
1031 xy
[0] = a
* -prevDiv
+ xy
[1];
1036 private static final void euclidInv(BigInteger a
, BigInteger b
,
1037 BigInteger prevDiv
, BigInteger
[] xy
)
1040 throw new ArithmeticException("not invertible");
1044 // Success: values are indeed invertible!
1045 // Bottom of the recursion reached; start unwinding.
1046 xy
[0] = neg(prevDiv
);
1051 // Recursion happens in the following conditional!
1053 // If a just contains an int, then use integer math for the rest.
1054 if (a
.words
== null)
1056 int[] xyInt
= euclidInv(b
.ival
, a
.ival
% b
.ival
, a
.ival
/ b
.ival
);
1057 xy
[0] = new BigInteger(xyInt
[0]);
1058 xy
[1] = new BigInteger(xyInt
[1]);
1062 BigInteger rem
= new BigInteger();
1063 BigInteger quot
= new BigInteger();
1064 divide(a
, b
, quot
, rem
, FLOOR
);
1065 // quot and rem may not be in canonical form. ensure
1067 quot
.canonicalize();
1068 euclidInv(b
, rem
, quot
, xy
);
1071 BigInteger t
= xy
[0];
1072 xy
[0] = add(xy
[1], times(t
, prevDiv
), -1);
1076 public BigInteger
modInverse(BigInteger y
)
1078 if (y
.isNegative() || y
.isZero())
1079 throw new ArithmeticException("non-positive modulo");
1081 // Degenerate cases.
1087 // Use Euclid's algorithm as in gcd() but do this recursively
1088 // rather than in a loop so we can use the intermediate results as we
1089 // unwind from the recursion.
1090 // Used http://www.math.nmsu.edu/~crypto/EuclideanAlgo.html as reference.
1091 BigInteger result
= new BigInteger();
1092 boolean swapped
= false;
1094 if (y
.words
== null)
1096 // The result is guaranteed to be less than the modulus, y (which is
1097 // an int), so simplify this by working with the int result of this
1098 // modulo y. Also, if this is negative, make it positive via modulo
1099 // math. Note that BigInteger.mod() must be used even if this is
1100 // already an int as the % operator would provide a negative result if
1101 // this is negative, BigInteger.mod() never returns negative values.
1102 int xval
= (words
!= null || isNegative()) ?
mod(y
).ival
: ival
;
1105 // Swap values so x > y.
1108 int tmp
= xval
; xval
= yval
; yval
= tmp
;
1111 // Normally, the result is in the 2nd element of the array, but
1112 // if originally x < y, then x and y were swapped and the result
1113 // is in the 1st element of the array.
1115 euclidInv(yval
, xval
% yval
, xval
/ yval
)[swapped ?
0 : 1];
1117 // Result can't be negative, so make it positive by adding the
1118 // original modulus, y.ival (not the possibly "swapped" yval).
1119 if (result
.ival
< 0)
1120 result
.ival
+= y
.ival
;
1124 // As above, force this to be a positive value via modulo math.
1125 BigInteger x
= isNegative() ?
this.mod(y
) : this;
1127 // Swap values so x > y.
1128 if (x
.compareTo(y
) < 0)
1130 result
= x
; x
= y
; y
= result
; // use 'result' as a work var
1133 // As above (for ints), result will be in the 2nd element unless
1134 // the original x and y were swapped.
1135 BigInteger rem
= new BigInteger();
1136 BigInteger quot
= new BigInteger();
1137 divide(x
, y
, quot
, rem
, FLOOR
);
1138 // quot and rem may not be in canonical form. ensure
1140 quot
.canonicalize();
1141 BigInteger
[] xy
= new BigInteger
[2];
1142 euclidInv(y
, rem
, quot
, xy
);
1143 result
= swapped ? xy
[0] : xy
[1];
1145 // Result can't be negative, so make it positive by adding the
1146 // original modulus, y (which is now x if they were swapped).
1147 if (result
.isNegative())
1148 result
= add(result
, swapped ? x
: y
, 1);
1154 public BigInteger
modPow(BigInteger exponent
, BigInteger m
)
1156 if (m
.isNegative() || m
.isZero())
1157 throw new ArithmeticException("non-positive modulo");
1159 if (exponent
.isNegative())
1160 return modInverse(m
);
1161 if (exponent
.isOne())
1164 // To do this naively by first raising this to the power of exponent
1165 // and then performing modulo m would be extremely expensive, especially
1166 // for very large numbers. The solution is found in Number Theory
1167 // where a combination of partial powers and moduli can be done easily.
1169 // We'll use the algorithm for Additive Chaining which can be found on
1170 // p. 244 of "Applied Cryptography, Second Edition" by Bruce Schneier.
1172 BigInteger t
= this;
1173 BigInteger u
= exponent
;
1177 if (u
.and(ONE
).isOne())
1178 s
= times(s
, t
).mod(m
);
1179 u
= u
.shiftRight(1);
1180 t
= times(t
, t
).mod(m
);
1186 /** Calculate Greatest Common Divisor for non-negative ints. */
1187 private static final int gcd(int a
, int b
)
1189 // Euclid's algorithm, copied from libg++.
1193 tmp
= a
; a
= b
; b
= tmp
;
1207 public BigInteger
gcd(BigInteger y
)
1216 && xval
!= Integer
.MIN_VALUE
&& yval
!= Integer
.MIN_VALUE
)
1222 return valueOf(gcd(xval
, yval
));
1226 if (y
.words
== null)
1232 int len
= (xval
> yval ? xval
: yval
) + 1;
1233 int[] xwords
= new int[len
];
1234 int[] ywords
= new int[len
];
1235 getAbsolute(xwords
);
1236 y
.getAbsolute(ywords
);
1237 len
= MPN
.gcd(xwords
, ywords
, len
);
1238 BigInteger result
= new BigInteger(0);
1240 result
.words
= xwords
;
1241 return result
.canonicalize();
1245 * <p>Returns <code>true</code> if this BigInteger is probably prime,
1246 * <code>false</code> if it's definitely composite. If <code>certainty</code>
1247 * is <code><= 0</code>, <code>true</code> is returned.</p>
1249 * @param certainty a measure of the uncertainty that the caller is willing
1250 * to tolerate: if the call returns <code>true</code> the probability that
1251 * this BigInteger is prime exceeds <code>(1 - 1/2<sup>certainty</sup>)</code>.
1252 * The execution time of this method is proportional to the value of this
1254 * @return <code>true</code> if this BigInteger is probably prime,
1255 * <code>false</code> if it's definitely composite.
1257 public boolean isProbablePrime(int certainty
)
1262 /** We'll use the Rabin-Miller algorithm for doing a probabilistic
1263 * primality test. It is fast, easy and has faster decreasing odds of a
1264 * composite passing than with other tests. This means that this
1265 * method will actually have a probability much greater than the
1266 * 1 - .5^certainty specified in the JCL (p. 117), but I don't think
1267 * anyone will complain about better performance with greater certainty.
1269 * The Rabin-Miller algorithm can be found on pp. 259-261 of "Applied
1270 * Cryptography, Second Edition" by Bruce Schneier.
1273 // First rule out small prime factors
1274 BigInteger rem
= new BigInteger();
1276 for (i
= 0; i
< primes
.length
; i
++)
1278 if (words
== null && ival
== primes
[i
])
1281 divide(this, smallFixNums
[primes
[i
] - minFixNum
], null, rem
, TRUNCATE
);
1282 if (rem
.canonicalize().isZero())
1286 // Now perform the Rabin-Miller test.
1288 // Set b to the number of times 2 evenly divides (this - 1).
1289 // I.e. 2^b is the largest power of 2 that divides (this - 1).
1290 BigInteger pMinus1
= add(this, -1);
1291 int b
= pMinus1
.getLowestSetBit();
1293 // Set m such that this = 1 + 2^b * m.
1294 BigInteger m
= pMinus1
.divide(valueOf(2L << b
- 1));
1296 // The HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Note
1297 // 4.49 (controlling the error probability) gives the number of trials
1298 // for an error probability of 1/2**80, given the number of bits in the
1299 // number to test. we shall use these numbers as is if/when 'certainty'
1300 // is less or equal to 80, and twice as much if it's greater.
1301 int bits
= this.bitLength();
1302 for (i
= 0; i
< k
.length
; i
++)
1309 for (int t
= 0; t
< trials
; t
++)
1311 // The HAC (Handbook of Applied Cryptography), Alfred Menezes & al.
1312 // Remark 4.28 states: "...A strategy that is sometimes employed
1313 // is to fix the bases a to be the first few primes instead of
1314 // choosing them at random.
1315 z
= smallFixNums
[primes
[t
] - minFixNum
].modPow(m
, this);
1316 if (z
.isOne() || z
.equals(pMinus1
))
1317 continue; // Passes the test; may be prime.
1319 for (i
= 0; i
< b
; )
1324 if (z
.equals(pMinus1
))
1325 break; // Passes the test; may be prime.
1327 z
= z
.modPow(valueOf(2), this);
1330 if (i
== b
&& !z
.equals(pMinus1
))
1336 private void setInvert()
1342 for (int i
= ival
; --i
>= 0; )
1343 words
[i
] = ~words
[i
];
1347 private void setShiftLeft(BigInteger x
, int count
)
1351 if (x
.words
== null)
1355 set((long) x
.ival
<< count
);
1358 xwords
= new int[1];
1367 int word_count
= count
>> 5;
1369 int new_len
= xlen
+ word_count
;
1373 for (int i
= xlen
; --i
>= 0; )
1374 words
[i
+word_count
] = xwords
[i
];
1380 int shift_out
= MPN
.lshift(words
, word_count
, xwords
, xlen
, count
);
1382 words
[new_len
-1] = (shift_out
<< count
) >> count
; // sign-extend.
1385 for (int i
= word_count
; --i
>= 0; )
1389 private void setShiftRight(BigInteger x
, int count
)
1391 if (x
.words
== null)
1392 set(count
< 32 ? x
.ival
>> count
: x
.ival
< 0 ?
-1 : 0);
1393 else if (count
== 0)
1397 boolean neg
= x
.isNegative();
1398 int word_count
= count
>> 5;
1400 int d_len
= x
.ival
- word_count
;
1405 if (words
== null || words
.length
< d_len
)
1407 MPN
.rshift0 (words
, x
.words
, word_count
, d_len
, count
);
1410 words
[d_len
-1] |= -2 << (31 - count
);
1415 private void setShift(BigInteger x
, int count
)
1418 setShiftLeft(x
, count
);
1420 setShiftRight(x
, -count
);
1423 private static BigInteger
shift(BigInteger x
, int count
)
1425 if (x
.words
== null)
1428 return valueOf(count
> -32 ? x
.ival
>> (-count
) : x
.ival
< 0 ?
-1 : 0);
1430 return valueOf((long) x
.ival
<< count
);
1434 BigInteger result
= new BigInteger(0);
1435 result
.setShift(x
, count
);
1436 return result
.canonicalize();
1439 public BigInteger
shiftLeft(int n
)
1441 return shift(this, n
);
1444 public BigInteger
shiftRight(int n
)
1446 return shift(this, -n
);
1449 private void format(int radix
, StringBuffer buffer
)
1452 buffer
.append(Integer
.toString(ival
, radix
));
1454 buffer
.append(Long
.toString(longValue(), radix
));
1457 boolean neg
= isNegative();
1459 if (neg
|| radix
!= 16)
1461 work
= new int[ival
];
1472 int buf_start
= buffer
.length();
1473 for (int i
= len
; --i
>= 0; )
1476 for (int j
= 8; --j
>= 0; )
1478 int hex_digit
= (word
>> (4 * j
)) & 0xF;
1479 // Suppress leading zeros:
1480 if (hex_digit
> 0 || buffer
.length() > buf_start
)
1481 buffer
.append(Character
.forDigit(hex_digit
, 16));
1487 int i
= buffer
.length();
1490 int digit
= MPN
.divmod_1(work
, work
, len
, radix
);
1491 buffer
.append(Character
.forDigit(digit
, radix
));
1492 while (len
> 0 && work
[len
-1] == 0) len
--;
1498 /* Reverse buffer. */
1499 int j
= buffer
.length() - 1;
1502 char tmp
= buffer
.charAt(i
);
1503 buffer
.setCharAt(i
, buffer
.charAt(j
));
1504 buffer
.setCharAt(j
, tmp
);
1511 public String
toString()
1513 return toString(10);
1516 public String
toString(int radix
)
1519 return Integer
.toString(ival
, radix
);
1521 return Long
.toString(longValue(), radix
);
1522 int buf_size
= ival
* (MPN
.chars_per_word(radix
) + 1);
1523 StringBuffer buffer
= new StringBuffer(buf_size
);
1524 format(radix
, buffer
);
1525 return buffer
.toString();
1528 public int intValue()
1535 public long longValue()
1541 return ((long)words
[1] << 32) + ((long)words
[0] & 0xffffffffL
);
1544 public int hashCode()
1546 // FIXME: May not match hashcode of JDK.
1547 return words
== null ? ival
: (words
[0] + words
[ival
- 1]);
1550 /* Assumes x and y are both canonicalized. */
1551 private static boolean equals(BigInteger x
, BigInteger y
)
1553 if (x
.words
== null && y
.words
== null)
1554 return x
.ival
== y
.ival
;
1555 if (x
.words
== null || y
.words
== null || x
.ival
!= y
.ival
)
1557 for (int i
= x
.ival
; --i
>= 0; )
1559 if (x
.words
[i
] != y
.words
[i
])
1565 /* Assumes this and obj are both canonicalized. */
1566 public boolean equals(Object obj
)
1568 if (! (obj
instanceof BigInteger
))
1570 return equals(this, (BigInteger
) obj
);
1573 private static BigInteger
valueOf(String s
, int radix
)
1574 throws NumberFormatException
1576 int len
= s
.length();
1577 // Testing (len < MPN.chars_per_word(radix)) would be more accurate,
1578 // but slightly more expensive, for little practical gain.
1579 if (len
<= 15 && radix
<= 16)
1580 return valueOf(Long
.parseLong(s
, radix
));
1583 byte[] bytes
= new byte[len
];
1584 boolean negative
= false;
1585 for (int i
= 0; i
< len
; i
++)
1587 char ch
= s
.charAt(i
);
1590 else if (ch
== '_' || (byte_len
== 0 && (ch
== ' ' || ch
== '\t')))
1594 int digit
= Character
.digit(ch
, radix
);
1597 bytes
[byte_len
++] = (byte) digit
;
1600 return valueOf(bytes
, byte_len
, negative
, radix
);
1603 private static BigInteger
valueOf(byte[] digits
, int byte_len
,
1604 boolean negative
, int radix
)
1606 int chars_per_word
= MPN
.chars_per_word(radix
);
1607 int[] words
= new int[byte_len
/ chars_per_word
+ 1];
1608 int size
= MPN
.set_str(words
, digits
, byte_len
, radix
);
1611 if (words
[size
-1] < 0)
1614 negate(words
, words
, size
);
1615 return make(words
, size
);
1618 public double doubleValue()
1621 return (double) ival
;
1623 return (double) longValue();
1625 return neg(this).roundToDouble(0, true, false);
1626 return roundToDouble(0, false, false);
1629 public float floatValue()
1631 return (float) doubleValue();
1634 /** Return true if any of the lowest n bits are one.
1635 * (false if n is negative). */
1636 private boolean checkBits(int n
)
1641 return n
> 31 || ((ival
& ((1 << n
) - 1)) != 0);
1643 for (i
= 0; i
< (n
>> 5) ; i
++)
1646 return (n
& 31) != 0 && (words
[i
] & ((1 << (n
& 31)) - 1)) != 0;
1649 /** Convert a semi-processed BigInteger to double.
1650 * Number must be non-negative. Multiplies by a power of two, applies sign,
1651 * and converts to double, with the usual java rounding.
1652 * @param exp power of two, positive or negative, by which to multiply
1653 * @param neg true if negative
1654 * @param remainder true if the BigInteger is the result of a truncating
1655 * division that had non-zero remainder. To ensure proper rounding in
1656 * this case, the BigInteger must have at least 54 bits. */
1657 private double roundToDouble(int exp
, boolean neg
, boolean remainder
)
1660 int il
= bitLength();
1662 // Exponent when normalized to have decimal point directly after
1663 // leading one. This is stored excess 1023 in the exponent bit field.
1666 // Gross underflow. If exp == -1075, we let the rounding
1667 // computation determine whether it is minval or 0 (which are just
1668 // 0x0000 0000 0000 0001 and 0x0000 0000 0000 0000 as bit
1671 return neg ?
-0.0 : 0.0;
1675 return neg ? Double
.NEGATIVE_INFINITY
: Double
.POSITIVE_INFINITY
;
1677 // number of bits in mantissa, including the leading one.
1678 // 53 unless it's denormalized
1679 int ml
= (exp
>= -1022 ?
53 : 53 + exp
+ 1022);
1681 // Get top ml + 1 bits. The extra one is for rounding.
1683 int excess_bits
= il
- (ml
+ 1);
1684 if (excess_bits
> 0)
1685 m
= ((words
== null) ? ival
>> excess_bits
1686 : MPN
.rshift_long(words
, ival
, excess_bits
));
1688 m
= longValue() << (- excess_bits
);
1690 // Special rounding for maxval. If the number exceeds maxval by
1691 // any amount, even if it's less than half a step, it overflows.
1692 if (exp
== 1023 && ((m
>> 1) == (1L << 53) - 1))
1694 if (remainder
|| checkBits(il
- ml
))
1695 return neg ? Double
.NEGATIVE_INFINITY
: Double
.POSITIVE_INFINITY
;
1697 return neg ?
- Double
.MAX_VALUE
: Double
.MAX_VALUE
;
1700 // Normal round-to-even rule: round up if the bit dropped is a one, and
1701 // the bit above it or any of the bits below it is a one.
1703 && ((m
& 2) == 2 || remainder
|| checkBits(excess_bits
)))
1706 // Check if we overflowed the mantissa
1707 if ((m
& (1L << 54)) != 0)
1713 // Check if a denormalized mantissa was just rounded up to a
1715 else if (ml
== 52 && (m
& (1L << 53)) != 0)
1719 // Discard the rounding bit
1722 long bits_sign
= neg ?
(1L << 63) : 0;
1724 long bits_exp
= (exp
<= 0) ?
0 : ((long)exp
) << 52;
1725 long bits_mant
= m
& ~
(1L << 52);
1726 return Double
.longBitsToDouble(bits_sign
| bits_exp
| bits_mant
);
1729 /** Copy the abolute value of this into an array of words.
1730 * Assumes words.length >= (this.words == null ? 1 : this.ival).
1731 * Result is zero-extended, but need not be a valid 2's complement number.
1733 private void getAbsolute(int[] words
)
1736 if (this.words
== null)
1739 words
[0] = this.ival
;
1744 for (int i
= len
; --i
>= 0; )
1745 words
[i
] = this.words
[i
];
1747 if (words
[len
- 1] < 0)
1748 negate(words
, words
, len
);
1749 for (int i
= words
.length
; --i
> len
; )
1753 /** Set dest[0:len-1] to the negation of src[0:len-1].
1754 * Return true if overflow (i.e. if src is -2**(32*len-1)).
1755 * Ok for src==dest. */
1756 private static boolean negate(int[] dest
, int[] src
, int len
)
1759 boolean negative
= src
[len
-1] < 0;
1760 for (int i
= 0; i
< len
; i
++)
1762 carry
+= ((long) (~src
[i
]) & 0xffffffffL
);
1763 dest
[i
] = (int) carry
;
1766 return (negative
&& dest
[len
-1] < 0);
1769 /** Destructively set this to the negative of x.
1770 * It is OK if x==this.*/
1771 private void setNegative(BigInteger x
)
1774 if (x
.words
== null)
1776 if (len
== Integer
.MIN_VALUE
)
1783 if (negate(words
, x
.words
, len
))
1788 /** Destructively negate this. */
1789 private final void setNegative()
1794 private static BigInteger
abs(BigInteger x
)
1796 return x
.isNegative() ?
neg(x
) : x
;
1799 public BigInteger
abs()
1804 private static BigInteger
neg(BigInteger x
)
1806 if (x
.words
== null && x
.ival
!= Integer
.MIN_VALUE
)
1807 return valueOf(- x
.ival
);
1808 BigInteger result
= new BigInteger(0);
1809 result
.setNegative(x
);
1810 return result
.canonicalize();
1813 public BigInteger
negate()
1818 /** Calculates ceiling(log2(this < 0 ? -this : this+1))
1819 * See Common Lisp: the Language, 2nd ed, p. 361.
1821 public int bitLength()
1824 return MPN
.intLength(ival
);
1825 return MPN
.intLength(words
, ival
);
1828 public byte[] toByteArray()
1830 // Determine number of bytes needed. The method bitlength returns
1831 // the size without the sign bit, so add one bit for that and then
1832 // add 7 more to emulate the ceil function using integer math.
1833 byte[] bytes
= new byte[(bitLength() + 1 + 7) / 8];
1834 int nbytes
= bytes
.length
;
1839 // Deal with words array until one word or less is left to process.
1840 // If BigInteger is an int, then it is in ival and nbytes will be <= 4.
1843 word
= words
[wptr
++];
1844 for (int i
= 4; i
> 0; --i
, word
>>= 8)
1845 bytes
[--nbytes
] = (byte) word
;
1848 // Deal with the last few bytes. If BigInteger is an int, use ival.
1849 word
= (words
== null) ? ival
: words
[wptr
];
1850 for ( ; nbytes
> 0; word
>>= 8)
1851 bytes
[--nbytes
] = (byte) word
;
1856 /** Return the boolean opcode (for bitOp) for swapped operands.
1857 * I.e. bitOp(swappedOp(op), x, y) == bitOp(op, y, x).
1859 private static int swappedOp(int op
)
1862 "\000\001\004\005\002\003\006\007\010\011\014\015\012\013\016\017"
1866 /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
1867 private static BigInteger
bitOp(int op
, BigInteger x
, BigInteger y
)
1871 case 0: return ZERO
;
1872 case 1: return x
.and(y
);
1875 case 15: return valueOf(-1);
1877 BigInteger result
= new BigInteger();
1878 setBitOp(result
, op
, x
, y
);
1879 return result
.canonicalize();
1882 /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
1883 private static void setBitOp(BigInteger result
, int op
,
1884 BigInteger x
, BigInteger y
)
1886 if (y
.words
== null) ;
1887 else if (x
.words
== null || x
.ival
< y
.ival
)
1889 BigInteger temp
= x
; x
= y
; y
= temp
;
1895 if (y
.words
== null)
1905 if (x
.words
== null)
1916 result
.realloc(xlen
);
1917 int[] w
= result
.words
;
1919 // Code for how to handle the remainder of x.
1920 // 0: Truncate to length of y.
1921 // 1: Copy rest of x.
1922 // 2: Invert rest of x.
1934 if (i
+1 >= ylen
) break;
1935 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
1937 if (yi
< 0) finish
= 1;
1943 if (i
+1 >= ylen
) break;
1944 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
1946 if (yi
>= 0) finish
= 1;
1950 finish
= 1; // Copy rest
1956 if (i
+1 >= ylen
) break;
1957 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
1959 if (yi
< 0) finish
= 2;
1965 if (i
+1 >= ylen
) break;
1966 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
1973 if (i
+1 >= ylen
) break;
1974 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
1976 finish
= yi
< 0 ?
2 : 1;
1982 if (i
+1 >= ylen
) break;
1983 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
1985 if (yi
>= 0) finish
= 1;
1991 if (i
+1 >= ylen
) break;
1992 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
1994 if (yi
>= 0) finish
= 2;
1996 case 9: // eqv [exclusive nor]
2000 if (i
+1 >= ylen
) break;
2001 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
2003 finish
= yi
>= 0 ?
2 : 1;
2009 if (i
+1 >= ylen
) break;
2010 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
2017 if (i
+1 >= ylen
) break;
2018 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
2020 if (yi
< 0) finish
= 1;
2030 if (i
+1 >= ylen
) break;
2031 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
2033 if (yi
>= 0) finish
= 2;
2039 if (i
+1 >= ylen
) break;
2040 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
2042 if (yi
< 0) finish
= 2;
2049 // Here i==ylen-1; w[0]..w[i-1] have the correct result;
2050 // and ni contains the correct result for w[i+1].
2056 if (i
== 0 && w
== null)
2063 case 1: w
[i
] = ni
; while (++i
< xlen
) w
[i
] = x
.words
[i
]; break;
2064 case 2: w
[i
] = ni
; while (++i
< xlen
) w
[i
] = ~x
.words
[i
]; break;
2069 /** Return the logical (bit-wise) "and" of a BigInteger and an int. */
2070 private static BigInteger
and(BigInteger x
, int y
)
2072 if (x
.words
== null)
2073 return valueOf(x
.ival
& y
);
2075 return valueOf(x
.words
[0] & y
);
2077 int[] words
= new int[len
];
2078 words
[0] = x
.words
[0] & y
;
2080 words
[len
] = x
.words
[len
];
2081 return make(words
, x
.ival
);
2084 /** Return the logical (bit-wise) "and" of two BigIntegers. */
2085 public BigInteger
and(BigInteger y
)
2087 if (y
.words
== null)
2088 return and(this, y
.ival
);
2089 else if (words
== null)
2090 return and(y
, ival
);
2092 BigInteger x
= this;
2095 BigInteger temp
= this; x
= y
; y
= temp
;
2098 int len
= y
.isNegative() ? x
.ival
: y
.ival
;
2099 int[] words
= new int[len
];
2100 for (i
= 0; i
< y
.ival
; i
++)
2101 words
[i
] = x
.words
[i
] & y
.words
[i
];
2102 for ( ; i
< len
; i
++)
2103 words
[i
] = x
.words
[i
];
2104 return make(words
, len
);
2107 /** Return the logical (bit-wise) "(inclusive) or" of two BigIntegers. */
2108 public BigInteger
or(BigInteger y
)
2110 return bitOp(7, this, y
);
2113 /** Return the logical (bit-wise) "exclusive or" of two BigIntegers. */
2114 public BigInteger
xor(BigInteger y
)
2116 return bitOp(6, this, y
);
2119 /** Return the logical (bit-wise) negation of a BigInteger. */
2120 public BigInteger
not()
2122 return bitOp(12, this, ZERO
);
2125 public BigInteger
andNot(BigInteger val
)
2127 return and(val
.not());
2130 public BigInteger
clearBit(int n
)
2133 throw new ArithmeticException();
2135 return and(ONE
.shiftLeft(n
).not());
2138 public BigInteger
setBit(int n
)
2141 throw new ArithmeticException();
2143 return or(ONE
.shiftLeft(n
));
2146 public boolean testBit(int n
)
2149 throw new ArithmeticException();
2151 return !and(ONE
.shiftLeft(n
)).isZero();
2154 public BigInteger
flipBit(int n
)
2157 throw new ArithmeticException();
2159 return xor(ONE
.shiftLeft(n
));
2162 public int getLowestSetBit()
2168 return MPN
.findLowestBit(ival
);
2170 return MPN
.findLowestBit(words
);
2173 // bit4count[I] is number of '1' bits in I.
2174 private static final byte[] bit4_count
= { 0, 1, 1, 2, 1, 2, 2, 3,
2175 1, 2, 2, 3, 2, 3, 3, 4};
2177 private static int bitCount(int i
)
2182 count
+= bit4_count
[i
& 15];
2188 private static int bitCount(int[] x
, int len
)
2192 count
+= bitCount(x
[len
]);
2196 /** Count one bits in a BigInteger.
2197 * If argument is negative, count zero bits instead. */
2198 public int bitCount()
2201 int[] x_words
= words
;
2202 if (x_words
== null)
2210 i
= bitCount(x_words
, x_len
);
2212 return isNegative() ? x_len
* 32 - i
: i
;
2215 private void readObject(ObjectInputStream s
)
2216 throws IOException
, ClassNotFoundException
2218 s
.defaultReadObject();
2219 words
= byteArrayToIntArray(magnitude
, signum
< 0 ?
-1 : 0);
2220 BigInteger result
= make(words
, words
.length
);
2221 this.ival
= result
.ival
;
2222 this.words
= result
.words
;
2225 private void writeObject(ObjectOutputStream s
)
2226 throws IOException
, ClassNotFoundException
2229 magnitude
= toByteArray();
2230 s
.defaultWriteObject();