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., 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. */
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 private static final int minFixNum
= -100;
81 private static final int maxFixNum
= 1024;
82 private static final int numFixNum
= maxFixNum
-minFixNum
+1;
83 private static final BigInteger
[] smallFixNums
= new BigInteger
[numFixNum
];
86 for (int i
= numFixNum
; --i
>= 0; )
87 smallFixNums
[i
] = new BigInteger(i
+ minFixNum
);
91 public static final BigInteger ZERO
= smallFixNums
[-minFixNum
];
94 public static final BigInteger ONE
= smallFixNums
[1 - minFixNum
];
97 private static final int FLOOR
= 1;
98 private static final int CEILING
= 2;
99 private static final int TRUNCATE
= 3;
100 private static final int ROUND
= 4;
102 /** When checking the probability of primes, it is most efficient to
103 * first check the factoring of small primes, so we'll use this array.
105 private static final int[] primes
=
106 { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
107 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
108 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181,
109 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251 };
111 /** HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Table 4.4. */
112 private static final int[] k
=
113 {100,150,200,250,300,350,400,500,600,800,1250, Integer
.MAX_VALUE
};
114 private static final int[] t
=
115 { 27, 18, 15, 12, 9, 8, 7, 6, 5, 4, 3, 2};
121 /* Create a new (non-shared) BigInteger, and initialize to an int. */
122 private BigInteger(int value
)
127 public BigInteger(String val
, int radix
)
129 BigInteger result
= valueOf(val
, radix
);
130 this.ival
= result
.ival
;
131 this.words
= result
.words
;
134 public BigInteger(String val
)
139 /* Create a new (non-shared) BigInteger, and initialize from a byte array. */
140 public BigInteger(byte[] val
)
142 if (val
== null || val
.length
< 1)
143 throw new NumberFormatException();
145 words
= byteArrayToIntArray(val
, val
[0] < 0 ?
-1 : 0);
146 BigInteger result
= make(words
, words
.length
);
147 this.ival
= result
.ival
;
148 this.words
= result
.words
;
151 public BigInteger(int signum
, byte[] magnitude
)
153 if (magnitude
== null || signum
> 1 || signum
< -1)
154 throw new NumberFormatException();
159 for (i
= magnitude
.length
- 1; i
>= 0 && magnitude
[i
] == 0; --i
)
162 throw new NumberFormatException();
166 // Magnitude is always positive, so don't ever pass a sign of -1.
167 words
= byteArrayToIntArray(magnitude
, 0);
168 BigInteger result
= make(words
, words
.length
);
169 this.ival
= result
.ival
;
170 this.words
= result
.words
;
176 public BigInteger(int numBits
, Random rnd
)
179 throw new IllegalArgumentException();
184 private void init(int numBits
, Random rnd
)
186 int highbits
= numBits
& 31;
188 highbits
= rnd
.nextInt() >>> (32 - highbits
);
189 int nwords
= numBits
/ 32;
191 while (highbits
== 0 && nwords
> 0)
193 highbits
= rnd
.nextInt();
196 if (nwords
== 0 && highbits
>= 0)
202 ival
= highbits
< 0 ? nwords
+ 2 : nwords
+ 1;
203 words
= new int[ival
];
204 words
[nwords
] = highbits
;
205 while (--nwords
>= 0)
206 words
[nwords
] = rnd
.nextInt();
210 public BigInteger(int bitLength
, int certainty
, Random rnd
)
212 this(bitLength
, rnd
);
214 // Keep going until we find a probable prime.
217 if (isProbablePrime(certainty
))
220 init(bitLength
, rnd
);
225 * Return a BigInteger that is bitLength bits long with a
226 * probability < 2^-100 of being composite.
228 * @param bitLength length in bits of resulting number
229 * @param rnd random number generator to use
230 * @throws ArithmeticException if bitLength < 2
233 public static BigInteger
probablePrime(int bitLength
, Random rnd
)
236 throw new ArithmeticException();
238 return new BigInteger(bitLength
, 100, rnd
);
241 /** Return a (possibly-shared) BigInteger with a given long value. */
242 public static BigInteger
valueOf(long val
)
244 if (val
>= minFixNum
&& val
<= maxFixNum
)
245 return smallFixNums
[(int) val
- minFixNum
];
248 return new BigInteger(i
);
249 BigInteger result
= alloc(2);
252 result
.words
[1] = (int)(val
>> 32);
256 /** Make a canonicalized BigInteger from an array of words.
257 * The array may be reused (without copying). */
258 private static BigInteger
make(int[] words
, int len
)
262 len
= BigInteger
.wordsNeeded(words
, len
);
264 return len
== 0 ? ZERO
: valueOf(words
[0]);
265 BigInteger num
= new BigInteger();
271 /** Convert a big-endian byte array to a little-endian array of words. */
272 private static int[] byteArrayToIntArray(byte[] bytes
, int sign
)
274 // Determine number of words needed.
275 int[] words
= new int[bytes
.length
/4 + 1];
276 int nwords
= words
.length
;
278 // Create a int out of modulo 4 high order bytes.
281 for (int i
= bytes
.length
% 4; i
> 0; --i
, bptr
++)
282 word
= (word
<< 8) | (bytes
[bptr
] & 0xff);
283 words
[--nwords
] = word
;
285 // Elements remaining in byte[] are a multiple of 4.
287 words
[--nwords
] = bytes
[bptr
++] << 24 |
288 (bytes
[bptr
++] & 0xff) << 16 |
289 (bytes
[bptr
++] & 0xff) << 8 |
290 (bytes
[bptr
++] & 0xff);
294 /** Allocate a new non-shared BigInteger.
295 * @param nwords number of words to allocate
297 private static BigInteger
alloc(int nwords
)
299 BigInteger result
= new BigInteger();
301 result
.words
= new int[nwords
];
305 /** Change words.length to nwords.
306 * We allow words.length to be upto nwords+2 without reallocating.
308 private void realloc(int nwords
)
319 else if (words
== null
320 || words
.length
< nwords
321 || words
.length
> nwords
+ 2)
323 int[] new_words
= new int [nwords
];
333 System
.arraycopy(words
, 0, new_words
, 0, ival
);
339 private boolean isNegative()
341 return (words
== null ? ival
: words
[ival
- 1]) < 0;
346 int top
= words
== null ? ival
: words
[ival
-1];
347 if (top
== 0 && words
== null)
349 return top
< 0 ?
-1 : 1;
352 private static int compareTo(BigInteger x
, BigInteger y
)
354 if (x
.words
== null && y
.words
== null)
355 return x
.ival
< y
.ival ?
-1 : x
.ival
> y
.ival ?
1 : 0;
356 boolean x_negative
= x
.isNegative();
357 boolean y_negative
= y
.isNegative();
358 if (x_negative
!= y_negative
)
359 return x_negative ?
-1 : 1;
360 int x_len
= x
.words
== null ?
1 : x
.ival
;
361 int y_len
= y
.words
== null ?
1 : y
.ival
;
363 return (x_len
> y_len
) != x_negative ?
1 : -1;
364 return MPN
.cmp(x
.words
, y
.words
, x_len
);
368 public int compareTo(Object obj
)
370 if (obj
instanceof BigInteger
)
371 return compareTo(this, (BigInteger
) obj
);
372 throw new ClassCastException();
375 public int compareTo(BigInteger val
)
377 return compareTo(this, val
);
380 public BigInteger
min(BigInteger val
)
382 return compareTo(this, val
) < 0 ?
this : val
;
385 public BigInteger
max(BigInteger val
)
387 return compareTo(this, val
) > 0 ?
this : val
;
390 private boolean isZero()
392 return words
== null && ival
== 0;
395 private boolean isOne()
397 return words
== null && ival
== 1;
400 /** Calculate how many words are significant in words[0:len-1].
401 * Returns the least value x such that x>0 && words[0:x-1]==words[0:len-1],
402 * when words is viewed as a 2's complement integer.
404 private static int wordsNeeded(int[] words
, int len
)
409 int word
= words
[--i
];
412 while (i
> 0 && (word
= words
[i
- 1]) < 0)
415 if (word
!= -1) break;
420 while (word
== 0 && i
> 0 && (word
= words
[i
- 1]) >= 0) i
--;
426 private BigInteger
canonicalize()
429 && (ival
= BigInteger
.wordsNeeded(words
, ival
)) <= 1)
435 if (words
== null && ival
>= minFixNum
&& ival
<= maxFixNum
)
436 return smallFixNums
[ival
- minFixNum
];
440 /** Add two ints, yielding a BigInteger. */
441 private static BigInteger
add(int x
, int y
)
443 return valueOf((long) x
+ (long) y
);
446 /** Add a BigInteger and an int, yielding a new BigInteger. */
447 private static BigInteger
add(BigInteger x
, int y
)
450 return BigInteger
.add(x
.ival
, y
);
451 BigInteger result
= new BigInteger(0);
453 return result
.canonicalize();
456 /** Set this to the sum of x and y.
458 private void setAdd(BigInteger x
, int y
)
462 set((long) x
.ival
+ (long) y
);
468 for (int i
= 0; i
< len
; i
++)
470 carry
+= ((long) x
.words
[i
] & 0xffffffffL
);
471 words
[i
] = (int) carry
;
474 if (x
.words
[len
- 1] < 0)
476 words
[len
] = (int) carry
;
477 ival
= wordsNeeded(words
, len
+ 1);
480 /** Destructively add an int to this. */
481 private void setAdd(int y
)
486 /** Destructively set the value of this to a long. */
487 private void set(long y
)
499 words
[1] = (int) (y
>> 32);
504 /** Destructively set the value of this to the given words.
505 * The words array is reused, not copied. */
506 private void set(int[] words
, int length
)
512 /** Destructively set the value of this to that of y. */
513 private void set(BigInteger y
)
520 System
.arraycopy(y
.words
, 0, words
, 0, y
.ival
);
525 /** Add two BigIntegers, yielding their sum as another BigInteger. */
526 private static BigInteger
add(BigInteger x
, BigInteger y
, int k
)
528 if (x
.words
== null && y
.words
== null)
529 return valueOf((long) k
* (long) y
.ival
+ (long) x
.ival
);
533 y
= BigInteger
.neg(y
);
535 y
= BigInteger
.times(y
, valueOf(k
));
538 return BigInteger
.add(y
, x
.ival
);
540 return BigInteger
.add(x
, y
.ival
);
543 { // Swap so x is longer then y.
544 BigInteger tmp
= x
; x
= y
; y
= tmp
;
546 BigInteger result
= alloc(x
.ival
+ 1);
548 long carry
= MPN
.add_n(result
.words
, x
.words
, y
.words
, i
);
549 long y_ext
= y
.words
[i
- 1] < 0 ?
0xffffffffL
: 0;
550 for (; i
< x
.ival
; i
++)
552 carry
+= ((long) x
.words
[i
] & 0xffffffffL
) + y_ext
;;
553 result
.words
[i
] = (int) carry
;
556 if (x
.words
[i
- 1] < 0)
558 result
.words
[i
] = (int) (carry
+ y_ext
);
560 return result
.canonicalize();
563 public BigInteger
add(BigInteger val
)
565 return add(this, val
, 1);
568 public BigInteger
subtract(BigInteger val
)
570 return add(this, val
, -1);
573 private static BigInteger
times(BigInteger x
, int y
)
579 int[] xwords
= x
.words
;
582 return valueOf((long) xlen
* (long) y
);
584 BigInteger result
= BigInteger
.alloc(xlen
+ 1);
585 if (xwords
[xlen
- 1] < 0)
588 negate(result
.words
, xwords
, xlen
);
589 xwords
= result
.words
;
595 negative
= !negative
;
598 result
.words
[xlen
] = MPN
.mul_1(result
.words
, xwords
, xlen
, y
);
599 result
.ival
= xlen
+ 1;
601 result
.setNegative();
602 return result
.canonicalize();
605 private static BigInteger
times(BigInteger x
, BigInteger y
)
608 return times(x
, y
.ival
);
610 return times(y
, x
.ival
);
611 boolean negative
= false;
619 xwords
= new int[xlen
];
620 negate(xwords
, x
.words
, xlen
);
629 negative
= !negative
;
630 ywords
= new int[ylen
];
631 negate(ywords
, y
.words
, ylen
);
635 // Swap if x is shorter then y.
638 int[] twords
= xwords
; xwords
= ywords
; ywords
= twords
;
639 int tlen
= xlen
; xlen
= ylen
; ylen
= tlen
;
641 BigInteger result
= BigInteger
.alloc(xlen
+ylen
);
642 MPN
.mul(result
.words
, xwords
, xlen
, ywords
, ylen
);
643 result
.ival
= xlen
+ylen
;
645 result
.setNegative();
646 return result
.canonicalize();
649 public BigInteger
multiply(BigInteger y
)
651 return times(this, y
);
654 private static void divide(long x
, long y
,
655 BigInteger quotient
, BigInteger remainder
,
658 boolean xNegative
, yNegative
;
662 if (x
== Long
.MIN_VALUE
)
664 divide(valueOf(x
), valueOf(y
),
665 quotient
, remainder
, rounding_mode
);
676 if (y
== Long
.MIN_VALUE
)
678 if (rounding_mode
== TRUNCATE
)
679 { // x != Long.Min_VALUE implies abs(x) < abs(y)
680 if (quotient
!= null)
682 if (remainder
!= null)
686 divide(valueOf(x
), valueOf(y
),
687 quotient
, remainder
, rounding_mode
);
697 boolean qNegative
= xNegative ^ yNegative
;
699 boolean add_one
= false;
702 switch (rounding_mode
)
708 if (qNegative
== (rounding_mode
== FLOOR
))
712 add_one
= r
> ((y
- (q
& 1)) >> 1);
716 if (quotient
!= null)
724 if (remainder
!= null)
726 // The remainder is by definition: X-Q*Y
729 // Subtract the remainder from Y.
731 // In this case, abs(Q*Y) > abs(X).
732 // So sign(remainder) = -sign(X).
733 xNegative
= ! xNegative
;
737 // If !add_one, then: abs(Q*Y) <= abs(X).
738 // So sign(remainder) = sign(X).
746 /** Divide two integers, yielding quotient and remainder.
747 * @param x the numerator in the division
748 * @param y the denominator in the division
749 * @param quotient is set to the quotient of the result (iff quotient!=null)
750 * @param remainder is set to the remainder of the result
751 * (iff remainder!=null)
752 * @param rounding_mode one of FLOOR, CEILING, TRUNCATE, or ROUND.
754 private static void divide(BigInteger x
, BigInteger y
,
755 BigInteger quotient
, BigInteger remainder
,
758 if ((x
.words
== null || x
.ival
<= 2)
759 && (y
.words
== null || y
.ival
<= 2))
761 long x_l
= x
.longValue();
762 long y_l
= y
.longValue();
763 if (x_l
!= Long
.MIN_VALUE
&& y_l
!= Long
.MIN_VALUE
)
765 divide(x_l
, y_l
, quotient
, remainder
, rounding_mode
);
770 boolean xNegative
= x
.isNegative();
771 boolean yNegative
= y
.isNegative();
772 boolean qNegative
= xNegative ^ yNegative
;
774 int ylen
= y
.words
== null ?
1 : y
.ival
;
775 int[] ywords
= new int[ylen
];
776 y
.getAbsolute(ywords
);
777 while (ylen
> 1 && ywords
[ylen
- 1] == 0) ylen
--;
779 int xlen
= x
.words
== null ?
1 : x
.ival
;
780 int[] xwords
= new int[xlen
+2];
781 x
.getAbsolute(xwords
);
782 while (xlen
> 1 && xwords
[xlen
-1] == 0) xlen
--;
786 int cmpval
= MPN
.cmp(xwords
, xlen
, ywords
, ylen
);
787 if (cmpval
< 0) // abs(x) < abs(y)
788 { // quotient = 0; remainder = num.
789 int[] rwords
= xwords
; xwords
= ywords
; ywords
= rwords
;
790 rlen
= xlen
; qlen
= 1; xwords
[0] = 0;
792 else if (cmpval
== 0) // abs(x) == abs(y)
794 xwords
[0] = 1; qlen
= 1; // quotient = 1
795 ywords
[0] = 0; rlen
= 1; // remainder = 0;
800 // Need to leave room for a word of leading zeros if dividing by 1
801 // and the dividend has the high bit set. It might be safe to
802 // increment qlen in all cases, but it certainly is only necessary
803 // in the following case.
804 if (ywords
[0] == 1 && xwords
[xlen
-1] < 0)
807 ywords
[0] = MPN
.divmod_1(xwords
, xwords
, xlen
, ywords
[0]);
809 else // abs(x) > abs(y)
811 // Normalize the denominator, i.e. make its most significant bit set by
812 // shifting it normalization_steps bits to the left. Also shift the
813 // numerator the same number of steps (to keep the quotient the same!).
815 int nshift
= MPN
.count_leading_zeros(ywords
[ylen
- 1]);
818 // Shift up the denominator setting the most significant bit of
819 // the most significant word.
820 MPN
.lshift(ywords
, 0, ywords
, ylen
, nshift
);
822 // Shift up the numerator, possibly introducing a new most
824 int x_high
= MPN
.lshift(xwords
, 0, xwords
, xlen
, nshift
);
825 xwords
[xlen
++] = x_high
;
830 MPN
.divide(xwords
, xlen
, ywords
, ylen
);
832 MPN
.rshift0 (ywords
, xwords
, 0, rlen
, nshift
);
834 qlen
= xlen
+ 1 - ylen
;
835 if (quotient
!= null)
837 for (int i
= 0; i
< qlen
; i
++)
838 xwords
[i
] = xwords
[i
+ylen
];
842 if (ywords
[rlen
-1] < 0)
848 // Now the quotient is in xwords, and the remainder is in ywords.
850 boolean add_one
= false;
851 if (rlen
> 1 || ywords
[0] != 0)
852 { // Non-zero remainder i.e. in-exact quotient.
853 switch (rounding_mode
)
859 if (qNegative
== (rounding_mode
== FLOOR
))
863 // int cmp = compareTo(remainder<<1, abs(y));
864 BigInteger tmp
= remainder
== null ?
new BigInteger() : remainder
;
865 tmp
.set(ywords
, rlen
);
869 int cmp
= compareTo(tmp
, y
);
870 // Now cmp == compareTo(sign(y)*(remainder<<1), y)
873 add_one
= (cmp
== 1) || (cmp
== 0 && (xwords
[0]&1) != 0);
876 if (quotient
!= null)
878 quotient
.set(xwords
, qlen
);
881 if (add_one
) // -(quotient + 1) == ~(quotient)
882 quotient
.setInvert();
884 quotient
.setNegative();
889 if (remainder
!= null)
891 // The remainder is by definition: X-Q*Y
892 remainder
.set(ywords
, rlen
);
895 // Subtract the remainder from Y:
896 // abs(R) = abs(Y) - abs(orig_rem) = -(abs(orig_rem) - abs(Y)).
901 tmp
.set(yNegative ? ywords
[0] + y
.ival
: ywords
[0] - y
.ival
);
904 tmp
= BigInteger
.add(remainder
, y
, yNegative ?
1 : -1);
906 // In this case, abs(Q) = 1 + floor(abs(X)/abs(Y)).
907 // Hence, abs(Q*Y) > abs(X).
908 // So sign(remainder) = -sign(X).
910 remainder
.setNegative(tmp
);
916 // If !add_one, then: abs(Q*Y) <= abs(X).
917 // So sign(remainder) = sign(X).
919 remainder
.setNegative();
924 public BigInteger
divide(BigInteger val
)
927 throw new ArithmeticException("divisor is zero");
929 BigInteger quot
= new BigInteger();
930 divide(this, val
, quot
, null, TRUNCATE
);
931 return quot
.canonicalize();
934 public BigInteger
remainder(BigInteger val
)
937 throw new ArithmeticException("divisor is zero");
939 BigInteger rem
= new BigInteger();
940 divide(this, val
, null, rem
, TRUNCATE
);
941 return rem
.canonicalize();
944 public BigInteger
[] divideAndRemainder(BigInteger val
)
947 throw new ArithmeticException("divisor is zero");
949 BigInteger
[] result
= new BigInteger
[2];
950 result
[0] = new BigInteger();
951 result
[1] = new BigInteger();
952 divide(this, val
, result
[0], result
[1], TRUNCATE
);
953 result
[0].canonicalize();
954 result
[1].canonicalize();
958 public BigInteger
mod(BigInteger m
)
960 if (m
.isNegative() || m
.isZero())
961 throw new ArithmeticException("non-positive modulus");
963 BigInteger rem
= new BigInteger();
964 divide(this, m
, null, rem
, FLOOR
);
965 return rem
.canonicalize();
968 /** Calculate the integral power of a BigInteger.
969 * @param exponent the exponent (must be non-negative)
971 public BigInteger
pow(int exponent
)
977 throw new ArithmeticException("negative exponent");
981 int plen
= words
== null ?
1 : ival
; // Length of pow2.
982 int blen
= ((bitLength() * exponent
) >> 5) + 2 * plen
;
983 boolean negative
= isNegative() && (exponent
& 1) != 0;
984 int[] pow2
= new int [blen
];
985 int[] rwords
= new int [blen
];
986 int[] work
= new int [blen
];
987 getAbsolute(pow2
); // pow2 = abs(this);
989 rwords
[0] = 1; // rwords = 1;
990 for (;;) // for (i = 0; ; i++)
992 // pow2 == this**(2**i)
993 // prod = this**(sum(j=0..i-1, (exponent>>j)&1))
994 if ((exponent
& 1) != 0)
996 MPN
.mul(work
, pow2
, plen
, rwords
, rlen
);
997 int[] temp
= work
; work
= rwords
; rwords
= temp
;
999 while (rwords
[rlen
- 1] == 0) rlen
--;
1005 MPN
.mul(work
, pow2
, plen
, pow2
, plen
);
1006 int[] temp
= work
; work
= pow2
; pow2
= temp
; // swap to avoid a copy
1008 while (pow2
[plen
- 1] == 0) plen
--;
1010 if (rwords
[rlen
- 1] < 0)
1013 negate(rwords
, rwords
, rlen
);
1014 return BigInteger
.make(rwords
, rlen
);
1017 private static int[] euclidInv(int a
, int b
, int prevDiv
)
1020 throw new ArithmeticException("not invertible");
1023 // Success: values are indeed invertible!
1024 // Bottom of the recursion reached; start unwinding.
1025 return new int[] { -prevDiv
, 1 };
1027 int[] xy
= euclidInv(b
, a
% b
, a
/ b
); // Recursion happens here.
1028 a
= xy
[0]; // use our local copy of 'a' as a work var
1029 xy
[0] = a
* -prevDiv
+ xy
[1];
1034 private static void euclidInv(BigInteger a
, BigInteger b
,
1035 BigInteger prevDiv
, BigInteger
[] xy
)
1038 throw new ArithmeticException("not invertible");
1042 // Success: values are indeed invertible!
1043 // Bottom of the recursion reached; start unwinding.
1044 xy
[0] = neg(prevDiv
);
1049 // Recursion happens in the following conditional!
1051 // If a just contains an int, then use integer math for the rest.
1052 if (a
.words
== null)
1054 int[] xyInt
= euclidInv(b
.ival
, a
.ival
% b
.ival
, a
.ival
/ b
.ival
);
1055 xy
[0] = new BigInteger(xyInt
[0]);
1056 xy
[1] = new BigInteger(xyInt
[1]);
1060 BigInteger rem
= new BigInteger();
1061 BigInteger quot
= new BigInteger();
1062 divide(a
, b
, quot
, rem
, FLOOR
);
1063 // quot and rem may not be in canonical form. ensure
1065 quot
.canonicalize();
1066 euclidInv(b
, rem
, quot
, xy
);
1069 BigInteger t
= xy
[0];
1070 xy
[0] = add(xy
[1], times(t
, prevDiv
), -1);
1074 public BigInteger
modInverse(BigInteger y
)
1076 if (y
.isNegative() || y
.isZero())
1077 throw new ArithmeticException("non-positive modulo");
1079 // Degenerate cases.
1085 // Use Euclid's algorithm as in gcd() but do this recursively
1086 // rather than in a loop so we can use the intermediate results as we
1087 // unwind from the recursion.
1088 // Used http://www.math.nmsu.edu/~crypto/EuclideanAlgo.html as reference.
1089 BigInteger result
= new BigInteger();
1090 boolean swapped
= false;
1092 if (y
.words
== null)
1094 // The result is guaranteed to be less than the modulus, y (which is
1095 // an int), so simplify this by working with the int result of this
1096 // modulo y. Also, if this is negative, make it positive via modulo
1097 // math. Note that BigInteger.mod() must be used even if this is
1098 // already an int as the % operator would provide a negative result if
1099 // this is negative, BigInteger.mod() never returns negative values.
1100 int xval
= (words
!= null || isNegative()) ?
mod(y
).ival
: ival
;
1103 // Swap values so x > y.
1106 int tmp
= xval
; xval
= yval
; yval
= tmp
;
1109 // Normally, the result is in the 2nd element of the array, but
1110 // if originally x < y, then x and y were swapped and the result
1111 // is in the 1st element of the array.
1113 euclidInv(yval
, xval
% yval
, xval
/ yval
)[swapped ?
0 : 1];
1115 // Result can't be negative, so make it positive by adding the
1116 // original modulus, y.ival (not the possibly "swapped" yval).
1117 if (result
.ival
< 0)
1118 result
.ival
+= y
.ival
;
1122 // As above, force this to be a positive value via modulo math.
1123 BigInteger x
= isNegative() ?
this.mod(y
) : this;
1125 // Swap values so x > y.
1126 if (x
.compareTo(y
) < 0)
1128 result
= x
; x
= y
; y
= result
; // use 'result' as a work var
1131 // As above (for ints), result will be in the 2nd element unless
1132 // the original x and y were swapped.
1133 BigInteger rem
= new BigInteger();
1134 BigInteger quot
= new BigInteger();
1135 divide(x
, y
, quot
, rem
, FLOOR
);
1136 // quot and rem may not be in canonical form. ensure
1138 quot
.canonicalize();
1139 BigInteger
[] xy
= new BigInteger
[2];
1140 euclidInv(y
, rem
, quot
, xy
);
1141 result
= swapped ? xy
[0] : xy
[1];
1143 // Result can't be negative, so make it positive by adding the
1144 // original modulus, y (which is now x if they were swapped).
1145 if (result
.isNegative())
1146 result
= add(result
, swapped ? x
: y
, 1);
1152 public BigInteger
modPow(BigInteger exponent
, BigInteger m
)
1154 if (m
.isNegative() || m
.isZero())
1155 throw new ArithmeticException("non-positive modulo");
1157 if (exponent
.isNegative())
1158 return modInverse(m
);
1159 if (exponent
.isOne())
1162 // To do this naively by first raising this to the power of exponent
1163 // and then performing modulo m would be extremely expensive, especially
1164 // for very large numbers. The solution is found in Number Theory
1165 // where a combination of partial powers and moduli can be done easily.
1167 // We'll use the algorithm for Additive Chaining which can be found on
1168 // p. 244 of "Applied Cryptography, Second Edition" by Bruce Schneier.
1170 BigInteger t
= this;
1171 BigInteger u
= exponent
;
1175 if (u
.and(ONE
).isOne())
1176 s
= times(s
, t
).mod(m
);
1177 u
= u
.shiftRight(1);
1178 t
= times(t
, t
).mod(m
);
1184 /** Calculate Greatest Common Divisor for non-negative ints. */
1185 private static int gcd(int a
, int b
)
1187 // Euclid's algorithm, copied from libg++.
1191 tmp
= a
; a
= b
; b
= tmp
;
1205 public BigInteger
gcd(BigInteger y
)
1214 && xval
!= Integer
.MIN_VALUE
&& yval
!= Integer
.MIN_VALUE
)
1220 return valueOf(gcd(xval
, yval
));
1224 if (y
.words
== null)
1230 int len
= (xval
> yval ? xval
: yval
) + 1;
1231 int[] xwords
= new int[len
];
1232 int[] ywords
= new int[len
];
1233 getAbsolute(xwords
);
1234 y
.getAbsolute(ywords
);
1235 len
= MPN
.gcd(xwords
, ywords
, len
);
1236 BigInteger result
= new BigInteger(0);
1238 result
.words
= xwords
;
1239 return result
.canonicalize();
1243 * <p>Returns <code>true</code> if this BigInteger is probably prime,
1244 * <code>false</code> if it's definitely composite. If <code>certainty</code>
1245 * is <code><= 0</code>, <code>true</code> is returned.</p>
1247 * @param certainty a measure of the uncertainty that the caller is willing
1248 * to tolerate: if the call returns <code>true</code> the probability that
1249 * this BigInteger is prime exceeds <code>(1 - 1/2<sup>certainty</sup>)</code>.
1250 * The execution time of this method is proportional to the value of this
1252 * @return <code>true</code> if this BigInteger is probably prime,
1253 * <code>false</code> if it's definitely composite.
1255 public boolean isProbablePrime(int certainty
)
1260 /** We'll use the Rabin-Miller algorithm for doing a probabilistic
1261 * primality test. It is fast, easy and has faster decreasing odds of a
1262 * composite passing than with other tests. This means that this
1263 * method will actually have a probability much greater than the
1264 * 1 - .5^certainty specified in the JCL (p. 117), but I don't think
1265 * anyone will complain about better performance with greater certainty.
1267 * The Rabin-Miller algorithm can be found on pp. 259-261 of "Applied
1268 * Cryptography, Second Edition" by Bruce Schneier.
1271 // First rule out small prime factors
1272 BigInteger rem
= new BigInteger();
1274 for (i
= 0; i
< primes
.length
; i
++)
1276 if (words
== null && ival
== primes
[i
])
1279 divide(this, smallFixNums
[primes
[i
] - minFixNum
], null, rem
, TRUNCATE
);
1280 if (rem
.canonicalize().isZero())
1284 // Now perform the Rabin-Miller test.
1286 // Set b to the number of times 2 evenly divides (this - 1).
1287 // I.e. 2^b is the largest power of 2 that divides (this - 1).
1288 BigInteger pMinus1
= add(this, -1);
1289 int b
= pMinus1
.getLowestSetBit();
1291 // Set m such that this = 1 + 2^b * m.
1292 BigInteger m
= pMinus1
.divide(valueOf(2L << b
- 1));
1294 // The HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Note
1295 // 4.49 (controlling the error probability) gives the number of trials
1296 // for an error probability of 1/2**80, given the number of bits in the
1297 // number to test. we shall use these numbers as is if/when 'certainty'
1298 // is less or equal to 80, and twice as much if it's greater.
1299 int bits
= this.bitLength();
1300 for (i
= 0; i
< k
.length
; i
++)
1307 for (int t
= 0; t
< trials
; t
++)
1309 // The HAC (Handbook of Applied Cryptography), Alfred Menezes & al.
1310 // Remark 4.28 states: "...A strategy that is sometimes employed
1311 // is to fix the bases a to be the first few primes instead of
1312 // choosing them at random.
1313 z
= smallFixNums
[primes
[t
] - minFixNum
].modPow(m
, this);
1314 if (z
.isOne() || z
.equals(pMinus1
))
1315 continue; // Passes the test; may be prime.
1317 for (i
= 0; i
< b
; )
1322 if (z
.equals(pMinus1
))
1323 break; // Passes the test; may be prime.
1325 z
= z
.modPow(valueOf(2), this);
1328 if (i
== b
&& !z
.equals(pMinus1
))
1334 private void setInvert()
1340 for (int i
= ival
; --i
>= 0; )
1341 words
[i
] = ~words
[i
];
1345 private void setShiftLeft(BigInteger x
, int count
)
1349 if (x
.words
== null)
1353 set((long) x
.ival
<< count
);
1356 xwords
= new int[1];
1365 int word_count
= count
>> 5;
1367 int new_len
= xlen
+ word_count
;
1371 for (int i
= xlen
; --i
>= 0; )
1372 words
[i
+word_count
] = xwords
[i
];
1378 int shift_out
= MPN
.lshift(words
, word_count
, xwords
, xlen
, count
);
1380 words
[new_len
-1] = (shift_out
<< count
) >> count
; // sign-extend.
1383 for (int i
= word_count
; --i
>= 0; )
1387 private void setShiftRight(BigInteger x
, int count
)
1389 if (x
.words
== null)
1390 set(count
< 32 ? x
.ival
>> count
: x
.ival
< 0 ?
-1 : 0);
1391 else if (count
== 0)
1395 boolean neg
= x
.isNegative();
1396 int word_count
= count
>> 5;
1398 int d_len
= x
.ival
- word_count
;
1403 if (words
== null || words
.length
< d_len
)
1405 MPN
.rshift0 (words
, x
.words
, word_count
, d_len
, count
);
1408 words
[d_len
-1] |= -2 << (31 - count
);
1413 private void setShift(BigInteger x
, int count
)
1416 setShiftLeft(x
, count
);
1418 setShiftRight(x
, -count
);
1421 private static BigInteger
shift(BigInteger x
, int count
)
1423 if (x
.words
== null)
1426 return valueOf(count
> -32 ? x
.ival
>> (-count
) : x
.ival
< 0 ?
-1 : 0);
1428 return valueOf((long) x
.ival
<< count
);
1432 BigInteger result
= new BigInteger(0);
1433 result
.setShift(x
, count
);
1434 return result
.canonicalize();
1437 public BigInteger
shiftLeft(int n
)
1439 return shift(this, n
);
1442 public BigInteger
shiftRight(int n
)
1444 return shift(this, -n
);
1447 private void format(int radix
, StringBuffer buffer
)
1450 buffer
.append(Integer
.toString(ival
, radix
));
1452 buffer
.append(Long
.toString(longValue(), radix
));
1455 boolean neg
= isNegative();
1457 if (neg
|| radix
!= 16)
1459 work
= new int[ival
];
1470 int buf_start
= buffer
.length();
1471 for (int i
= len
; --i
>= 0; )
1474 for (int j
= 8; --j
>= 0; )
1476 int hex_digit
= (word
>> (4 * j
)) & 0xF;
1477 // Suppress leading zeros:
1478 if (hex_digit
> 0 || buffer
.length() > buf_start
)
1479 buffer
.append(Character
.forDigit(hex_digit
, 16));
1485 int i
= buffer
.length();
1488 int digit
= MPN
.divmod_1(work
, work
, len
, radix
);
1489 buffer
.append(Character
.forDigit(digit
, radix
));
1490 while (len
> 0 && work
[len
-1] == 0) len
--;
1496 /* Reverse buffer. */
1497 int j
= buffer
.length() - 1;
1500 char tmp
= buffer
.charAt(i
);
1501 buffer
.setCharAt(i
, buffer
.charAt(j
));
1502 buffer
.setCharAt(j
, tmp
);
1509 public String
toString()
1511 return toString(10);
1514 public String
toString(int radix
)
1517 return Integer
.toString(ival
, radix
);
1519 return Long
.toString(longValue(), radix
);
1520 int buf_size
= ival
* (MPN
.chars_per_word(radix
) + 1);
1521 StringBuffer buffer
= new StringBuffer(buf_size
);
1522 format(radix
, buffer
);
1523 return buffer
.toString();
1526 public int intValue()
1533 public long longValue()
1539 return ((long)words
[1] << 32) + ((long)words
[0] & 0xffffffffL
);
1542 public int hashCode()
1544 // FIXME: May not match hashcode of JDK.
1545 return words
== null ? ival
: (words
[0] + words
[ival
- 1]);
1548 /* Assumes x and y are both canonicalized. */
1549 private static boolean equals(BigInteger x
, BigInteger y
)
1551 if (x
.words
== null && y
.words
== null)
1552 return x
.ival
== y
.ival
;
1553 if (x
.words
== null || y
.words
== null || x
.ival
!= y
.ival
)
1555 for (int i
= x
.ival
; --i
>= 0; )
1557 if (x
.words
[i
] != y
.words
[i
])
1563 /* Assumes this and obj are both canonicalized. */
1564 public boolean equals(Object obj
)
1566 if (! (obj
instanceof BigInteger
))
1568 return equals(this, (BigInteger
) obj
);
1571 private static BigInteger
valueOf(String s
, int radix
)
1572 throws NumberFormatException
1574 int len
= s
.length();
1575 // Testing (len < MPN.chars_per_word(radix)) would be more accurate,
1576 // but slightly more expensive, for little practical gain.
1577 if (len
<= 15 && radix
<= 16)
1578 return valueOf(Long
.parseLong(s
, radix
));
1581 byte[] bytes
= new byte[len
];
1582 boolean negative
= false;
1583 for (int i
= 0; i
< len
; i
++)
1585 char ch
= s
.charAt(i
);
1588 else if (ch
== '_' || (byte_len
== 0 && (ch
== ' ' || ch
== '\t')))
1592 int digit
= Character
.digit(ch
, radix
);
1595 bytes
[byte_len
++] = (byte) digit
;
1598 return valueOf(bytes
, byte_len
, negative
, radix
);
1601 private static BigInteger
valueOf(byte[] digits
, int byte_len
,
1602 boolean negative
, int radix
)
1604 int chars_per_word
= MPN
.chars_per_word(radix
);
1605 int[] words
= new int[byte_len
/ chars_per_word
+ 1];
1606 int size
= MPN
.set_str(words
, digits
, byte_len
, radix
);
1609 if (words
[size
-1] < 0)
1612 negate(words
, words
, size
);
1613 return make(words
, size
);
1616 public double doubleValue()
1619 return (double) ival
;
1621 return (double) longValue();
1623 return neg(this).roundToDouble(0, true, false);
1624 return roundToDouble(0, false, false);
1627 public float floatValue()
1629 return (float) doubleValue();
1632 /** Return true if any of the lowest n bits are one.
1633 * (false if n is negative). */
1634 private boolean checkBits(int n
)
1639 return n
> 31 || ((ival
& ((1 << n
) - 1)) != 0);
1641 for (i
= 0; i
< (n
>> 5) ; i
++)
1644 return (n
& 31) != 0 && (words
[i
] & ((1 << (n
& 31)) - 1)) != 0;
1647 /** Convert a semi-processed BigInteger to double.
1648 * Number must be non-negative. Multiplies by a power of two, applies sign,
1649 * and converts to double, with the usual java rounding.
1650 * @param exp power of two, positive or negative, by which to multiply
1651 * @param neg true if negative
1652 * @param remainder true if the BigInteger is the result of a truncating
1653 * division that had non-zero remainder. To ensure proper rounding in
1654 * this case, the BigInteger must have at least 54 bits. */
1655 private double roundToDouble(int exp
, boolean neg
, boolean remainder
)
1658 int il
= bitLength();
1660 // Exponent when normalized to have decimal point directly after
1661 // leading one. This is stored excess 1023 in the exponent bit field.
1664 // Gross underflow. If exp == -1075, we let the rounding
1665 // computation determine whether it is minval or 0 (which are just
1666 // 0x0000 0000 0000 0001 and 0x0000 0000 0000 0000 as bit
1669 return neg ?
-0.0 : 0.0;
1673 return neg ? Double
.NEGATIVE_INFINITY
: Double
.POSITIVE_INFINITY
;
1675 // number of bits in mantissa, including the leading one.
1676 // 53 unless it's denormalized
1677 int ml
= (exp
>= -1022 ?
53 : 53 + exp
+ 1022);
1679 // Get top ml + 1 bits. The extra one is for rounding.
1681 int excess_bits
= il
- (ml
+ 1);
1682 if (excess_bits
> 0)
1683 m
= ((words
== null) ? ival
>> excess_bits
1684 : MPN
.rshift_long(words
, ival
, excess_bits
));
1686 m
= longValue() << (- excess_bits
);
1688 // Special rounding for maxval. If the number exceeds maxval by
1689 // any amount, even if it's less than half a step, it overflows.
1690 if (exp
== 1023 && ((m
>> 1) == (1L << 53) - 1))
1692 if (remainder
|| checkBits(il
- ml
))
1693 return neg ? Double
.NEGATIVE_INFINITY
: Double
.POSITIVE_INFINITY
;
1695 return neg ?
- Double
.MAX_VALUE
: Double
.MAX_VALUE
;
1698 // Normal round-to-even rule: round up if the bit dropped is a one, and
1699 // the bit above it or any of the bits below it is a one.
1701 && ((m
& 2) == 2 || remainder
|| checkBits(excess_bits
)))
1704 // Check if we overflowed the mantissa
1705 if ((m
& (1L << 54)) != 0)
1711 // Check if a denormalized mantissa was just rounded up to a
1713 else if (ml
== 52 && (m
& (1L << 53)) != 0)
1717 // Discard the rounding bit
1720 long bits_sign
= neg ?
(1L << 63) : 0;
1722 long bits_exp
= (exp
<= 0) ?
0 : ((long)exp
) << 52;
1723 long bits_mant
= m
& ~
(1L << 52);
1724 return Double
.longBitsToDouble(bits_sign
| bits_exp
| bits_mant
);
1727 /** Copy the abolute value of this into an array of words.
1728 * Assumes words.length >= (this.words == null ? 1 : this.ival).
1729 * Result is zero-extended, but need not be a valid 2's complement number.
1731 private void getAbsolute(int[] words
)
1734 if (this.words
== null)
1737 words
[0] = this.ival
;
1742 for (int i
= len
; --i
>= 0; )
1743 words
[i
] = this.words
[i
];
1745 if (words
[len
- 1] < 0)
1746 negate(words
, words
, len
);
1747 for (int i
= words
.length
; --i
> len
; )
1751 /** Set dest[0:len-1] to the negation of src[0:len-1].
1752 * Return true if overflow (i.e. if src is -2**(32*len-1)).
1753 * Ok for src==dest. */
1754 private static boolean negate(int[] dest
, int[] src
, int len
)
1757 boolean negative
= src
[len
-1] < 0;
1758 for (int i
= 0; i
< len
; i
++)
1760 carry
+= ((long) (~src
[i
]) & 0xffffffffL
);
1761 dest
[i
] = (int) carry
;
1764 return (negative
&& dest
[len
-1] < 0);
1767 /** Destructively set this to the negative of x.
1768 * It is OK if x==this.*/
1769 private void setNegative(BigInteger x
)
1772 if (x
.words
== null)
1774 if (len
== Integer
.MIN_VALUE
)
1781 if (negate(words
, x
.words
, len
))
1786 /** Destructively negate this. */
1787 private void setNegative()
1792 private static BigInteger
abs(BigInteger x
)
1794 return x
.isNegative() ?
neg(x
) : x
;
1797 public BigInteger
abs()
1802 private static BigInteger
neg(BigInteger x
)
1804 if (x
.words
== null && x
.ival
!= Integer
.MIN_VALUE
)
1805 return valueOf(- x
.ival
);
1806 BigInteger result
= new BigInteger(0);
1807 result
.setNegative(x
);
1808 return result
.canonicalize();
1811 public BigInteger
negate()
1816 /** Calculates ceiling(log2(this < 0 ? -this : this+1))
1817 * See Common Lisp: the Language, 2nd ed, p. 361.
1819 public int bitLength()
1822 return MPN
.intLength(ival
);
1823 return MPN
.intLength(words
, ival
);
1826 public byte[] toByteArray()
1828 // Determine number of bytes needed. The method bitlength returns
1829 // the size without the sign bit, so add one bit for that and then
1830 // add 7 more to emulate the ceil function using integer math.
1831 byte[] bytes
= new byte[(bitLength() + 1 + 7) / 8];
1832 int nbytes
= bytes
.length
;
1837 // Deal with words array until one word or less is left to process.
1838 // If BigInteger is an int, then it is in ival and nbytes will be <= 4.
1841 word
= words
[wptr
++];
1842 for (int i
= 4; i
> 0; --i
, word
>>= 8)
1843 bytes
[--nbytes
] = (byte) word
;
1846 // Deal with the last few bytes. If BigInteger is an int, use ival.
1847 word
= (words
== null) ? ival
: words
[wptr
];
1848 for ( ; nbytes
> 0; word
>>= 8)
1849 bytes
[--nbytes
] = (byte) word
;
1854 /** Return the boolean opcode (for bitOp) for swapped operands.
1855 * I.e. bitOp(swappedOp(op), x, y) == bitOp(op, y, x).
1857 private static int swappedOp(int op
)
1860 "\000\001\004\005\002\003\006\007\010\011\014\015\012\013\016\017"
1864 /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
1865 private static BigInteger
bitOp(int op
, BigInteger x
, BigInteger y
)
1869 case 0: return ZERO
;
1870 case 1: return x
.and(y
);
1873 case 15: return valueOf(-1);
1875 BigInteger result
= new BigInteger();
1876 setBitOp(result
, op
, x
, y
);
1877 return result
.canonicalize();
1880 /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
1881 private static void setBitOp(BigInteger result
, int op
,
1882 BigInteger x
, BigInteger y
)
1884 if (y
.words
== null) ;
1885 else if (x
.words
== null || x
.ival
< y
.ival
)
1887 BigInteger temp
= x
; x
= y
; y
= temp
;
1893 if (y
.words
== null)
1903 if (x
.words
== null)
1914 result
.realloc(xlen
);
1915 int[] w
= result
.words
;
1917 // Code for how to handle the remainder of x.
1918 // 0: Truncate to length of y.
1919 // 1: Copy rest of x.
1920 // 2: Invert rest of x.
1932 if (i
+1 >= ylen
) break;
1933 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
1935 if (yi
< 0) finish
= 1;
1941 if (i
+1 >= ylen
) break;
1942 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
1944 if (yi
>= 0) finish
= 1;
1948 finish
= 1; // Copy rest
1954 if (i
+1 >= ylen
) break;
1955 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
1957 if (yi
< 0) finish
= 2;
1963 if (i
+1 >= ylen
) break;
1964 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
1971 if (i
+1 >= ylen
) break;
1972 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
1974 finish
= yi
< 0 ?
2 : 1;
1980 if (i
+1 >= ylen
) break;
1981 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
1983 if (yi
>= 0) finish
= 1;
1989 if (i
+1 >= ylen
) break;
1990 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
1992 if (yi
>= 0) finish
= 2;
1994 case 9: // eqv [exclusive nor]
1998 if (i
+1 >= ylen
) break;
1999 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
2001 finish
= yi
>= 0 ?
2 : 1;
2007 if (i
+1 >= ylen
) break;
2008 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
2015 if (i
+1 >= ylen
) break;
2016 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
2018 if (yi
< 0) finish
= 1;
2028 if (i
+1 >= ylen
) break;
2029 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
2031 if (yi
>= 0) finish
= 2;
2037 if (i
+1 >= ylen
) break;
2038 w
[i
++] = ni
; xi
= x
.words
[i
]; yi
= y
.words
[i
];
2040 if (yi
< 0) finish
= 2;
2047 // Here i==ylen-1; w[0]..w[i-1] have the correct result;
2048 // and ni contains the correct result for w[i+1].
2054 if (i
== 0 && w
== null)
2061 case 1: w
[i
] = ni
; while (++i
< xlen
) w
[i
] = x
.words
[i
]; break;
2062 case 2: w
[i
] = ni
; while (++i
< xlen
) w
[i
] = ~x
.words
[i
]; break;
2067 /** Return the logical (bit-wise) "and" of a BigInteger and an int. */
2068 private static BigInteger
and(BigInteger x
, int y
)
2070 if (x
.words
== null)
2071 return valueOf(x
.ival
& y
);
2073 return valueOf(x
.words
[0] & y
);
2075 int[] words
= new int[len
];
2076 words
[0] = x
.words
[0] & y
;
2078 words
[len
] = x
.words
[len
];
2079 return make(words
, x
.ival
);
2082 /** Return the logical (bit-wise) "and" of two BigIntegers. */
2083 public BigInteger
and(BigInteger y
)
2085 if (y
.words
== null)
2086 return and(this, y
.ival
);
2087 else if (words
== null)
2088 return and(y
, ival
);
2090 BigInteger x
= this;
2093 BigInteger temp
= this; x
= y
; y
= temp
;
2096 int len
= y
.isNegative() ? x
.ival
: y
.ival
;
2097 int[] words
= new int[len
];
2098 for (i
= 0; i
< y
.ival
; i
++)
2099 words
[i
] = x
.words
[i
] & y
.words
[i
];
2100 for ( ; i
< len
; i
++)
2101 words
[i
] = x
.words
[i
];
2102 return make(words
, len
);
2105 /** Return the logical (bit-wise) "(inclusive) or" of two BigIntegers. */
2106 public BigInteger
or(BigInteger y
)
2108 return bitOp(7, this, y
);
2111 /** Return the logical (bit-wise) "exclusive or" of two BigIntegers. */
2112 public BigInteger
xor(BigInteger y
)
2114 return bitOp(6, this, y
);
2117 /** Return the logical (bit-wise) negation of a BigInteger. */
2118 public BigInteger
not()
2120 return bitOp(12, this, ZERO
);
2123 public BigInteger
andNot(BigInteger val
)
2125 return and(val
.not());
2128 public BigInteger
clearBit(int n
)
2131 throw new ArithmeticException();
2133 return and(ONE
.shiftLeft(n
).not());
2136 public BigInteger
setBit(int n
)
2139 throw new ArithmeticException();
2141 return or(ONE
.shiftLeft(n
));
2144 public boolean testBit(int n
)
2147 throw new ArithmeticException();
2149 return !and(ONE
.shiftLeft(n
)).isZero();
2152 public BigInteger
flipBit(int n
)
2155 throw new ArithmeticException();
2157 return xor(ONE
.shiftLeft(n
));
2160 public int getLowestSetBit()
2166 return MPN
.findLowestBit(ival
);
2168 return MPN
.findLowestBit(words
);
2171 // bit4count[I] is number of '1' bits in I.
2172 private static final byte[] bit4_count
= { 0, 1, 1, 2, 1, 2, 2, 3,
2173 1, 2, 2, 3, 2, 3, 3, 4};
2175 private static int bitCount(int i
)
2180 count
+= bit4_count
[i
& 15];
2186 private static int bitCount(int[] x
, int len
)
2190 count
+= bitCount(x
[len
]);
2194 /** Count one bits in a BigInteger.
2195 * If argument is negative, count zero bits instead. */
2196 public int bitCount()
2199 int[] x_words
= words
;
2200 if (x_words
== null)
2208 i
= bitCount(x_words
, x_len
);
2210 return isNegative() ? x_len
* 32 - i
: i
;
2213 private void readObject(ObjectInputStream s
)
2214 throws IOException
, ClassNotFoundException
2216 s
.defaultReadObject();
2217 words
= byteArrayToIntArray(magnitude
, signum
< 0 ?
-1 : 0);
2218 BigInteger result
= make(words
, words
.length
);
2219 this.ival
= result
.ival
;
2220 this.words
= result
.words
;
2223 private void writeObject(ObjectOutputStream s
)
2224 throws IOException
, ClassNotFoundException
2227 magnitude
= toByteArray();
2228 s
.defaultWriteObject();