1:
37:
38:
39: package ;
40:
41: import ;
42:
43: import ;
44: import ;
45: import ;
46:
47: import ;
48: import ;
49: import ;
50: import ;
51: import ;
52:
53:
65: public class BigInteger extends Number implements Comparable<BigInteger>
66: {
67: private static final Logger log = Logger.getLogger(BigInteger.class.getName());
68:
69:
73: private transient int ival;
74: private transient int[] words;
75:
76:
77:
78:
79: private int bitCount = -1;
80: private int bitLength = -1;
81: private int lowestSetBit = -2;
82: private byte[] magnitude;
83: private int signum;
84: private static final long serialVersionUID = -8287574255936472291L;
85:
86:
87:
89: private static final int minFixNum = -100;
90: private static final int maxFixNum = 1024;
91: private static final int numFixNum = maxFixNum-minFixNum+1;
92: private static final BigInteger[] smallFixNums;
93:
94:
95: private transient GMP mpz;
96:
97: private static final boolean USING_NATIVE = Configuration.WANT_NATIVE_BIG_INTEGER
98: && initializeLibrary();
99:
100: static
101: {
102: if (USING_NATIVE)
103: {
104: smallFixNums = null;
105: ZERO = valueOf(0L);
106: ONE = valueOf(1L);
107: TEN = valueOf(10L);
108: }
109: else
110: {
111: smallFixNums = new BigInteger[numFixNum];
112: for (int i = numFixNum; --i >= 0; )
113: smallFixNums[i] = new BigInteger(i + minFixNum);
114:
115: ZERO = smallFixNums[-minFixNum];
116: ONE = smallFixNums[1 - minFixNum];
117: TEN = smallFixNums[10 - minFixNum];
118: }
119: }
120:
121:
125: public static final BigInteger ZERO;
126:
127:
131: public static final BigInteger ONE;
132:
133:
137: public static final BigInteger TEN;
138:
139:
140: private static final int FLOOR = 1;
141: private static final int CEILING = 2;
142: private static final int TRUNCATE = 3;
143: private static final int ROUND = 4;
144:
145:
148: private static final int[] primes =
149: { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
150: 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
151: 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181,
152: 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251 };
153:
154:
155: private static final int[] k =
156: {100,150,200,250,300,350,400,500,600,800,1250, Integer.MAX_VALUE};
157: private static final int[] t =
158: { 27, 18, 15, 12, 9, 8, 7, 6, 5, 4, 3, 2};
159:
160: private BigInteger()
161: {
162: super();
163:
164: if (USING_NATIVE)
165: mpz = new GMP();
166: }
167:
168:
169: private BigInteger(int value)
170: {
171: super();
172:
173: ival = value;
174: }
175:
176: public BigInteger(String s, int radix)
177: {
178: this();
179:
180: int len = s.length();
181: int i, digit;
182: boolean negative;
183: byte[] bytes;
184: char ch = s.charAt(0);
185: if (ch == '-')
186: {
187: negative = true;
188: i = 1;
189: bytes = new byte[len - 1];
190: }
191: else
192: {
193: negative = false;
194: i = 0;
195: bytes = new byte[len];
196: }
197: int byte_len = 0;
198: for ( ; i < len; i++)
199: {
200: ch = s.charAt(i);
201: digit = Character.digit(ch, radix);
202: if (digit < 0)
203: throw new NumberFormatException("Invalid character at position #" + i);
204: bytes[byte_len++] = (byte) digit;
205: }
206:
207: if (USING_NATIVE)
208: {
209: bytes = null;
210: if (mpz.fromString(s, radix) != 0)
211: throw new NumberFormatException("String \"" + s
212: + "\" is NOT a valid number in base "
213: + radix);
214: }
215: else
216: {
217: BigInteger result;
218:
219:
220: if (len <= 15 && radix <= 16)
221: result = valueOf(Long.parseLong(s, radix));
222: else
223: result = valueOf(bytes, byte_len, negative, radix);
224:
225: this.ival = result.ival;
226: this.words = result.words;
227: }
228: }
229:
230: public BigInteger(String val)
231: {
232: this(val, 10);
233: }
234:
235:
236: public BigInteger(byte[] val)
237: {
238: this();
239:
240: if (val == null || val.length < 1)
241: throw new NumberFormatException();
242:
243: if (USING_NATIVE)
244: mpz.fromByteArray(val);
245: else
246: {
247: words = byteArrayToIntArray(val, val[0] < 0 ? -1 : 0);
248: BigInteger result = make(words, words.length);
249: this.ival = result.ival;
250: this.words = result.words;
251: }
252: }
253:
254: public BigInteger(int signum, byte[] magnitude)
255: {
256: this();
257:
258: if (magnitude == null || signum > 1 || signum < -1)
259: throw new NumberFormatException();
260:
261: if (signum == 0)
262: {
263: int i;
264: for (i = magnitude.length - 1; i >= 0 && magnitude[i] == 0; --i)
265: ;
266: if (i >= 0)
267: throw new NumberFormatException();
268: return;
269: }
270:
271: if (USING_NATIVE)
272: mpz.fromSignedMagnitude(magnitude, signum == -1);
273: else
274: {
275:
276: words = byteArrayToIntArray(magnitude, 0);
277: BigInteger result = make(words, words.length);
278: this.ival = result.ival;
279: this.words = result.words;
280:
281: if (signum < 0)
282: setNegative();
283: }
284: }
285:
286: public BigInteger(int numBits, Random rnd)
287: {
288: this();
289:
290: if (numBits < 0)
291: throw new IllegalArgumentException();
292:
293: init(numBits, rnd);
294: }
295:
296: private void init(int numBits, Random rnd)
297: {
298: if (USING_NATIVE)
299: {
300: int length = (numBits + 7) / 8;
301: byte[] magnitude = new byte[length];
302: rnd.nextBytes(magnitude);
303: int discardedBitCount = numBits % 8;
304: if (discardedBitCount != 0)
305: {
306: discardedBitCount = 8 - discardedBitCount;
307: magnitude[0] = (byte)((magnitude[0] & 0xFF) >>> discardedBitCount);
308: }
309: mpz.fromSignedMagnitude(magnitude, false);
310: magnitude = null;
311: return;
312: }
313:
314: int highbits = numBits & 31;
315:
316: int highBitByteCount = (highbits + 7) / 8;
317:
318: int discardedBitCount = highbits % 8;
319: if (discardedBitCount != 0)
320: discardedBitCount = 8 - discardedBitCount;
321: byte[] highBitBytes = new byte[highBitByteCount];
322: if (highbits > 0)
323: {
324: rnd.nextBytes(highBitBytes);
325: highbits = (highBitBytes[highBitByteCount - 1] & 0xFF) >>> discardedBitCount;
326: for (int i = highBitByteCount - 2; i >= 0; i--)
327: highbits = (highbits << 8) | (highBitBytes[i] & 0xFF);
328: }
329: int nwords = numBits / 32;
330:
331: while (highbits == 0 && nwords > 0)
332: {
333: highbits = rnd.nextInt();
334: --nwords;
335: }
336: if (nwords == 0 && highbits >= 0)
337: {
338: ival = highbits;
339: }
340: else
341: {
342: ival = highbits < 0 ? nwords + 2 : nwords + 1;
343: words = new int[ival];
344: words[nwords] = highbits;
345: while (--nwords >= 0)
346: words[nwords] = rnd.nextInt();
347: }
348: }
349:
350: public BigInteger(int bitLength, int certainty, Random rnd)
351: {
352: this();
353:
354: BigInteger result = new BigInteger();
355: while (true)
356: {
357: result.init(bitLength, rnd);
358: result = result.setBit(bitLength - 1);
359: if (result.isProbablePrime(certainty))
360: break;
361: }
362:
363: if (USING_NATIVE)
364: mpz.fromBI(result.mpz);
365: else
366: {
367: this.ival = result.ival;
368: this.words = result.words;
369: }
370: }
371:
372:
381: public static BigInteger probablePrime(int bitLength, Random rnd)
382: {
383: if (bitLength < 2)
384: throw new ArithmeticException();
385:
386: return new BigInteger(bitLength, 100, rnd);
387: }
388:
389:
390: public static BigInteger valueOf(long val)
391: {
392: if (USING_NATIVE)
393: {
394: BigInteger result = new BigInteger();
395: result.mpz.fromLong(val);
396: return result;
397: }
398:
399: if (val >= minFixNum && val <= maxFixNum)
400: return smallFixNums[(int) val - minFixNum];
401: int i = (int) val;
402: if ((long) i == val)
403: return new BigInteger(i);
404: BigInteger result = alloc(2);
405: result.ival = 2;
406: result.words[0] = i;
407: result.words[1] = (int)(val >> 32);
408: return result;
409: }
410:
411:
415: private static boolean initializeLibrary()
416: {
417: boolean result;
418: try
419: {
420: System.loadLibrary("javamath");
421: GMP.natInitializeLibrary();
422: result = true;
423: }
424: catch (Throwable x)
425: {
426: result = false;
427: if (Configuration.DEBUG)
428: {
429: log.info("Unable to use native BigInteger: " + x);
430: log.info("Will use a pure Java implementation instead");
431: }
432: }
433: return result;
434: }
435:
436:
438: private static BigInteger make(int[] words, int len)
439: {
440: if (words == null)
441: return valueOf(len);
442: len = BigInteger.wordsNeeded(words, len);
443: if (len <= 1)
444: return len == 0 ? ZERO : valueOf(words[0]);
445: BigInteger num = new BigInteger();
446: num.words = words;
447: num.ival = len;
448: return num;
449: }
450:
451:
452: private static int[] byteArrayToIntArray(byte[] bytes, int sign)
453: {
454:
455: int[] words = new int[bytes.length/4 + 1];
456: int nwords = words.length;
457:
458:
459: int bptr = 0;
460: int word = sign;
461: for (int i = bytes.length % 4; i > 0; --i, bptr++)
462: word = (word << 8) | (bytes[bptr] & 0xff);
463: words[--nwords] = word;
464:
465:
466: while (nwords > 0)
467: words[--nwords] = bytes[bptr++] << 24 |
468: (bytes[bptr++] & 0xff) << 16 |
469: (bytes[bptr++] & 0xff) << 8 |
470: (bytes[bptr++] & 0xff);
471: return words;
472: }
473:
474:
477: private static BigInteger alloc(int nwords)
478: {
479: BigInteger result = new BigInteger();
480: if (nwords > 1)
481: result.words = new int[nwords];
482: return result;
483: }
484:
485:
488: private void realloc(int nwords)
489: {
490: if (nwords == 0)
491: {
492: if (words != null)
493: {
494: if (ival > 0)
495: ival = words[0];
496: words = null;
497: }
498: }
499: else if (words == null
500: || words.length < nwords
501: || words.length > nwords + 2)
502: {
503: int[] new_words = new int [nwords];
504: if (words == null)
505: {
506: new_words[0] = ival;
507: ival = 1;
508: }
509: else
510: {
511: if (nwords < ival)
512: ival = nwords;
513: System.arraycopy(words, 0, new_words, 0, ival);
514: }
515: words = new_words;
516: }
517: }
518:
519: private boolean isNegative()
520: {
521: return (words == null ? ival : words[ival - 1]) < 0;
522: }
523:
524: public int signum()
525: {
526: if (USING_NATIVE)
527: return mpz.compare(ZERO.mpz);
528:
529: if (ival == 0 && words == null)
530: return 0;
531: int top = words == null ? ival : words[ival-1];
532: return top < 0 ? -1 : 1;
533: }
534:
535: private static int compareTo(BigInteger x, BigInteger y)
536: {
537: if (USING_NATIVE)
538: {
539: int dummy = y.signum;
540: return x.mpz.compare(y.mpz);
541: }
542:
543: if (x.words == null && y.words == null)
544: return x.ival < y.ival ? -1 : x.ival > y.ival ? 1 : 0;
545: boolean x_negative = x.isNegative();
546: boolean y_negative = y.isNegative();
547: if (x_negative != y_negative)
548: return x_negative ? -1 : 1;
549: int x_len = x.words == null ? 1 : x.ival;
550: int y_len = y.words == null ? 1 : y.ival;
551: if (x_len != y_len)
552: return (x_len > y_len) != x_negative ? 1 : -1;
553: return MPN.cmp(x.words, y.words, x_len);
554: }
555:
556:
557: public int compareTo(BigInteger val)
558: {
559: return compareTo(this, val);
560: }
561:
562: public BigInteger min(BigInteger val)
563: {
564: return compareTo(this, val) < 0 ? this : val;
565: }
566:
567: public BigInteger max(BigInteger val)
568: {
569: return compareTo(this, val) > 0 ? this : val;
570: }
571:
572: private boolean isZero()
573: {
574: return words == null && ival == 0;
575: }
576:
577: private boolean isOne()
578: {
579: return words == null && ival == 1;
580: }
581:
582:
586: private static int wordsNeeded(int[] words, int len)
587: {
588: int i = len;
589: if (i > 0)
590: {
591: int word = words[--i];
592: if (word == -1)
593: {
594: while (i > 0 && (word = words[i - 1]) < 0)
595: {
596: i--;
597: if (word != -1) break;
598: }
599: }
600: else
601: {
602: while (word == 0 && i > 0 && (word = words[i - 1]) >= 0) i--;
603: }
604: }
605: return i + 1;
606: }
607:
608: private BigInteger canonicalize()
609: {
610: if (words != null
611: && (ival = BigInteger.wordsNeeded(words, ival)) <= 1)
612: {
613: if (ival == 1)
614: ival = words[0];
615: words = null;
616: }
617: if (words == null && ival >= minFixNum && ival <= maxFixNum)
618: return smallFixNums[ival - minFixNum];
619: return this;
620: }
621:
622:
623: private static BigInteger add(int x, int y)
624: {
625: return valueOf((long) x + (long) y);
626: }
627:
628:
629: private static BigInteger add(BigInteger x, int y)
630: {
631: if (x.words == null)
632: return BigInteger.add(x.ival, y);
633: BigInteger result = new BigInteger(0);
634: result.setAdd(x, y);
635: return result.canonicalize();
636: }
637:
638:
640: private void setAdd(BigInteger x, int y)
641: {
642: if (x.words == null)
643: {
644: set((long) x.ival + (long) y);
645: return;
646: }
647: int len = x.ival;
648: realloc(len + 1);
649: long carry = y;
650: for (int i = 0; i < len; i++)
651: {
652: carry += ((long) x.words[i] & 0xffffffffL);
653: words[i] = (int) carry;
654: carry >>= 32;
655: }
656: if (x.words[len - 1] < 0)
657: carry--;
658: words[len] = (int) carry;
659: ival = wordsNeeded(words, len + 1);
660: }
661:
662:
663: private void setAdd(int y)
664: {
665: setAdd(this, y);
666: }
667:
668:
669: private void set(long y)
670: {
671: int i = (int) y;
672: if ((long) i == y)
673: {
674: ival = i;
675: words = null;
676: }
677: else
678: {
679: realloc(2);
680: words[0] = i;
681: words[1] = (int) (y >> 32);
682: ival = 2;
683: }
684: }
685:
686:
688: private void set(int[] words, int length)
689: {
690: this.ival = length;
691: this.words = words;
692: }
693:
694:
695: private void set(BigInteger y)
696: {
697: if (y.words == null)
698: set(y.ival);
699: else if (this != y)
700: {
701: realloc(y.ival);
702: System.arraycopy(y.words, 0, words, 0, y.ival);
703: ival = y.ival;
704: }
705: }
706:
707:
708: private static BigInteger add(BigInteger x, BigInteger y, int k)
709: {
710: if (x.words == null && y.words == null)
711: return valueOf((long) k * (long) y.ival + (long) x.ival);
712: if (k != 1)
713: {
714: if (k == -1)
715: y = BigInteger.neg(y);
716: else
717: y = BigInteger.times(y, valueOf(k));
718: }
719: if (x.words == null)
720: return BigInteger.add(y, x.ival);
721: if (y.words == null)
722: return BigInteger.add(x, y.ival);
723:
724: if (y.ival > x.ival)
725: {
726: BigInteger tmp = x; x = y; y = tmp;
727: }
728: BigInteger result = alloc(x.ival + 1);
729: int i = y.ival;
730: long carry = MPN.add_n(result.words, x.words, y.words, i);
731: long y_ext = y.words[i - 1] < 0 ? 0xffffffffL : 0;
732: for (; i < x.ival; i++)
733: {
734: carry += ((long) x.words[i] & 0xffffffffL) + y_ext;
735: result.words[i] = (int) carry;
736: carry >>>= 32;
737: }
738: if (x.words[i - 1] < 0)
739: y_ext--;
740: result.words[i] = (int) (carry + y_ext);
741: result.ival = i+1;
742: return result.canonicalize();
743: }
744:
745: public BigInteger add(BigInteger val)
746: {
747: if (USING_NATIVE)
748: {
749: int dummy = val.signum;
750: BigInteger result = new BigInteger();
751: mpz.add(val.mpz, result.mpz);
752: return result;
753: }
754:
755: return add(this, val, 1);
756: }
757:
758: public BigInteger subtract(BigInteger val)
759: {
760: if (USING_NATIVE)
761: {
762: int dummy = val.signum;
763: BigInteger result = new BigInteger();
764: mpz.subtract(val.mpz, result.mpz);
765: return result;
766: }
767:
768: return add(this, val, -1);
769: }
770:
771: private static BigInteger times(BigInteger x, int y)
772: {
773: if (y == 0)
774: return ZERO;
775: if (y == 1)
776: return x;
777: int[] xwords = x.words;
778: int xlen = x.ival;
779: if (xwords == null)
780: return valueOf((long) xlen * (long) y);
781: boolean negative;
782: BigInteger result = BigInteger.alloc(xlen + 1);
783: if (xwords[xlen - 1] < 0)
784: {
785: negative = true;
786: negate(result.words, xwords, xlen);
787: xwords = result.words;
788: }
789: else
790: negative = false;
791: if (y < 0)
792: {
793: negative = !negative;
794: y = -y;
795: }
796: result.words[xlen] = MPN.mul_1(result.words, xwords, xlen, y);
797: result.ival = xlen + 1;
798: if (negative)
799: result.setNegative();
800: return result.canonicalize();
801: }
802:
803: private static BigInteger times(BigInteger x, BigInteger y)
804: {
805: if (y.words == null)
806: return times(x, y.ival);
807: if (x.words == null)
808: return times(y, x.ival);
809: boolean negative = false;
810: int[] xwords;
811: int[] ywords;
812: int xlen = x.ival;
813: int ylen = y.ival;
814: if (x.isNegative())
815: {
816: negative = true;
817: xwords = new int[xlen];
818: negate(xwords, x.words, xlen);
819: }
820: else
821: {
822: negative = false;
823: xwords = x.words;
824: }
825: if (y.isNegative())
826: {
827: negative = !negative;
828: ywords = new int[ylen];
829: negate(ywords, y.words, ylen);
830: }
831: else
832: ywords = y.words;
833:
834: if (xlen < ylen)
835: {
836: int[] twords = xwords; xwords = ywords; ywords = twords;
837: int tlen = xlen; xlen = ylen; ylen = tlen;
838: }
839: BigInteger result = BigInteger.alloc(xlen+ylen);
840: MPN.mul(result.words, xwords, xlen, ywords, ylen);
841: result.ival = xlen+ylen;
842: if (negative)
843: result.setNegative();
844: return result.canonicalize();
845: }
846:
847: public BigInteger multiply(BigInteger y)
848: {
849: if (USING_NATIVE)
850: {
851: int dummy = y.signum;
852: BigInteger result = new BigInteger();
853: mpz.multiply(y.mpz, result.mpz);
854: return result;
855: }
856:
857: return times(this, y);
858: }
859:
860: private static void divide(long x, long y,
861: BigInteger quotient, BigInteger remainder,
862: int rounding_mode)
863: {
864: boolean xNegative, yNegative;
865: if (x < 0)
866: {
867: xNegative = true;
868: if (x == Long.MIN_VALUE)
869: {
870: divide(valueOf(x), valueOf(y),
871: quotient, remainder, rounding_mode);
872: return;
873: }
874: x = -x;
875: }
876: else
877: xNegative = false;
878:
879: if (y < 0)
880: {
881: yNegative = true;
882: if (y == Long.MIN_VALUE)
883: {
884: if (rounding_mode == TRUNCATE)
885: {
886: if (quotient != null)
887: quotient.set(0);
888: if (remainder != null)
889: remainder.set(x);
890: }
891: else
892: divide(valueOf(x), valueOf(y),
893: quotient, remainder, rounding_mode);
894: return;
895: }
896: y = -y;
897: }
898: else
899: yNegative = false;
900:
901: long q = x / y;
902: long r = x % y;
903: boolean qNegative = xNegative ^ yNegative;
904:
905: boolean add_one = false;
906: if (r != 0)
907: {
908: switch (rounding_mode)
909: {
910: case TRUNCATE:
911: break;
912: case CEILING:
913: case FLOOR:
914: if (qNegative == (rounding_mode == FLOOR))
915: add_one = true;
916: break;
917: case ROUND:
918: add_one = r > ((y - (q & 1)) >> 1);
919: break;
920: }
921: }
922: if (quotient != null)
923: {
924: if (add_one)
925: q++;
926: if (qNegative)
927: q = -q;
928: quotient.set(q);
929: }
930: if (remainder != null)
931: {
932:
933: if (add_one)
934: {
935:
936: r = y - r;
937:
938:
939: xNegative = ! xNegative;
940: }
941: else
942: {
943:
944:
945: }
946: if (xNegative)
947: r = -r;
948: remainder.set(r);
949: }
950: }
951:
952:
960: private static void divide(BigInteger x, BigInteger y,
961: BigInteger quotient, BigInteger remainder,
962: int rounding_mode)
963: {
964: if ((x.words == null || x.ival <= 2)
965: && (y.words == null || y.ival <= 2))
966: {
967: long x_l = x.longValue();
968: long y_l = y.longValue();
969: if (x_l != Long.MIN_VALUE && y_l != Long.MIN_VALUE)
970: {
971: divide(x_l, y_l, quotient, remainder, rounding_mode);
972: return;
973: }
974: }
975:
976: boolean xNegative = x.isNegative();
977: boolean yNegative = y.isNegative();
978: boolean qNegative = xNegative ^ yNegative;
979:
980: int ylen = y.words == null ? 1 : y.ival;
981: int[] ywords = new int[ylen];
982: y.getAbsolute(ywords);
983: while (ylen > 1 && ywords[ylen - 1] == 0) ylen--;
984:
985: int xlen = x.words == null ? 1 : x.ival;
986: int[] xwords = new int[xlen+2];
987: x.getAbsolute(xwords);
988: while (xlen > 1 && xwords[xlen-1] == 0) xlen--;
989:
990: int qlen, rlen;
991:
992: int cmpval = MPN.cmp(xwords, xlen, ywords, ylen);
993: if (cmpval < 0)
994: {
995: int[] rwords = xwords; xwords = ywords; ywords = rwords;
996: rlen = xlen; qlen = 1; xwords[0] = 0;
997: }
998: else if (cmpval == 0)
999: {
1000: xwords[0] = 1; qlen = 1;
1001: ywords[0] = 0; rlen = 1;
1002: }
1003: else if (ylen == 1)
1004: {
1005: qlen = xlen;
1006:
1007:
1008:
1009:
1010: if (ywords[0] == 1 && xwords[xlen-1] < 0)
1011: qlen++;
1012: rlen = 1;
1013: ywords[0] = MPN.divmod_1(xwords, xwords, xlen, ywords[0]);
1014: }
1015: else
1016: {
1017:
1018:
1019:
1020:
1021: int nshift = MPN.count_leading_zeros(ywords[ylen - 1]);
1022: if (nshift != 0)
1023: {
1024:
1025:
1026: MPN.lshift(ywords, 0, ywords, ylen, nshift);
1027:
1028:
1029:
1030: int x_high = MPN.lshift(xwords, 0, xwords, xlen, nshift);
1031: xwords[xlen++] = x_high;
1032: }
1033:
1034: if (xlen == ylen)
1035: xwords[xlen++] = 0;
1036: MPN.divide(xwords, xlen, ywords, ylen);
1037: rlen = ylen;
1038: MPN.rshift0 (ywords, xwords, 0, rlen, nshift);
1039:
1040: qlen = xlen + 1 - ylen;
1041: if (quotient != null)
1042: {
1043: for (int i = 0; i < qlen; i++)
1044: xwords[i] = xwords[i+ylen];
1045: }
1046: }
1047:
1048: if (ywords[rlen-1] < 0)
1049: {
1050: ywords[rlen] = 0;
1051: rlen++;
1052: }
1053:
1054:
1055:
1056: boolean add_one = false;
1057: if (rlen > 1 || ywords[0] != 0)
1058: {
1059: switch (rounding_mode)
1060: {
1061: case TRUNCATE:
1062: break;
1063: case CEILING:
1064: case FLOOR:
1065: if (qNegative == (rounding_mode == FLOOR))
1066: add_one = true;
1067: break;
1068: case ROUND:
1069:
1070: BigInteger tmp = remainder == null ? new BigInteger() : remainder;
1071: tmp.set(ywords, rlen);
1072: tmp = shift(tmp, 1);
1073: if (yNegative)
1074: tmp.setNegative();
1075: int cmp = compareTo(tmp, y);
1076:
1077: if (yNegative)
1078: cmp = -cmp;
1079: add_one = (cmp == 1) || (cmp == 0 && (xwords[0]&1) != 0);
1080: }
1081: }
1082: if (quotient != null)
1083: {
1084: quotient.set(xwords, qlen);
1085: if (qNegative)
1086: {
1087: if (add_one)
1088: quotient.setInvert();
1089: else
1090: quotient.setNegative();
1091: }
1092: else if (add_one)
1093: quotient.setAdd(1);
1094: }
1095: if (remainder != null)
1096: {
1097:
1098: remainder.set(ywords, rlen);
1099: if (add_one)
1100: {
1101:
1102:
1103: BigInteger tmp;
1104: if (y.words == null)
1105: {
1106: tmp = remainder;
1107: tmp.set(yNegative ? ywords[0] + y.ival : ywords[0] - y.ival);
1108: }
1109: else
1110: tmp = BigInteger.add(remainder, y, yNegative ? 1 : -1);
1111:
1112:
1113:
1114:
1115: if (xNegative)
1116: remainder.setNegative(tmp);
1117: else
1118: remainder.set(tmp);
1119: }
1120: else
1121: {
1122:
1123:
1124: if (xNegative)
1125: remainder.setNegative();
1126: }
1127: }
1128: }
1129:
1130: public BigInteger divide(BigInteger val)
1131: {
1132: if (USING_NATIVE)
1133: {
1134: if (val.compareTo(ZERO) == 0)
1135: throw new ArithmeticException("divisor is zero");
1136:
1137: BigInteger result = new BigInteger();
1138: mpz.quotient(val.mpz, result.mpz);
1139: return result;
1140: }
1141:
1142: if (val.isZero())
1143: throw new ArithmeticException("divisor is zero");
1144:
1145: BigInteger quot = new BigInteger();
1146: divide(this, val, quot, null, TRUNCATE);
1147: return quot.canonicalize();
1148: }
1149:
1150: public BigInteger remainder(BigInteger val)
1151: {
1152: if (USING_NATIVE)
1153: {
1154: if (val.compareTo(ZERO) == 0)
1155: throw new ArithmeticException("divisor is zero");
1156:
1157: BigInteger result = new BigInteger();
1158: mpz.remainder(val.mpz, result.mpz);
1159: return result;
1160: }
1161:
1162: if (val.isZero())
1163: throw new ArithmeticException("divisor is zero");
1164:
1165: BigInteger rem = new BigInteger();
1166: divide(this, val, null, rem, TRUNCATE);
1167: return rem.canonicalize();
1168: }
1169:
1170: public BigInteger[] divideAndRemainder(BigInteger val)
1171: {
1172: if (USING_NATIVE)
1173: {
1174: if (val.compareTo(ZERO) == 0)
1175: throw new ArithmeticException("divisor is zero");
1176:
1177: BigInteger q = new BigInteger();
1178: BigInteger r = new BigInteger();
1179: mpz.quotientAndRemainder(val.mpz, q.mpz, r.mpz);
1180: return new BigInteger[] { q, r };
1181: }
1182:
1183: if (val.isZero())
1184: throw new ArithmeticException("divisor is zero");
1185:
1186: BigInteger[] result = new BigInteger[2];
1187: result[0] = new BigInteger();
1188: result[1] = new BigInteger();
1189: divide(this, val, result[0], result[1], TRUNCATE);
1190: result[0].canonicalize();
1191: result[1].canonicalize();
1192: return result;
1193: }
1194:
1195: public BigInteger mod(BigInteger m)
1196: {
1197: if (USING_NATIVE)
1198: {
1199: int dummy = m.signum;
1200: if (m.compareTo(ZERO) < 1)
1201: throw new ArithmeticException("non-positive modulus");
1202:
1203: BigInteger result = new BigInteger();
1204: mpz.modulo(m.mpz, result.mpz);
1205: return result;
1206: }
1207:
1208: if (m.isNegative() || m.isZero())
1209: throw new ArithmeticException("non-positive modulus");
1210:
1211: BigInteger rem = new BigInteger();
1212: divide(this, m, null, rem, FLOOR);
1213: return rem.canonicalize();
1214: }
1215:
1216:
1219: public BigInteger pow(int exponent)
1220: {
1221: if (exponent <= 0)
1222: {
1223: if (exponent == 0)
1224: return ONE;
1225: throw new ArithmeticException("negative exponent");
1226: }
1227:
1228: if (USING_NATIVE)
1229: {
1230: BigInteger result = new BigInteger();
1231: mpz.pow(exponent, result.mpz);
1232: return result;
1233: }
1234:
1235: if (isZero())
1236: return this;
1237: int plen = words == null ? 1 : ival;
1238: int blen = ((bitLength() * exponent) >> 5) + 2 * plen;
1239: boolean negative = isNegative() && (exponent & 1) != 0;
1240: int[] pow2 = new int [blen];
1241: int[] rwords = new int [blen];
1242: int[] work = new int [blen];
1243: getAbsolute(pow2);
1244: int rlen = 1;
1245: rwords[0] = 1;
1246: for (;;)
1247: {
1248:
1249:
1250: if ((exponent & 1) != 0)
1251: {
1252: MPN.mul(work, pow2, plen, rwords, rlen);
1253: int[] temp = work; work = rwords; rwords = temp;
1254: rlen += plen;
1255: while (rwords[rlen - 1] == 0) rlen--;
1256: }
1257: exponent >>= 1;
1258: if (exponent == 0)
1259: break;
1260:
1261: MPN.mul(work, pow2, plen, pow2, plen);
1262: int[] temp = work; work = pow2; pow2 = temp;
1263: plen *= 2;
1264: while (pow2[plen - 1] == 0) plen--;
1265: }
1266: if (rwords[rlen - 1] < 0)
1267: rlen++;
1268: if (negative)
1269: negate(rwords, rwords, rlen);
1270: return BigInteger.make(rwords, rlen);
1271: }
1272:
1273: private static int[] euclidInv(int a, int b, int prevDiv)
1274: {
1275: if (b == 0)
1276: throw new ArithmeticException("not invertible");
1277:
1278: if (b == 1)
1279:
1280:
1281: return new int[] { -prevDiv, 1 };
1282:
1283: int[] xy = euclidInv(b, a % b, a / b);
1284: a = xy[0];
1285: xy[0] = a * -prevDiv + xy[1];
1286: xy[1] = a;
1287: return xy;
1288: }
1289:
1290: private static void euclidInv(BigInteger a, BigInteger b,
1291: BigInteger prevDiv, BigInteger[] xy)
1292: {
1293: if (b.isZero())
1294: throw new ArithmeticException("not invertible");
1295:
1296: if (b.isOne())
1297: {
1298:
1299:
1300: xy[0] = neg(prevDiv);
1301: xy[1] = ONE;
1302: return;
1303: }
1304:
1305:
1306:
1307:
1308: if (a.words == null)
1309: {
1310: int[] xyInt = euclidInv(b.ival, a.ival % b.ival, a.ival / b.ival);
1311: xy[0] = new BigInteger(xyInt[0]);
1312: xy[1] = new BigInteger(xyInt[1]);
1313: }
1314: else
1315: {
1316: BigInteger rem = new BigInteger();
1317: BigInteger quot = new BigInteger();
1318: divide(a, b, quot, rem, FLOOR);
1319:
1320: rem.canonicalize();
1321: quot.canonicalize();
1322: euclidInv(b, rem, quot, xy);
1323: }
1324:
1325: BigInteger t = xy[0];
1326: xy[0] = add(xy[1], times(t, prevDiv), -1);
1327: xy[1] = t;
1328: }
1329:
1330: public BigInteger modInverse(BigInteger y)
1331: {
1332: if (USING_NATIVE)
1333: {
1334: int dummy = y.signum;
1335: if (mpz.compare(ZERO.mpz) < 1)
1336: throw new ArithmeticException("non-positive modulo");
1337:
1338: BigInteger result = new BigInteger();
1339: mpz.modInverse(y.mpz, result.mpz);
1340: return result;
1341: }
1342:
1343: if (y.isNegative() || y.isZero())
1344: throw new ArithmeticException("non-positive modulo");
1345:
1346:
1347: if (y.isOne())
1348: return ZERO;
1349: if (isOne())
1350: return ONE;
1351:
1352:
1353:
1354:
1355:
1356: BigInteger result = new BigInteger();
1357: boolean swapped = false;
1358:
1359: if (y.words == null)
1360: {
1361:
1362:
1363:
1364:
1365:
1366:
1367: int xval = (words != null || isNegative()) ? mod(y).ival : ival;
1368: int yval = y.ival;
1369:
1370:
1371: if (yval > xval)
1372: {
1373: int tmp = xval; xval = yval; yval = tmp;
1374: swapped = true;
1375: }
1376:
1377:
1378:
1379: result.ival =
1380: euclidInv(yval, xval % yval, xval / yval)[swapped ? 0 : 1];
1381:
1382:
1383:
1384: if (result.ival < 0)
1385: result.ival += y.ival;
1386: }
1387: else
1388: {
1389:
1390: BigInteger x = isNegative() ? this.mod(y) : this;
1391:
1392:
1393: if (x.compareTo(y) < 0)
1394: {
1395: result = x; x = y; y = result;
1396: swapped = true;
1397: }
1398:
1399:
1400: BigInteger rem = new BigInteger();
1401: BigInteger quot = new BigInteger();
1402: divide(x, y, quot, rem, FLOOR);
1403:
1404: rem.canonicalize();
1405: quot.canonicalize();
1406: BigInteger[] xy = new BigInteger[2];
1407: euclidInv(y, rem, quot, xy);
1408: result = swapped ? xy[0] : xy[1];
1409:
1410:
1411:
1412: if (result.isNegative())
1413: result = add(result, swapped ? x : y, 1);
1414: }
1415:
1416: return result;
1417: }
1418:
1419: public BigInteger modPow(BigInteger exponent, BigInteger m)
1420: {
1421: if (USING_NATIVE)
1422: {
1423: int dummy = exponent.signum;
1424: if (m.mpz.compare(ZERO.mpz) < 1)
1425: throw new ArithmeticException("non-positive modulo");
1426:
1427: BigInteger result = new BigInteger();
1428: mpz.modPow(exponent.mpz, m.mpz, result.mpz);
1429: return result;
1430: }
1431:
1432: if (m.isNegative() || m.isZero())
1433: throw new ArithmeticException("non-positive modulo");
1434:
1435: if (exponent.isNegative())
1436: return modInverse(m).modPow(exponent.negate(), m);
1437: if (exponent.isOne())
1438: return mod(m);
1439:
1440:
1441:
1442:
1443:
1444:
1445:
1446:
1447: BigInteger s = ONE;
1448: BigInteger t = this;
1449: BigInteger u = exponent;
1450:
1451: while (!u.isZero())
1452: {
1453: if (u.and(ONE).isOne())
1454: s = times(s, t).mod(m);
1455: u = u.shiftRight(1);
1456: t = times(t, t).mod(m);
1457: }
1458:
1459: return s;
1460: }
1461:
1462:
1463: private static int gcd(int a, int b)
1464: {
1465:
1466: int tmp;
1467: if (b > a)
1468: {
1469: tmp = a; a = b; b = tmp;
1470: }
1471: for(;;)
1472: {
1473: if (b == 0)
1474: return a;
1475: if (b == 1)
1476: return b;
1477: tmp = b;
1478: b = a % b;
1479: a = tmp;
1480: }
1481: }
1482:
1483: public BigInteger gcd(BigInteger y)
1484: {
1485: if (USING_NATIVE)
1486: {
1487: int dummy = y.signum;
1488: BigInteger result = new BigInteger();
1489: mpz.gcd(y.mpz, result.mpz);
1490: return result;
1491: }
1492:
1493: int xval = ival;
1494: int yval = y.ival;
1495: if (words == null)
1496: {
1497: if (xval == 0)
1498: return abs(y);
1499: if (y.words == null
1500: && xval != Integer.MIN_VALUE && yval != Integer.MIN_VALUE)
1501: {
1502: if (xval < 0)
1503: xval = -xval;
1504: if (yval < 0)
1505: yval = -yval;
1506: return valueOf(gcd(xval, yval));
1507: }
1508: xval = 1;
1509: }
1510: if (y.words == null)
1511: {
1512: if (yval == 0)
1513: return abs(this);
1514: yval = 1;
1515: }
1516: int len = (xval > yval ? xval : yval) + 1;
1517: int[] xwords = new int[len];
1518: int[] ywords = new int[len];
1519: getAbsolute(xwords);
1520: y.getAbsolute(ywords);
1521: len = MPN.gcd(xwords, ywords, len);
1522: BigInteger result = new BigInteger(0);
1523: result.ival = len;
1524: result.words = xwords;
1525: return result.canonicalize();
1526: }
1527:
1528:
1541: public boolean isProbablePrime(int certainty)
1542: {
1543: if (certainty < 1)
1544: return true;
1545:
1546: if (USING_NATIVE)
1547: return mpz.testPrimality(certainty) != 0;
1548:
1549:
1559:
1560:
1561: BigInteger rem = new BigInteger();
1562: int i;
1563: for (i = 0; i < primes.length; i++)
1564: {
1565: if (words == null && ival == primes[i])
1566: return true;
1567:
1568: divide(this, smallFixNums[primes[i] - minFixNum], null, rem, TRUNCATE);
1569: if (rem.canonicalize().isZero())
1570: return false;
1571: }
1572:
1573:
1574:
1575:
1576:
1577: BigInteger pMinus1 = add(this, -1);
1578: int b = pMinus1.getLowestSetBit();
1579:
1580:
1581: BigInteger m = pMinus1.divide(valueOf(2L).pow(b));
1582:
1583:
1584:
1585:
1586:
1587:
1588: int bits = this.bitLength();
1589: for (i = 0; i < k.length; i++)
1590: if (bits <= k[i])
1591: break;
1592: int trials = t[i];
1593: if (certainty > 80)
1594: trials *= 2;
1595: BigInteger z;
1596: for (int t = 0; t < trials; t++)
1597: {
1598:
1599:
1600:
1601:
1602: z = smallFixNums[primes[t] - minFixNum].modPow(m, this);
1603: if (z.isOne() || z.equals(pMinus1))
1604: continue;
1605:
1606: for (i = 0; i < b; )
1607: {
1608: if (z.isOne())
1609: return false;
1610: i++;
1611: if (z.equals(pMinus1))
1612: break;
1613:
1614: z = z.modPow(valueOf(2), this);
1615: }
1616:
1617: if (i == b && !z.equals(pMinus1))
1618: return false;
1619: }
1620: return true;
1621: }
1622:
1623: private void setInvert()
1624: {
1625: if (words == null)
1626: ival = ~ival;
1627: else
1628: {
1629: for (int i = ival; --i >= 0; )
1630: words[i] = ~words[i];
1631: }
1632: }
1633:
1634: private void setShiftLeft(BigInteger x, int count)
1635: {
1636: int[] xwords;
1637: int xlen;
1638: if (x.words == null)
1639: {
1640: if (count < 32)
1641: {
1642: set((long) x.ival << count);
1643: return;
1644: }
1645: xwords = new int[1];
1646: xwords[0] = x.ival;
1647: xlen = 1;
1648: }
1649: else
1650: {
1651: xwords = x.words;
1652: xlen = x.ival;
1653: }
1654: int word_count = count >> 5;
1655: count &= 31;
1656: int new_len = xlen + word_count;
1657: if (count == 0)
1658: {
1659: realloc(new_len);
1660: for (int i = xlen; --i >= 0; )
1661: words[i+word_count] = xwords[i];
1662: }
1663: else
1664: {
1665: new_len++;
1666: realloc(new_len);
1667: int shift_out = MPN.lshift(words, word_count, xwords, xlen, count);
1668: count = 32 - count;
1669: words[new_len-1] = (shift_out << count) >> count;
1670: }
1671: ival = new_len;
1672: for (int i = word_count; --i >= 0; )
1673: words[i] = 0;
1674: }
1675:
1676: private void setShiftRight(BigInteger x, int count)
1677: {
1678: if (x.words == null)
1679: set(count < 32 ? x.ival >> count : x.ival < 0 ? -1 : 0);
1680: else if (count == 0)
1681: set(x);
1682: else
1683: {
1684: boolean neg = x.isNegative();
1685: int word_count = count >> 5;
1686: count &= 31;
1687: int d_len = x.ival - word_count;
1688: if (d_len <= 0)
1689: set(neg ? -1 : 0);
1690: else
1691: {
1692: if (words == null || words.length < d_len)
1693: realloc(d_len);
1694: MPN.rshift0 (words, x.words, word_count, d_len, count);
1695: ival = d_len;
1696: if (neg)
1697: words[d_len-1] |= -2 << (31 - count);
1698: }
1699: }
1700: }
1701:
1702: private void setShift(BigInteger x, int count)
1703: {
1704: if (count > 0)
1705: setShiftLeft(x, count);
1706: else
1707: setShiftRight(x, -count);
1708: }
1709:
1710: private static BigInteger shift(BigInteger x, int count)
1711: {
1712: if (x.words == null)
1713: {
1714: if (count <= 0)
1715: return valueOf(count > -32 ? x.ival >> (-count) : x.ival < 0 ? -1 : 0);
1716: if (count < 32)
1717: return valueOf((long) x.ival << count);
1718: }
1719: if (count == 0)
1720: return x;
1721: BigInteger result = new BigInteger(0);
1722: result.setShift(x, count);
1723: return result.canonicalize();
1724: }
1725:
1726: public BigInteger shiftLeft(int n)
1727: {
1728: if (n == 0)
1729: return this;
1730:
1731: if (USING_NATIVE)
1732: {
1733: BigInteger result = new BigInteger();
1734: if (n < 0)
1735: mpz.shiftRight(-n, result.mpz);
1736: else
1737: mpz.shiftLeft(n, result.mpz);
1738: return result;
1739: }
1740:
1741: return shift(this, n);
1742: }
1743:
1744: public BigInteger shiftRight(int n)
1745: {
1746: if (n == 0)
1747: return this;
1748:
1749: if (USING_NATIVE)
1750: {
1751: BigInteger result = new BigInteger();
1752: if (n < 0)
1753: mpz.shiftLeft(-n, result.mpz);
1754: else
1755: mpz.shiftRight(n, result.mpz);
1756: return result;
1757: }
1758:
1759: return shift(this, -n);
1760: }
1761:
1762: private void format(int radix, CPStringBuilder buffer)
1763: {
1764: if (words == null)
1765: buffer.append(Integer.toString(ival, radix));
1766: else if (ival <= 2)
1767: buffer.append(Long.toString(longValue(), radix));
1768: else
1769: {
1770: boolean neg = isNegative();
1771: int[] work;
1772: if (neg || radix != 16)
1773: {
1774: work = new int[ival];
1775: getAbsolute(work);
1776: }
1777: else
1778: work = words;
1779: int len = ival;
1780:
1781: if (radix == 16)
1782: {
1783: if (neg)
1784: buffer.append('-');
1785: int buf_start = buffer.length();
1786: for (int i = len; --i >= 0; )
1787: {
1788: int word = work[i];
1789: for (int j = 8; --j >= 0; )
1790: {
1791: int hex_digit = (word >> (4 * j)) & 0xF;
1792:
1793: if (hex_digit > 0 || buffer.length() > buf_start)
1794: buffer.append(Character.forDigit(hex_digit, 16));
1795: }
1796: }
1797: }
1798: else
1799: {
1800: int i = buffer.length();
1801: for (;;)
1802: {
1803: int digit = MPN.divmod_1(work, work, len, radix);
1804: buffer.append(Character.forDigit(digit, radix));
1805: while (len > 0 && work[len-1] == 0) len--;
1806: if (len == 0)
1807: break;
1808: }
1809: if (neg)
1810: buffer.append('-');
1811:
1812: int j = buffer.length() - 1;
1813: while (i < j)
1814: {
1815: char tmp = buffer.charAt(i);
1816: buffer.setCharAt(i, buffer.charAt(j));
1817: buffer.setCharAt(j, tmp);
1818: i++; j--;
1819: }
1820: }
1821: }
1822: }
1823:
1824: public String toString()
1825: {
1826: return toString(10);
1827: }
1828:
1829: public String toString(int radix)
1830: {
1831: if (USING_NATIVE)
1832: return mpz.toString(radix);
1833:
1834: if (words == null)
1835: return Integer.toString(ival, radix);
1836: if (ival <= 2)
1837: return Long.toString(longValue(), radix);
1838: int buf_size = ival * (MPN.chars_per_word(radix) + 1);
1839: CPStringBuilder buffer = new CPStringBuilder(buf_size);
1840: format(radix, buffer);
1841: return buffer.toString();
1842: }
1843:
1844: public int intValue()
1845: {
1846: if (USING_NATIVE)
1847: {
1848: int result = mpz.absIntValue();
1849: return mpz.compare(ZERO.mpz) < 0 ? - result : result;
1850: }
1851:
1852: if (words == null)
1853: return ival;
1854: return words[0];
1855: }
1856:
1857: public long longValue()
1858: {
1859: if (USING_NATIVE)
1860: {
1861: long result;
1862: result = (abs().shiftRight(32)).mpz.absIntValue();
1863: result <<= 32;
1864: result |= mpz.absIntValue() & 0xFFFFFFFFL;
1865: return this.compareTo(ZERO) < 0 ? - result : result;
1866: }
1867:
1868: if (words == null)
1869: return ival;
1870: if (ival == 1)
1871: return words[0];
1872: return ((long)words[1] << 32) + ((long)words[0] & 0xffffffffL);
1873: }
1874:
1875: public int hashCode()
1876: {
1877:
1878: if (USING_NATIVE)
1879: {
1880:
1881: byte[] bytes = this.toByteArray();
1882: int result = 0;
1883: for (int i = 0; i < bytes.length; i++)
1884: result ^= (bytes[i] & 0xFF) << (8 * (i % 4));
1885: return result;
1886: }
1887:
1888: return words == null ? ival : (words[0] + words[ival - 1]);
1889: }
1890:
1891:
1892: private static boolean equals(BigInteger x, BigInteger y)
1893: {
1894: if (USING_NATIVE)
1895: return x.mpz.compare(y.mpz) == 0;
1896:
1897: if (x.words == null && y.words == null)
1898: return x.ival == y.ival;
1899: if (x.words == null || y.words == null || x.ival != y.ival)
1900: return false;
1901: for (int i = x.ival; --i >= 0; )
1902: {
1903: if (x.words[i] != y.words[i])
1904: return false;
1905: }
1906: return true;
1907: }
1908:
1909:
1910: public boolean equals(Object obj)
1911: {
1912: if (! (obj instanceof BigInteger))
1913: return false;
1914: return equals(this, (BigInteger) obj);
1915: }
1916:
1917: private static BigInteger valueOf(byte[] digits, int byte_len,
1918: boolean negative, int radix)
1919: {
1920: int chars_per_word = MPN.chars_per_word(radix);
1921: int[] words = new int[byte_len / chars_per_word + 1];
1922: int size = MPN.set_str(words, digits, byte_len, radix);
1923: if (size == 0)
1924: return ZERO;
1925: if (words[size-1] < 0)
1926: words[size++] = 0;
1927: if (negative)
1928: negate(words, words, size);
1929: return make(words, size);
1930: }
1931:
1932: public double doubleValue()
1933: {
1934: if (USING_NATIVE)
1935: return mpz.doubleValue();
1936:
1937: if (words == null)
1938: return (double) ival;
1939: if (ival <= 2)
1940: return (double) longValue();
1941: if (isNegative())
1942: return neg(this).roundToDouble(0, true, false);
1943: return roundToDouble(0, false, false);
1944: }
1945:
1946: public float floatValue()
1947: {
1948: return (float) doubleValue();
1949: }
1950:
1951:
1953: private boolean checkBits(int n)
1954: {
1955: if (n <= 0)
1956: return false;
1957: if (words == null)
1958: return n > 31 || ((ival & ((1 << n) - 1)) != 0);
1959: int i;
1960: for (i = 0; i < (n >> 5) ; i++)
1961: if (words[i] != 0)
1962: return true;
1963: return (n & 31) != 0 && (words[i] & ((1 << (n & 31)) - 1)) != 0;
1964: }
1965:
1966:
1974: private double roundToDouble(int exp, boolean neg, boolean remainder)
1975: {
1976:
1977: int il = bitLength();
1978:
1979:
1980:
1981: exp += il - 1;
1982:
1983:
1984:
1985:
1986:
1987: if (exp < -1075)
1988: return neg ? -0.0 : 0.0;
1989:
1990:
1991: if (exp > 1023)
1992: return neg ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
1993:
1994:
1995:
1996: int ml = (exp >= -1022 ? 53 : 53 + exp + 1022);
1997:
1998:
1999: long m;
2000: int excess_bits = il - (ml + 1);
2001: if (excess_bits > 0)
2002: m = ((words == null) ? ival >> excess_bits
2003: : MPN.rshift_long(words, ival, excess_bits));
2004: else
2005: m = longValue() << (- excess_bits);
2006:
2007:
2008:
2009: if (exp == 1023 && ((m >> 1) == (1L << 53) - 1))
2010: {
2011: if (remainder || checkBits(il - ml))
2012: return neg ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
2013: else
2014: return neg ? - Double.MAX_VALUE : Double.MAX_VALUE;
2015: }
2016:
2017:
2018:
2019: if ((m & 1) == 1
2020: && ((m & 2) == 2 || remainder || checkBits(excess_bits)))
2021: {
2022: m += 2;
2023:
2024: if ((m & (1L << 54)) != 0)
2025: {
2026: exp++;
2027:
2028: m >>= 1;
2029: }
2030:
2031:
2032: else if (ml == 52 && (m & (1L << 53)) != 0)
2033: exp++;
2034: }
2035:
2036:
2037: m >>= 1;
2038:
2039: long bits_sign = neg ? (1L << 63) : 0;
2040: exp += 1023;
2041: long bits_exp = (exp <= 0) ? 0 : ((long)exp) << 52;
2042: long bits_mant = m & ~(1L << 52);
2043: return Double.longBitsToDouble(bits_sign | bits_exp | bits_mant);
2044: }
2045:
2046:
2050: private void getAbsolute(int[] words)
2051: {
2052: int len;
2053: if (this.words == null)
2054: {
2055: len = 1;
2056: words[0] = this.ival;
2057: }
2058: else
2059: {
2060: len = this.ival;
2061: for (int i = len; --i >= 0; )
2062: words[i] = this.words[i];
2063: }
2064: if (words[len - 1] < 0)
2065: negate(words, words, len);
2066: for (int i = words.length; --i > len; )
2067: words[i] = 0;
2068: }
2069:
2070:
2073: private static boolean negate(int[] dest, int[] src, int len)
2074: {
2075: long carry = 1;
2076: boolean negative = src[len-1] < 0;
2077: for (int i = 0; i < len; i++)
2078: {
2079: carry += ((long) (~src[i]) & 0xffffffffL);
2080: dest[i] = (int) carry;
2081: carry >>= 32;
2082: }
2083: return (negative && dest[len-1] < 0);
2084: }
2085:
2086:
2088: private void setNegative(BigInteger x)
2089: {
2090: int len = x.ival;
2091: if (x.words == null)
2092: {
2093: if (len == Integer.MIN_VALUE)
2094: set(- (long) len);
2095: else
2096: set(-len);
2097: return;
2098: }
2099: realloc(len + 1);
2100: if (negate(words, x.words, len))
2101: words[len++] = 0;
2102: ival = len;
2103: }
2104:
2105:
2106: private void setNegative()
2107: {
2108: setNegative(this);
2109: }
2110:
2111: private static BigInteger abs(BigInteger x)
2112: {
2113: return x.isNegative() ? neg(x) : x;
2114: }
2115:
2116: public BigInteger abs()
2117: {
2118: if (USING_NATIVE)
2119: {
2120: BigInteger result = new BigInteger();
2121: mpz.abs(result.mpz);
2122: return result;
2123: }
2124:
2125: return abs(this);
2126: }
2127:
2128: private static BigInteger neg(BigInteger x)
2129: {
2130: if (x.words == null && x.ival != Integer.MIN_VALUE)
2131: return valueOf(- x.ival);
2132: BigInteger result = new BigInteger(0);
2133: result.setNegative(x);
2134: return result.canonicalize();
2135: }
2136:
2137: public BigInteger negate()
2138: {
2139: if (USING_NATIVE)
2140: {
2141: BigInteger result = new BigInteger();
2142: mpz.negate(result.mpz);
2143: return result;
2144: }
2145:
2146: return neg(this);
2147: }
2148:
2149:
2152: public int bitLength()
2153: {
2154: if (USING_NATIVE)
2155: return mpz.bitLength();
2156:
2157: if (words == null)
2158: return MPN.intLength(ival);
2159: return MPN.intLength(words, ival);
2160: }
2161:
2162: public byte[] toByteArray()
2163: {
2164: if (signum() == 0)
2165: return new byte[1];
2166:
2167: if (USING_NATIVE)
2168: {
2169:
2170:
2171:
2172:
2173:
2174:
2175: int bits = bitLength();
2176: if (bits % 8 == 0 || this.signum() == 1)
2177: bits++;
2178: byte[] bytes = new byte[(bits + 7) / 8];
2179: mpz.toByteArray(bytes);
2180: return bytes;
2181: }
2182:
2183:
2184:
2185:
2186: byte[] bytes = new byte[(bitLength() + 1 + 7) / 8];
2187: int nbytes = bytes.length;
2188:
2189: int wptr = 0;
2190: int word;
2191:
2192:
2193:
2194: while (nbytes > 4)
2195: {
2196: word = words[wptr++];
2197: for (int i = 4; i > 0; --i, word >>= 8)
2198: bytes[--nbytes] = (byte) word;
2199: }
2200:
2201:
2202: word = (words == null) ? ival : words[wptr];
2203: for ( ; nbytes > 0; word >>= 8)
2204: bytes[--nbytes] = (byte) word;
2205:
2206: return bytes;
2207: }
2208:
2209:
2212: private static int swappedOp(int op)
2213: {
2214: return
2215: "\000\001\004\005\002\003\006\007\010\011\014\015\012\013\016\017"
2216: .charAt(op);
2217: }
2218:
2219:
2220: private static BigInteger bitOp(int op, BigInteger x, BigInteger y)
2221: {
2222: switch (op)
2223: {
2224: case 0: return ZERO;
2225: case 1: return x.and(y);
2226: case 3: return x;
2227: case 5: return y;
2228: case 15: return valueOf(-1);
2229: }
2230: BigInteger result = new BigInteger();
2231: setBitOp(result, op, x, y);
2232: return result.canonicalize();
2233: }
2234:
2235:
2236: private static void setBitOp(BigInteger result, int op,
2237: BigInteger x, BigInteger y)
2238: {
2239: if ((y.words != null) && (x.words == null || x.ival < y.ival))
2240: {
2241: BigInteger temp = x; x = y; y = temp;
2242: op = swappedOp(op);
2243: }
2244: int xi;
2245: int yi;
2246: int xlen, ylen;
2247: if (y.words == null)
2248: {
2249: yi = y.ival;
2250: ylen = 1;
2251: }
2252: else
2253: {
2254: yi = y.words[0];
2255: ylen = y.ival;
2256: }
2257: if (x.words == null)
2258: {
2259: xi = x.ival;
2260: xlen = 1;
2261: }
2262: else
2263: {
2264: xi = x.words[0];
2265: xlen = x.ival;
2266: }
2267: if (xlen > 1)
2268: result.realloc(xlen);
2269: int[] w = result.words;
2270: int i = 0;
2271:
2272:
2273:
2274:
2275: int finish = 0;
2276: int ni;
2277: switch (op)
2278: {
2279: case 0:
2280: ni = 0;
2281: break;
2282: case 1:
2283: for (;;)
2284: {
2285: ni = xi & yi;
2286: if (i+1 >= ylen) break;
2287: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2288: }
2289: if (yi < 0) finish = 1;
2290: break;
2291: case 2:
2292: for (;;)
2293: {
2294: ni = xi & ~yi;
2295: if (i+1 >= ylen) break;
2296: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2297: }
2298: if (yi >= 0) finish = 1;
2299: break;
2300: case 3:
2301: ni = xi;
2302: finish = 1;
2303: break;
2304: case 4:
2305: for (;;)
2306: {
2307: ni = ~xi & yi;
2308: if (i+1 >= ylen) break;
2309: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2310: }
2311: if (yi < 0) finish = 2;
2312: break;
2313: case 5:
2314: for (;;)
2315: {
2316: ni = yi;
2317: if (i+1 >= ylen) break;
2318: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2319: }
2320: break;
2321: case 6:
2322: for (;;)
2323: {
2324: ni = xi ^ yi;
2325: if (i+1 >= ylen) break;
2326: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2327: }
2328: finish = yi < 0 ? 2 : 1;
2329: break;
2330: case 7:
2331: for (;;)
2332: {
2333: ni = xi | yi;
2334: if (i+1 >= ylen) break;
2335: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2336: }
2337: if (yi >= 0) finish = 1;
2338: break;
2339: case 8:
2340: for (;;)
2341: {
2342: ni = ~(xi | yi);
2343: if (i+1 >= ylen) break;
2344: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2345: }
2346: if (yi >= 0) finish = 2;
2347: break;
2348: case 9:
2349: for (;;)
2350: {
2351: ni = ~(xi ^ yi);
2352: if (i+1 >= ylen) break;
2353: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2354: }
2355: finish = yi >= 0 ? 2 : 1;
2356: break;
2357: case 10:
2358: for (;;)
2359: {
2360: ni = ~yi;
2361: if (i+1 >= ylen) break;
2362: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2363: }
2364: break;
2365: case 11:
2366: for (;;)
2367: {
2368: ni = xi | ~yi;
2369: if (i+1 >= ylen) break;
2370: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2371: }
2372: if (yi < 0) finish = 1;
2373: break;
2374: case 12:
2375: ni = ~xi;
2376: finish = 2;
2377: break;
2378: case 13:
2379: for (;;)
2380: {
2381: ni = ~xi | yi;
2382: if (i+1 >= ylen) break;
2383: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2384: }
2385: if (yi >= 0) finish = 2;
2386: break;
2387: case 14:
2388: for (;;)
2389: {
2390: ni = ~(xi & yi);
2391: if (i+1 >= ylen) break;
2392: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2393: }
2394: if (yi < 0) finish = 2;
2395: break;
2396: default:
2397: case 15:
2398: ni = -1;
2399: break;
2400: }
2401:
2402:
2403: if (i+1 == xlen)
2404: finish = 0;
2405: switch (finish)
2406: {
2407: case 0:
2408: if (i == 0 && w == null)
2409: {
2410: result.ival = ni;
2411: return;
2412: }
2413: w[i++] = ni;
2414: break;
2415: case 1: w[i] = ni; while (++i < xlen) w[i] = x.words[i]; break;
2416: case 2: w[i] = ni; while (++i < xlen) w[i] = ~x.words[i]; break;
2417: }
2418: result.ival = i;
2419: }
2420:
2421:
2422: private static BigInteger and(BigInteger x, int y)
2423: {
2424: if (x.words == null)
2425: return valueOf(x.ival & y);
2426: if (y >= 0)
2427: return valueOf(x.words[0] & y);
2428: int len = x.ival;
2429: int[] words = new int[len];
2430: words[0] = x.words[0] & y;
2431: while (--len > 0)
2432: words[len] = x.words[len];
2433: return make(words, x.ival);
2434: }
2435:
2436:
2437: public BigInteger and(BigInteger y)
2438: {
2439: if (USING_NATIVE)
2440: {
2441: int dummy = y.signum;
2442: BigInteger result = new BigInteger();
2443: mpz.and(y.mpz, result.mpz);
2444: return result;
2445: }
2446:
2447: if (y.words == null)
2448: return and(this, y.ival);
2449: else if (words == null)
2450: return and(y, ival);
2451:
2452: BigInteger x = this;
2453: if (ival < y.ival)
2454: {
2455: BigInteger temp = this; x = y; y = temp;
2456: }
2457: int i;
2458: int len = y.isNegative() ? x.ival : y.ival;
2459: int[] words = new int[len];
2460: for (i = 0; i < y.ival; i++)
2461: words[i] = x.words[i] & y.words[i];
2462: for ( ; i < len; i++)
2463: words[i] = x.words[i];
2464: return make(words, len);
2465: }
2466:
2467:
2468: public BigInteger or(BigInteger y)
2469: {
2470: if (USING_NATIVE)
2471: {
2472: int dummy = y.signum;
2473: BigInteger result = new BigInteger();
2474: mpz.or(y.mpz, result.mpz);
2475: return result;
2476: }
2477:
2478: return bitOp(7, this, y);
2479: }
2480:
2481:
2482: public BigInteger xor(BigInteger y)
2483: {
2484: if (USING_NATIVE)
2485: {
2486: int dummy = y.signum;
2487: BigInteger result = new BigInteger();
2488: mpz.xor(y.mpz, result.mpz);
2489: return result;
2490: }
2491:
2492: return bitOp(6, this, y);
2493: }
2494:
2495:
2496: public BigInteger not()
2497: {
2498: if (USING_NATIVE)
2499: {
2500: BigInteger result = new BigInteger();
2501: mpz.not(result.mpz);
2502: return result;
2503: }
2504:
2505: return bitOp(12, this, ZERO);
2506: }
2507:
2508: public BigInteger andNot(BigInteger val)
2509: {
2510: if (USING_NATIVE)
2511: {
2512: int dummy = val.signum;
2513: BigInteger result = new BigInteger();
2514: mpz.andNot(val.mpz, result.mpz);
2515: return result;
2516: }
2517:
2518: return and(val.not());
2519: }
2520:
2521: public BigInteger clearBit(int n)
2522: {
2523: if (n < 0)
2524: throw new ArithmeticException();
2525:
2526: if (USING_NATIVE)
2527: {
2528: BigInteger result = new BigInteger();
2529: mpz.setBit(n, false, result.mpz);
2530: return result;
2531: }
2532:
2533: return and(ONE.shiftLeft(n).not());
2534: }
2535:
2536: public BigInteger setBit(int n)
2537: {
2538: if (n < 0)
2539: throw new ArithmeticException();
2540:
2541: if (USING_NATIVE)
2542: {
2543: BigInteger result = new BigInteger();
2544: mpz.setBit(n, true, result.mpz);
2545: return result;
2546: }
2547:
2548: return or(ONE.shiftLeft(n));
2549: }
2550:
2551: public boolean testBit(int n)
2552: {
2553: if (n < 0)
2554: throw new ArithmeticException();
2555:
2556: if (USING_NATIVE)
2557: return mpz.testBit(n) != 0;
2558:
2559: return !and(ONE.shiftLeft(n)).isZero();
2560: }
2561:
2562: public BigInteger flipBit(int n)
2563: {
2564: if (n < 0)
2565: throw new ArithmeticException();
2566:
2567: if (USING_NATIVE)
2568: {
2569: BigInteger result = new BigInteger();
2570: mpz.flipBit(n, result.mpz);
2571: return result;
2572: }
2573:
2574: return xor(ONE.shiftLeft(n));
2575: }
2576:
2577: public int getLowestSetBit()
2578: {
2579: if (USING_NATIVE)
2580: return mpz.compare(ZERO.mpz) == 0 ? -1 : mpz.lowestSetBit();
2581:
2582: if (isZero())
2583: return -1;
2584:
2585: if (words == null)
2586: return MPN.findLowestBit(ival);
2587: else
2588: return MPN.findLowestBit(words);
2589: }
2590:
2591:
2592: private static final byte[] bit4_count = { 0, 1, 1, 2, 1, 2, 2, 3,
2593: 1, 2, 2, 3, 2, 3, 3, 4};
2594:
2595: private static int bitCount(int i)
2596: {
2597: int count = 0;
2598: while (i != 0)
2599: {
2600: count += bit4_count[i & 15];
2601: i >>>= 4;
2602: }
2603: return count;
2604: }
2605:
2606: private static int bitCount(int[] x, int len)
2607: {
2608: int count = 0;
2609: while (--len >= 0)
2610: count += bitCount(x[len]);
2611: return count;
2612: }
2613:
2614:
2616: public int bitCount()
2617: {
2618: if (USING_NATIVE)
2619: return mpz.bitCount();
2620:
2621: int i, x_len;
2622: int[] x_words = words;
2623: if (x_words == null)
2624: {
2625: x_len = 1;
2626: i = bitCount(ival);
2627: }
2628: else
2629: {
2630: x_len = ival;
2631: i = bitCount(x_words, x_len);
2632: }
2633: return isNegative() ? x_len * 32 - i : i;
2634: }
2635:
2636: private void readObject(ObjectInputStream s)
2637: throws IOException, ClassNotFoundException
2638: {
2639: if (USING_NATIVE)
2640: {
2641: mpz = new GMP();
2642: s.defaultReadObject();
2643: if (signum != 0)
2644: mpz.fromByteArray(magnitude);
2645:
2646: }
2647: else
2648: {
2649: s.defaultReadObject();
2650: if (magnitude.length == 0 || signum == 0)
2651: {
2652: this.ival = 0;
2653: this.words = null;
2654: }
2655: else
2656: {
2657: words = byteArrayToIntArray(magnitude, signum < 0 ? -1 : 0);
2658: BigInteger result = make(words, words.length);
2659: this.ival = result.ival;
2660: this.words = result.words;
2661: }
2662: }
2663: }
2664:
2665: private void writeObject(ObjectOutputStream s)
2666: throws IOException, ClassNotFoundException
2667: {
2668: signum = signum();
2669: magnitude = signum == 0 ? new byte[0] : toByteArray();
2670: s.defaultWriteObject();
2671: magnitude = null;
2672: }
2673:
2674:
2675:
2676: }