1:
37:
38:
39: package ;
40:
41: import ;
42:
43: import ;
44: import ;
45: import ;
46: import ;
47:
48:
60: public class BigInteger extends Number implements Comparable
61: {
62:
66: private transient int ival;
67: private transient int[] words;
68:
69:
70: private int bitCount = -1;
71: private int bitLength = -1;
72: private int firstNonzeroByteNum = -2;
73: private int lowestSetBit = -2;
74: private byte[] magnitude;
75: private int signum;
76: private static final long serialVersionUID = -8287574255936472291L;
77:
78:
79:
81: private static final int minFixNum = -100;
82: private static final int maxFixNum = 1024;
83: private static final int numFixNum = maxFixNum-minFixNum+1;
84: private static final BigInteger[] smallFixNums = new BigInteger[numFixNum];
85:
86: static {
87: for (int i = numFixNum; --i >= 0; )
88: smallFixNums[i] = new BigInteger(i + minFixNum);
89: }
90:
91:
95: public static final BigInteger ZERO = smallFixNums[-minFixNum];
96:
97:
101: public static final BigInteger ONE = smallFixNums[1 - minFixNum];
102:
103:
107: public static final BigInteger TEN = smallFixNums[10 - minFixNum];
108:
109:
110: private static final int FLOOR = 1;
111: private static final int CEILING = 2;
112: private static final int TRUNCATE = 3;
113: private static final int ROUND = 4;
114:
115:
118: private static final int[] primes =
119: { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
120: 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107,
121: 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181,
122: 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251 };
123:
124:
125: private static final int[] k =
126: {100,150,200,250,300,350,400,500,600,800,1250, Integer.MAX_VALUE};
127: private static final int[] t =
128: { 27, 18, 15, 12, 9, 8, 7, 6, 5, 4, 3, 2};
129:
130: private BigInteger()
131: {
132: }
133:
134:
135: private BigInteger(int value)
136: {
137: ival = value;
138: }
139:
140: public BigInteger(String val, int radix)
141: {
142: BigInteger result = valueOf(val, radix);
143: this.ival = result.ival;
144: this.words = result.words;
145: }
146:
147: public BigInteger(String val)
148: {
149: this(val, 10);
150: }
151:
152:
153: public BigInteger(byte[] val)
154: {
155: if (val == null || val.length < 1)
156: throw new NumberFormatException();
157:
158: words = byteArrayToIntArray(val, val[0] < 0 ? -1 : 0);
159: BigInteger result = make(words, words.length);
160: this.ival = result.ival;
161: this.words = result.words;
162: }
163:
164: public BigInteger(int signum, byte[] magnitude)
165: {
166: if (magnitude == null || signum > 1 || signum < -1)
167: throw new NumberFormatException();
168:
169: if (signum == 0)
170: {
171: int i;
172: for (i = magnitude.length - 1; i >= 0 && magnitude[i] == 0; --i)
173: ;
174: if (i >= 0)
175: throw new NumberFormatException();
176: return;
177: }
178:
179:
180: words = byteArrayToIntArray(magnitude, 0);
181: BigInteger result = make(words, words.length);
182: this.ival = result.ival;
183: this.words = result.words;
184:
185: if (signum < 0)
186: setNegative();
187: }
188:
189: public BigInteger(int numBits, Random rnd)
190: {
191: if (numBits < 0)
192: throw new IllegalArgumentException();
193:
194: init(numBits, rnd);
195: }
196:
197: private void init(int numBits, Random rnd)
198: {
199: int highbits = numBits & 31;
200: if (highbits > 0)
201: highbits = rnd.nextInt() >>> (32 - highbits);
202: int nwords = numBits / 32;
203:
204: while (highbits == 0 && nwords > 0)
205: {
206: highbits = rnd.nextInt();
207: --nwords;
208: }
209: if (nwords == 0 && highbits >= 0)
210: {
211: ival = highbits;
212: }
213: else
214: {
215: ival = highbits < 0 ? nwords + 2 : nwords + 1;
216: words = new int[ival];
217: words[nwords] = highbits;
218: while (--nwords >= 0)
219: words[nwords] = rnd.nextInt();
220: }
221: }
222:
223: public BigInteger(int bitLength, int certainty, Random rnd)
224: {
225: this(bitLength, rnd);
226:
227:
228: while (true)
229: {
230: if (isProbablePrime(certainty))
231: return;
232:
233: init(bitLength, rnd);
234: }
235: }
236:
237:
246: public static BigInteger probablePrime(int bitLength, Random rnd)
247: {
248: if (bitLength < 2)
249: throw new ArithmeticException();
250:
251: return new BigInteger(bitLength, 100, rnd);
252: }
253:
254:
255: public static BigInteger valueOf(long val)
256: {
257: if (val >= minFixNum && val <= maxFixNum)
258: return smallFixNums[(int) val - minFixNum];
259: int i = (int) val;
260: if ((long) i == val)
261: return new BigInteger(i);
262: BigInteger result = alloc(2);
263: result.ival = 2;
264: result.words[0] = i;
265: result.words[1] = (int)(val >> 32);
266: return result;
267: }
268:
269:
271: private static BigInteger make(int[] words, int len)
272: {
273: if (words == null)
274: return valueOf(len);
275: len = BigInteger.wordsNeeded(words, len);
276: if (len <= 1)
277: return len == 0 ? ZERO : valueOf(words[0]);
278: BigInteger num = new BigInteger();
279: num.words = words;
280: num.ival = len;
281: return num;
282: }
283:
284:
285: private static int[] byteArrayToIntArray(byte[] bytes, int sign)
286: {
287:
288: int[] words = new int[bytes.length/4 + 1];
289: int nwords = words.length;
290:
291:
292: int bptr = 0;
293: int word = sign;
294: for (int i = bytes.length % 4; i > 0; --i, bptr++)
295: word = (word << 8) | (bytes[bptr] & 0xff);
296: words[--nwords] = word;
297:
298:
299: while (nwords > 0)
300: words[--nwords] = bytes[bptr++] << 24 |
301: (bytes[bptr++] & 0xff) << 16 |
302: (bytes[bptr++] & 0xff) << 8 |
303: (bytes[bptr++] & 0xff);
304: return words;
305: }
306:
307:
310: private static BigInteger alloc(int nwords)
311: {
312: BigInteger result = new BigInteger();
313: if (nwords > 1)
314: result.words = new int[nwords];
315: return result;
316: }
317:
318:
321: private void realloc(int nwords)
322: {
323: if (nwords == 0)
324: {
325: if (words != null)
326: {
327: if (ival > 0)
328: ival = words[0];
329: words = null;
330: }
331: }
332: else if (words == null
333: || words.length < nwords
334: || words.length > nwords + 2)
335: {
336: int[] new_words = new int [nwords];
337: if (words == null)
338: {
339: new_words[0] = ival;
340: ival = 1;
341: }
342: else
343: {
344: if (nwords < ival)
345: ival = nwords;
346: System.arraycopy(words, 0, new_words, 0, ival);
347: }
348: words = new_words;
349: }
350: }
351:
352: private boolean isNegative()
353: {
354: return (words == null ? ival : words[ival - 1]) < 0;
355: }
356:
357: public int signum()
358: {
359: if (ival == 0 && words == null)
360: return 0;
361: int top = words == null ? ival : words[ival-1];
362: return top < 0 ? -1 : 1;
363: }
364:
365: private static int compareTo(BigInteger x, BigInteger y)
366: {
367: if (x.words == null && y.words == null)
368: return x.ival < y.ival ? -1 : x.ival > y.ival ? 1 : 0;
369: boolean x_negative = x.isNegative();
370: boolean y_negative = y.isNegative();
371: if (x_negative != y_negative)
372: return x_negative ? -1 : 1;
373: int x_len = x.words == null ? 1 : x.ival;
374: int y_len = y.words == null ? 1 : y.ival;
375: if (x_len != y_len)
376: return (x_len > y_len) != x_negative ? 1 : -1;
377: return MPN.cmp(x.words, y.words, x_len);
378: }
379:
380:
381: public int compareTo(Object obj)
382: {
383: if (obj instanceof BigInteger)
384: return compareTo(this, (BigInteger) obj);
385: throw new ClassCastException();
386: }
387:
388: public int compareTo(BigInteger val)
389: {
390: return compareTo(this, val);
391: }
392:
393: public BigInteger min(BigInteger val)
394: {
395: return compareTo(this, val) < 0 ? this : val;
396: }
397:
398: public BigInteger max(BigInteger val)
399: {
400: return compareTo(this, val) > 0 ? this : val;
401: }
402:
403: private boolean isZero()
404: {
405: return words == null && ival == 0;
406: }
407:
408: private boolean isOne()
409: {
410: return words == null && ival == 1;
411: }
412:
413:
417: private static int wordsNeeded(int[] words, int len)
418: {
419: int i = len;
420: if (i > 0)
421: {
422: int word = words[--i];
423: if (word == -1)
424: {
425: while (i > 0 && (word = words[i - 1]) < 0)
426: {
427: i--;
428: if (word != -1) break;
429: }
430: }
431: else
432: {
433: while (word == 0 && i > 0 && (word = words[i - 1]) >= 0) i--;
434: }
435: }
436: return i + 1;
437: }
438:
439: private BigInteger canonicalize()
440: {
441: if (words != null
442: && (ival = BigInteger.wordsNeeded(words, ival)) <= 1)
443: {
444: if (ival == 1)
445: ival = words[0];
446: words = null;
447: }
448: if (words == null && ival >= minFixNum && ival <= maxFixNum)
449: return smallFixNums[ival - minFixNum];
450: return this;
451: }
452:
453:
454: private static BigInteger add(int x, int y)
455: {
456: return valueOf((long) x + (long) y);
457: }
458:
459:
460: private static BigInteger add(BigInteger x, int y)
461: {
462: if (x.words == null)
463: return BigInteger.add(x.ival, y);
464: BigInteger result = new BigInteger(0);
465: result.setAdd(x, y);
466: return result.canonicalize();
467: }
468:
469:
471: private void setAdd(BigInteger x, int y)
472: {
473: if (x.words == null)
474: {
475: set((long) x.ival + (long) y);
476: return;
477: }
478: int len = x.ival;
479: realloc(len + 1);
480: long carry = y;
481: for (int i = 0; i < len; i++)
482: {
483: carry += ((long) x.words[i] & 0xffffffffL);
484: words[i] = (int) carry;
485: carry >>= 32;
486: }
487: if (x.words[len - 1] < 0)
488: carry--;
489: words[len] = (int) carry;
490: ival = wordsNeeded(words, len + 1);
491: }
492:
493:
494: private void setAdd(int y)
495: {
496: setAdd(this, y);
497: }
498:
499:
500: private void set(long y)
501: {
502: int i = (int) y;
503: if ((long) i == y)
504: {
505: ival = i;
506: words = null;
507: }
508: else
509: {
510: realloc(2);
511: words[0] = i;
512: words[1] = (int) (y >> 32);
513: ival = 2;
514: }
515: }
516:
517:
519: private void set(int[] words, int length)
520: {
521: this.ival = length;
522: this.words = words;
523: }
524:
525:
526: private void set(BigInteger y)
527: {
528: if (y.words == null)
529: set(y.ival);
530: else if (this != y)
531: {
532: realloc(y.ival);
533: System.arraycopy(y.words, 0, words, 0, y.ival);
534: ival = y.ival;
535: }
536: }
537:
538:
539: private static BigInteger add(BigInteger x, BigInteger y, int k)
540: {
541: if (x.words == null && y.words == null)
542: return valueOf((long) k * (long) y.ival + (long) x.ival);
543: if (k != 1)
544: {
545: if (k == -1)
546: y = BigInteger.neg(y);
547: else
548: y = BigInteger.times(y, valueOf(k));
549: }
550: if (x.words == null)
551: return BigInteger.add(y, x.ival);
552: if (y.words == null)
553: return BigInteger.add(x, y.ival);
554:
555: if (y.ival > x.ival)
556: {
557: BigInteger tmp = x; x = y; y = tmp;
558: }
559: BigInteger result = alloc(x.ival + 1);
560: int i = y.ival;
561: long carry = MPN.add_n(result.words, x.words, y.words, i);
562: long y_ext = y.words[i - 1] < 0 ? 0xffffffffL : 0;
563: for (; i < x.ival; i++)
564: {
565: carry += ((long) x.words[i] & 0xffffffffL) + y_ext;;
566: result.words[i] = (int) carry;
567: carry >>>= 32;
568: }
569: if (x.words[i - 1] < 0)
570: y_ext--;
571: result.words[i] = (int) (carry + y_ext);
572: result.ival = i+1;
573: return result.canonicalize();
574: }
575:
576: public BigInteger add(BigInteger val)
577: {
578: return add(this, val, 1);
579: }
580:
581: public BigInteger subtract(BigInteger val)
582: {
583: return add(this, val, -1);
584: }
585:
586: private static BigInteger times(BigInteger x, int y)
587: {
588: if (y == 0)
589: return ZERO;
590: if (y == 1)
591: return x;
592: int[] xwords = x.words;
593: int xlen = x.ival;
594: if (xwords == null)
595: return valueOf((long) xlen * (long) y);
596: boolean negative;
597: BigInteger result = BigInteger.alloc(xlen + 1);
598: if (xwords[xlen - 1] < 0)
599: {
600: negative = true;
601: negate(result.words, xwords, xlen);
602: xwords = result.words;
603: }
604: else
605: negative = false;
606: if (y < 0)
607: {
608: negative = !negative;
609: y = -y;
610: }
611: result.words[xlen] = MPN.mul_1(result.words, xwords, xlen, y);
612: result.ival = xlen + 1;
613: if (negative)
614: result.setNegative();
615: return result.canonicalize();
616: }
617:
618: private static BigInteger times(BigInteger x, BigInteger y)
619: {
620: if (y.words == null)
621: return times(x, y.ival);
622: if (x.words == null)
623: return times(y, x.ival);
624: boolean negative = false;
625: int[] xwords;
626: int[] ywords;
627: int xlen = x.ival;
628: int ylen = y.ival;
629: if (x.isNegative())
630: {
631: negative = true;
632: xwords = new int[xlen];
633: negate(xwords, x.words, xlen);
634: }
635: else
636: {
637: negative = false;
638: xwords = x.words;
639: }
640: if (y.isNegative())
641: {
642: negative = !negative;
643: ywords = new int[ylen];
644: negate(ywords, y.words, ylen);
645: }
646: else
647: ywords = y.words;
648:
649: if (xlen < ylen)
650: {
651: int[] twords = xwords; xwords = ywords; ywords = twords;
652: int tlen = xlen; xlen = ylen; ylen = tlen;
653: }
654: BigInteger result = BigInteger.alloc(xlen+ylen);
655: MPN.mul(result.words, xwords, xlen, ywords, ylen);
656: result.ival = xlen+ylen;
657: if (negative)
658: result.setNegative();
659: return result.canonicalize();
660: }
661:
662: public BigInteger multiply(BigInteger y)
663: {
664: return times(this, y);
665: }
666:
667: private static void divide(long x, long y,
668: BigInteger quotient, BigInteger remainder,
669: int rounding_mode)
670: {
671: boolean xNegative, yNegative;
672: if (x < 0)
673: {
674: xNegative = true;
675: if (x == Long.MIN_VALUE)
676: {
677: divide(valueOf(x), valueOf(y),
678: quotient, remainder, rounding_mode);
679: return;
680: }
681: x = -x;
682: }
683: else
684: xNegative = false;
685:
686: if (y < 0)
687: {
688: yNegative = true;
689: if (y == Long.MIN_VALUE)
690: {
691: if (rounding_mode == TRUNCATE)
692: {
693: if (quotient != null)
694: quotient.set(0);
695: if (remainder != null)
696: remainder.set(x);
697: }
698: else
699: divide(valueOf(x), valueOf(y),
700: quotient, remainder, rounding_mode);
701: return;
702: }
703: y = -y;
704: }
705: else
706: yNegative = false;
707:
708: long q = x / y;
709: long r = x % y;
710: boolean qNegative = xNegative ^ yNegative;
711:
712: boolean add_one = false;
713: if (r != 0)
714: {
715: switch (rounding_mode)
716: {
717: case TRUNCATE:
718: break;
719: case CEILING:
720: case FLOOR:
721: if (qNegative == (rounding_mode == FLOOR))
722: add_one = true;
723: break;
724: case ROUND:
725: add_one = r > ((y - (q & 1)) >> 1);
726: break;
727: }
728: }
729: if (quotient != null)
730: {
731: if (add_one)
732: q++;
733: if (qNegative)
734: q = -q;
735: quotient.set(q);
736: }
737: if (remainder != null)
738: {
739:
740: if (add_one)
741: {
742:
743: r = y - r;
744:
745:
746: xNegative = ! xNegative;
747: }
748: else
749: {
750:
751:
752: }
753: if (xNegative)
754: r = -r;
755: remainder.set(r);
756: }
757: }
758:
759:
767: private static void divide(BigInteger x, BigInteger y,
768: BigInteger quotient, BigInteger remainder,
769: int rounding_mode)
770: {
771: if ((x.words == null || x.ival <= 2)
772: && (y.words == null || y.ival <= 2))
773: {
774: long x_l = x.longValue();
775: long y_l = y.longValue();
776: if (x_l != Long.MIN_VALUE && y_l != Long.MIN_VALUE)
777: {
778: divide(x_l, y_l, quotient, remainder, rounding_mode);
779: return;
780: }
781: }
782:
783: boolean xNegative = x.isNegative();
784: boolean yNegative = y.isNegative();
785: boolean qNegative = xNegative ^ yNegative;
786:
787: int ylen = y.words == null ? 1 : y.ival;
788: int[] ywords = new int[ylen];
789: y.getAbsolute(ywords);
790: while (ylen > 1 && ywords[ylen - 1] == 0) ylen--;
791:
792: int xlen = x.words == null ? 1 : x.ival;
793: int[] xwords = new int[xlen+2];
794: x.getAbsolute(xwords);
795: while (xlen > 1 && xwords[xlen-1] == 0) xlen--;
796:
797: int qlen, rlen;
798:
799: int cmpval = MPN.cmp(xwords, xlen, ywords, ylen);
800: if (cmpval < 0)
801: {
802: int[] rwords = xwords; xwords = ywords; ywords = rwords;
803: rlen = xlen; qlen = 1; xwords[0] = 0;
804: }
805: else if (cmpval == 0)
806: {
807: xwords[0] = 1; qlen = 1;
808: ywords[0] = 0; rlen = 1;
809: }
810: else if (ylen == 1)
811: {
812: qlen = xlen;
813:
814:
815:
816:
817: if (ywords[0] == 1 && xwords[xlen-1] < 0)
818: qlen++;
819: rlen = 1;
820: ywords[0] = MPN.divmod_1(xwords, xwords, xlen, ywords[0]);
821: }
822: else
823: {
824:
825:
826:
827:
828: int nshift = MPN.count_leading_zeros(ywords[ylen - 1]);
829: if (nshift != 0)
830: {
831:
832:
833: MPN.lshift(ywords, 0, ywords, ylen, nshift);
834:
835:
836:
837: int x_high = MPN.lshift(xwords, 0, xwords, xlen, nshift);
838: xwords[xlen++] = x_high;
839: }
840:
841: if (xlen == ylen)
842: xwords[xlen++] = 0;
843: MPN.divide(xwords, xlen, ywords, ylen);
844: rlen = ylen;
845: MPN.rshift0 (ywords, xwords, 0, rlen, nshift);
846:
847: qlen = xlen + 1 - ylen;
848: if (quotient != null)
849: {
850: for (int i = 0; i < qlen; i++)
851: xwords[i] = xwords[i+ylen];
852: }
853: }
854:
855: if (ywords[rlen-1] < 0)
856: {
857: ywords[rlen] = 0;
858: rlen++;
859: }
860:
861:
862:
863: boolean add_one = false;
864: if (rlen > 1 || ywords[0] != 0)
865: {
866: switch (rounding_mode)
867: {
868: case TRUNCATE:
869: break;
870: case CEILING:
871: case FLOOR:
872: if (qNegative == (rounding_mode == FLOOR))
873: add_one = true;
874: break;
875: case ROUND:
876:
877: BigInteger tmp = remainder == null ? new BigInteger() : remainder;
878: tmp.set(ywords, rlen);
879: tmp = shift(tmp, 1);
880: if (yNegative)
881: tmp.setNegative();
882: int cmp = compareTo(tmp, y);
883:
884: if (yNegative)
885: cmp = -cmp;
886: add_one = (cmp == 1) || (cmp == 0 && (xwords[0]&1) != 0);
887: }
888: }
889: if (quotient != null)
890: {
891: quotient.set(xwords, qlen);
892: if (qNegative)
893: {
894: if (add_one)
895: quotient.setInvert();
896: else
897: quotient.setNegative();
898: }
899: else if (add_one)
900: quotient.setAdd(1);
901: }
902: if (remainder != null)
903: {
904:
905: remainder.set(ywords, rlen);
906: if (add_one)
907: {
908:
909:
910: BigInteger tmp;
911: if (y.words == null)
912: {
913: tmp = remainder;
914: tmp.set(yNegative ? ywords[0] + y.ival : ywords[0] - y.ival);
915: }
916: else
917: tmp = BigInteger.add(remainder, y, yNegative ? 1 : -1);
918:
919:
920:
921:
922: if (xNegative)
923: remainder.setNegative(tmp);
924: else
925: remainder.set(tmp);
926: }
927: else
928: {
929:
930:
931: if (xNegative)
932: remainder.setNegative();
933: }
934: }
935: }
936:
937: public BigInteger divide(BigInteger val)
938: {
939: if (val.isZero())
940: throw new ArithmeticException("divisor is zero");
941:
942: BigInteger quot = new BigInteger();
943: divide(this, val, quot, null, TRUNCATE);
944: return quot.canonicalize();
945: }
946:
947: public BigInteger remainder(BigInteger val)
948: {
949: if (val.isZero())
950: throw new ArithmeticException("divisor is zero");
951:
952: BigInteger rem = new BigInteger();
953: divide(this, val, null, rem, TRUNCATE);
954: return rem.canonicalize();
955: }
956:
957: public BigInteger[] divideAndRemainder(BigInteger val)
958: {
959: if (val.isZero())
960: throw new ArithmeticException("divisor is zero");
961:
962: BigInteger[] result = new BigInteger[2];
963: result[0] = new BigInteger();
964: result[1] = new BigInteger();
965: divide(this, val, result[0], result[1], TRUNCATE);
966: result[0].canonicalize();
967: result[1].canonicalize();
968: return result;
969: }
970:
971: public BigInteger mod(BigInteger m)
972: {
973: if (m.isNegative() || m.isZero())
974: throw new ArithmeticException("non-positive modulus");
975:
976: BigInteger rem = new BigInteger();
977: divide(this, m, null, rem, FLOOR);
978: return rem.canonicalize();
979: }
980:
981:
984: public BigInteger pow(int exponent)
985: {
986: if (exponent <= 0)
987: {
988: if (exponent == 0)
989: return ONE;
990: throw new ArithmeticException("negative exponent");
991: }
992: if (isZero())
993: return this;
994: int plen = words == null ? 1 : ival;
995: int blen = ((bitLength() * exponent) >> 5) + 2 * plen;
996: boolean negative = isNegative() && (exponent & 1) != 0;
997: int[] pow2 = new int [blen];
998: int[] rwords = new int [blen];
999: int[] work = new int [blen];
1000: getAbsolute(pow2);
1001: int rlen = 1;
1002: rwords[0] = 1;
1003: for (;;)
1004: {
1005:
1006:
1007: if ((exponent & 1) != 0)
1008: {
1009: MPN.mul(work, pow2, plen, rwords, rlen);
1010: int[] temp = work; work = rwords; rwords = temp;
1011: rlen += plen;
1012: while (rwords[rlen - 1] == 0) rlen--;
1013: }
1014: exponent >>= 1;
1015: if (exponent == 0)
1016: break;
1017:
1018: MPN.mul(work, pow2, plen, pow2, plen);
1019: int[] temp = work; work = pow2; pow2 = temp;
1020: plen *= 2;
1021: while (pow2[plen - 1] == 0) plen--;
1022: }
1023: if (rwords[rlen - 1] < 0)
1024: rlen++;
1025: if (negative)
1026: negate(rwords, rwords, rlen);
1027: return BigInteger.make(rwords, rlen);
1028: }
1029:
1030: private static int[] euclidInv(int a, int b, int prevDiv)
1031: {
1032: if (b == 0)
1033: throw new ArithmeticException("not invertible");
1034:
1035: if (b == 1)
1036:
1037:
1038: return new int[] { -prevDiv, 1 };
1039:
1040: int[] xy = euclidInv(b, a % b, a / b);
1041: a = xy[0];
1042: xy[0] = a * -prevDiv + xy[1];
1043: xy[1] = a;
1044: return xy;
1045: }
1046:
1047: private static void euclidInv(BigInteger a, BigInteger b,
1048: BigInteger prevDiv, BigInteger[] xy)
1049: {
1050: if (b.isZero())
1051: throw new ArithmeticException("not invertible");
1052:
1053: if (b.isOne())
1054: {
1055:
1056:
1057: xy[0] = neg(prevDiv);
1058: xy[1] = ONE;
1059: return;
1060: }
1061:
1062:
1063:
1064:
1065: if (a.words == null)
1066: {
1067: int[] xyInt = euclidInv(b.ival, a.ival % b.ival, a.ival / b.ival);
1068: xy[0] = new BigInteger(xyInt[0]);
1069: xy[1] = new BigInteger(xyInt[1]);
1070: }
1071: else
1072: {
1073: BigInteger rem = new BigInteger();
1074: BigInteger quot = new BigInteger();
1075: divide(a, b, quot, rem, FLOOR);
1076:
1077: rem.canonicalize();
1078: quot.canonicalize();
1079: euclidInv(b, rem, quot, xy);
1080: }
1081:
1082: BigInteger t = xy[0];
1083: xy[0] = add(xy[1], times(t, prevDiv), -1);
1084: xy[1] = t;
1085: }
1086:
1087: public BigInteger modInverse(BigInteger y)
1088: {
1089: if (y.isNegative() || y.isZero())
1090: throw new ArithmeticException("non-positive modulo");
1091:
1092:
1093: if (y.isOne())
1094: return ZERO;
1095: if (isOne())
1096: return ONE;
1097:
1098:
1099:
1100:
1101:
1102: BigInteger result = new BigInteger();
1103: boolean swapped = false;
1104:
1105: if (y.words == null)
1106: {
1107:
1108:
1109:
1110:
1111:
1112:
1113: int xval = (words != null || isNegative()) ? mod(y).ival : ival;
1114: int yval = y.ival;
1115:
1116:
1117: if (yval > xval)
1118: {
1119: int tmp = xval; xval = yval; yval = tmp;
1120: swapped = true;
1121: }
1122:
1123:
1124:
1125: result.ival =
1126: euclidInv(yval, xval % yval, xval / yval)[swapped ? 0 : 1];
1127:
1128:
1129:
1130: if (result.ival < 0)
1131: result.ival += y.ival;
1132: }
1133: else
1134: {
1135:
1136: BigInteger x = isNegative() ? this.mod(y) : this;
1137:
1138:
1139: if (x.compareTo(y) < 0)
1140: {
1141: result = x; x = y; y = result;
1142: swapped = true;
1143: }
1144:
1145:
1146: BigInteger rem = new BigInteger();
1147: BigInteger quot = new BigInteger();
1148: divide(x, y, quot, rem, FLOOR);
1149:
1150: rem.canonicalize();
1151: quot.canonicalize();
1152: BigInteger[] xy = new BigInteger[2];
1153: euclidInv(y, rem, quot, xy);
1154: result = swapped ? xy[0] : xy[1];
1155:
1156:
1157:
1158: if (result.isNegative())
1159: result = add(result, swapped ? x : y, 1);
1160: }
1161:
1162: return result;
1163: }
1164:
1165: public BigInteger modPow(BigInteger exponent, BigInteger m)
1166: {
1167: if (m.isNegative() || m.isZero())
1168: throw new ArithmeticException("non-positive modulo");
1169:
1170: if (exponent.isNegative())
1171: return modInverse(m).modPow(exponent.negate(), m);
1172: if (exponent.isOne())
1173: return mod(m);
1174:
1175:
1176:
1177:
1178:
1179:
1180:
1181:
1182: BigInteger s = ONE;
1183: BigInteger t = this;
1184: BigInteger u = exponent;
1185:
1186: while (!u.isZero())
1187: {
1188: if (u.and(ONE).isOne())
1189: s = times(s, t).mod(m);
1190: u = u.shiftRight(1);
1191: t = times(t, t).mod(m);
1192: }
1193:
1194: return s;
1195: }
1196:
1197:
1198: private static int gcd(int a, int b)
1199: {
1200:
1201: int tmp;
1202: if (b > a)
1203: {
1204: tmp = a; a = b; b = tmp;
1205: }
1206: for(;;)
1207: {
1208: if (b == 0)
1209: return a;
1210: if (b == 1)
1211: return b;
1212: tmp = b;
1213: b = a % b;
1214: a = tmp;
1215: }
1216: }
1217:
1218: public BigInteger gcd(BigInteger y)
1219: {
1220: int xval = ival;
1221: int yval = y.ival;
1222: if (words == null)
1223: {
1224: if (xval == 0)
1225: return abs(y);
1226: if (y.words == null
1227: && xval != Integer.MIN_VALUE && yval != Integer.MIN_VALUE)
1228: {
1229: if (xval < 0)
1230: xval = -xval;
1231: if (yval < 0)
1232: yval = -yval;
1233: return valueOf(gcd(xval, yval));
1234: }
1235: xval = 1;
1236: }
1237: if (y.words == null)
1238: {
1239: if (yval == 0)
1240: return abs(this);
1241: yval = 1;
1242: }
1243: int len = (xval > yval ? xval : yval) + 1;
1244: int[] xwords = new int[len];
1245: int[] ywords = new int[len];
1246: getAbsolute(xwords);
1247: y.getAbsolute(ywords);
1248: len = MPN.gcd(xwords, ywords, len);
1249: BigInteger result = new BigInteger(0);
1250: result.ival = len;
1251: result.words = xwords;
1252: return result.canonicalize();
1253: }
1254:
1255:
1268: public boolean isProbablePrime(int certainty)
1269: {
1270: if (certainty < 1)
1271: return true;
1272:
1273:
1283:
1284:
1285: BigInteger rem = new BigInteger();
1286: int i;
1287: for (i = 0; i < primes.length; i++)
1288: {
1289: if (words == null && ival == primes[i])
1290: return true;
1291:
1292: divide(this, smallFixNums[primes[i] - minFixNum], null, rem, TRUNCATE);
1293: if (rem.canonicalize().isZero())
1294: return false;
1295: }
1296:
1297:
1298:
1299:
1300:
1301: BigInteger pMinus1 = add(this, -1);
1302: int b = pMinus1.getLowestSetBit();
1303:
1304:
1305: BigInteger m = pMinus1.divide(valueOf(2L << b - 1));
1306:
1307:
1308:
1309:
1310:
1311:
1312: int bits = this.bitLength();
1313: for (i = 0; i < k.length; i++)
1314: if (bits <= k[i])
1315: break;
1316: int trials = t[i];
1317: if (certainty > 80)
1318: trials *= 2;
1319: BigInteger z;
1320: for (int t = 0; t < trials; t++)
1321: {
1322:
1323:
1324:
1325:
1326: z = smallFixNums[primes[t] - minFixNum].modPow(m, this);
1327: if (z.isOne() || z.equals(pMinus1))
1328: continue;
1329:
1330: for (i = 0; i < b; )
1331: {
1332: if (z.isOne())
1333: return false;
1334: i++;
1335: if (z.equals(pMinus1))
1336: break;
1337:
1338: z = z.modPow(valueOf(2), this);
1339: }
1340:
1341: if (i == b && !z.equals(pMinus1))
1342: return false;
1343: }
1344: return true;
1345: }
1346:
1347: private void setInvert()
1348: {
1349: if (words == null)
1350: ival = ~ival;
1351: else
1352: {
1353: for (int i = ival; --i >= 0; )
1354: words[i] = ~words[i];
1355: }
1356: }
1357:
1358: private void setShiftLeft(BigInteger x, int count)
1359: {
1360: int[] xwords;
1361: int xlen;
1362: if (x.words == null)
1363: {
1364: if (count < 32)
1365: {
1366: set((long) x.ival << count);
1367: return;
1368: }
1369: xwords = new int[1];
1370: xwords[0] = x.ival;
1371: xlen = 1;
1372: }
1373: else
1374: {
1375: xwords = x.words;
1376: xlen = x.ival;
1377: }
1378: int word_count = count >> 5;
1379: count &= 31;
1380: int new_len = xlen + word_count;
1381: if (count == 0)
1382: {
1383: realloc(new_len);
1384: for (int i = xlen; --i >= 0; )
1385: words[i+word_count] = xwords[i];
1386: }
1387: else
1388: {
1389: new_len++;
1390: realloc(new_len);
1391: int shift_out = MPN.lshift(words, word_count, xwords, xlen, count);
1392: count = 32 - count;
1393: words[new_len-1] = (shift_out << count) >> count;
1394: }
1395: ival = new_len;
1396: for (int i = word_count; --i >= 0; )
1397: words[i] = 0;
1398: }
1399:
1400: private void setShiftRight(BigInteger x, int count)
1401: {
1402: if (x.words == null)
1403: set(count < 32 ? x.ival >> count : x.ival < 0 ? -1 : 0);
1404: else if (count == 0)
1405: set(x);
1406: else
1407: {
1408: boolean neg = x.isNegative();
1409: int word_count = count >> 5;
1410: count &= 31;
1411: int d_len = x.ival - word_count;
1412: if (d_len <= 0)
1413: set(neg ? -1 : 0);
1414: else
1415: {
1416: if (words == null || words.length < d_len)
1417: realloc(d_len);
1418: MPN.rshift0 (words, x.words, word_count, d_len, count);
1419: ival = d_len;
1420: if (neg)
1421: words[d_len-1] |= -2 << (31 - count);
1422: }
1423: }
1424: }
1425:
1426: private void setShift(BigInteger x, int count)
1427: {
1428: if (count > 0)
1429: setShiftLeft(x, count);
1430: else
1431: setShiftRight(x, -count);
1432: }
1433:
1434: private static BigInteger shift(BigInteger x, int count)
1435: {
1436: if (x.words == null)
1437: {
1438: if (count <= 0)
1439: return valueOf(count > -32 ? x.ival >> (-count) : x.ival < 0 ? -1 : 0);
1440: if (count < 32)
1441: return valueOf((long) x.ival << count);
1442: }
1443: if (count == 0)
1444: return x;
1445: BigInteger result = new BigInteger(0);
1446: result.setShift(x, count);
1447: return result.canonicalize();
1448: }
1449:
1450: public BigInteger shiftLeft(int n)
1451: {
1452: return shift(this, n);
1453: }
1454:
1455: public BigInteger shiftRight(int n)
1456: {
1457: return shift(this, -n);
1458: }
1459:
1460: private void format(int radix, StringBuffer buffer)
1461: {
1462: if (words == null)
1463: buffer.append(Integer.toString(ival, radix));
1464: else if (ival <= 2)
1465: buffer.append(Long.toString(longValue(), radix));
1466: else
1467: {
1468: boolean neg = isNegative();
1469: int[] work;
1470: if (neg || radix != 16)
1471: {
1472: work = new int[ival];
1473: getAbsolute(work);
1474: }
1475: else
1476: work = words;
1477: int len = ival;
1478:
1479: if (radix == 16)
1480: {
1481: if (neg)
1482: buffer.append('-');
1483: int buf_start = buffer.length();
1484: for (int i = len; --i >= 0; )
1485: {
1486: int word = work[i];
1487: for (int j = 8; --j >= 0; )
1488: {
1489: int hex_digit = (word >> (4 * j)) & 0xF;
1490:
1491: if (hex_digit > 0 || buffer.length() > buf_start)
1492: buffer.append(Character.forDigit(hex_digit, 16));
1493: }
1494: }
1495: }
1496: else
1497: {
1498: int i = buffer.length();
1499: for (;;)
1500: {
1501: int digit = MPN.divmod_1(work, work, len, radix);
1502: buffer.append(Character.forDigit(digit, radix));
1503: while (len > 0 && work[len-1] == 0) len--;
1504: if (len == 0)
1505: break;
1506: }
1507: if (neg)
1508: buffer.append('-');
1509:
1510: int j = buffer.length() - 1;
1511: while (i < j)
1512: {
1513: char tmp = buffer.charAt(i);
1514: buffer.setCharAt(i, buffer.charAt(j));
1515: buffer.setCharAt(j, tmp);
1516: i++; j--;
1517: }
1518: }
1519: }
1520: }
1521:
1522: public String toString()
1523: {
1524: return toString(10);
1525: }
1526:
1527: public String toString(int radix)
1528: {
1529: if (words == null)
1530: return Integer.toString(ival, radix);
1531: if (ival <= 2)
1532: return Long.toString(longValue(), radix);
1533: int buf_size = ival * (MPN.chars_per_word(radix) + 1);
1534: StringBuffer buffer = new StringBuffer(buf_size);
1535: format(radix, buffer);
1536: return buffer.toString();
1537: }
1538:
1539: public int intValue()
1540: {
1541: if (words == null)
1542: return ival;
1543: return words[0];
1544: }
1545:
1546: public long longValue()
1547: {
1548: if (words == null)
1549: return ival;
1550: if (ival == 1)
1551: return words[0];
1552: return ((long)words[1] << 32) + ((long)words[0] & 0xffffffffL);
1553: }
1554:
1555: public int hashCode()
1556: {
1557:
1558: return words == null ? ival : (words[0] + words[ival - 1]);
1559: }
1560:
1561:
1562: private static boolean equals(BigInteger x, BigInteger y)
1563: {
1564: if (x.words == null && y.words == null)
1565: return x.ival == y.ival;
1566: if (x.words == null || y.words == null || x.ival != y.ival)
1567: return false;
1568: for (int i = x.ival; --i >= 0; )
1569: {
1570: if (x.words[i] != y.words[i])
1571: return false;
1572: }
1573: return true;
1574: }
1575:
1576:
1577: public boolean equals(Object obj)
1578: {
1579: if (! (obj instanceof BigInteger))
1580: return false;
1581: return equals(this, (BigInteger) obj);
1582: }
1583:
1584: private static BigInteger valueOf(String s, int radix)
1585: throws NumberFormatException
1586: {
1587: int len = s.length();
1588:
1589:
1590: if (len <= 15 && radix <= 16)
1591: return valueOf(Long.parseLong(s, radix));
1592:
1593: int byte_len = 0;
1594: byte[] bytes = new byte[len];
1595: boolean negative = false;
1596: for (int i = 0; i < len; i++)
1597: {
1598: char ch = s.charAt(i);
1599: if (ch == '-')
1600: negative = true;
1601: else if (ch == '_' || (byte_len == 0 && (ch == ' ' || ch == '\t')))
1602: continue;
1603: else
1604: {
1605: int digit = Character.digit(ch, radix);
1606: if (digit < 0)
1607: break;
1608: bytes[byte_len++] = (byte) digit;
1609: }
1610: }
1611: return valueOf(bytes, byte_len, negative, radix);
1612: }
1613:
1614: private static BigInteger valueOf(byte[] digits, int byte_len,
1615: boolean negative, int radix)
1616: {
1617: int chars_per_word = MPN.chars_per_word(radix);
1618: int[] words = new int[byte_len / chars_per_word + 1];
1619: int size = MPN.set_str(words, digits, byte_len, radix);
1620: if (size == 0)
1621: return ZERO;
1622: if (words[size-1] < 0)
1623: words[size++] = 0;
1624: if (negative)
1625: negate(words, words, size);
1626: return make(words, size);
1627: }
1628:
1629: public double doubleValue()
1630: {
1631: if (words == null)
1632: return (double) ival;
1633: if (ival <= 2)
1634: return (double) longValue();
1635: if (isNegative())
1636: return neg(this).roundToDouble(0, true, false);
1637: return roundToDouble(0, false, false);
1638: }
1639:
1640: public float floatValue()
1641: {
1642: return (float) doubleValue();
1643: }
1644:
1645:
1647: private boolean checkBits(int n)
1648: {
1649: if (n <= 0)
1650: return false;
1651: if (words == null)
1652: return n > 31 || ((ival & ((1 << n) - 1)) != 0);
1653: int i;
1654: for (i = 0; i < (n >> 5) ; i++)
1655: if (words[i] != 0)
1656: return true;
1657: return (n & 31) != 0 && (words[i] & ((1 << (n & 31)) - 1)) != 0;
1658: }
1659:
1660:
1668: private double roundToDouble(int exp, boolean neg, boolean remainder)
1669: {
1670:
1671: int il = bitLength();
1672:
1673:
1674:
1675: exp += il - 1;
1676:
1677:
1678:
1679:
1680:
1681: if (exp < -1075)
1682: return neg ? -0.0 : 0.0;
1683:
1684:
1685: if (exp > 1023)
1686: return neg ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
1687:
1688:
1689:
1690: int ml = (exp >= -1022 ? 53 : 53 + exp + 1022);
1691:
1692:
1693: long m;
1694: int excess_bits = il - (ml + 1);
1695: if (excess_bits > 0)
1696: m = ((words == null) ? ival >> excess_bits
1697: : MPN.rshift_long(words, ival, excess_bits));
1698: else
1699: m = longValue() << (- excess_bits);
1700:
1701:
1702:
1703: if (exp == 1023 && ((m >> 1) == (1L << 53) - 1))
1704: {
1705: if (remainder || checkBits(il - ml))
1706: return neg ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
1707: else
1708: return neg ? - Double.MAX_VALUE : Double.MAX_VALUE;
1709: }
1710:
1711:
1712:
1713: if ((m & 1) == 1
1714: && ((m & 2) == 2 || remainder || checkBits(excess_bits)))
1715: {
1716: m += 2;
1717:
1718: if ((m & (1L << 54)) != 0)
1719: {
1720: exp++;
1721:
1722: m >>= 1;
1723: }
1724:
1725:
1726: else if (ml == 52 && (m & (1L << 53)) != 0)
1727: exp++;
1728: }
1729:
1730:
1731: m >>= 1;
1732:
1733: long bits_sign = neg ? (1L << 63) : 0;
1734: exp += 1023;
1735: long bits_exp = (exp <= 0) ? 0 : ((long)exp) << 52;
1736: long bits_mant = m & ~(1L << 52);
1737: return Double.longBitsToDouble(bits_sign | bits_exp | bits_mant);
1738: }
1739:
1740:
1744: private void getAbsolute(int[] words)
1745: {
1746: int len;
1747: if (this.words == null)
1748: {
1749: len = 1;
1750: words[0] = this.ival;
1751: }
1752: else
1753: {
1754: len = this.ival;
1755: for (int i = len; --i >= 0; )
1756: words[i] = this.words[i];
1757: }
1758: if (words[len - 1] < 0)
1759: negate(words, words, len);
1760: for (int i = words.length; --i > len; )
1761: words[i] = 0;
1762: }
1763:
1764:
1767: private static boolean negate(int[] dest, int[] src, int len)
1768: {
1769: long carry = 1;
1770: boolean negative = src[len-1] < 0;
1771: for (int i = 0; i < len; i++)
1772: {
1773: carry += ((long) (~src[i]) & 0xffffffffL);
1774: dest[i] = (int) carry;
1775: carry >>= 32;
1776: }
1777: return (negative && dest[len-1] < 0);
1778: }
1779:
1780:
1782: private void setNegative(BigInteger x)
1783: {
1784: int len = x.ival;
1785: if (x.words == null)
1786: {
1787: if (len == Integer.MIN_VALUE)
1788: set(- (long) len);
1789: else
1790: set(-len);
1791: return;
1792: }
1793: realloc(len + 1);
1794: if (negate(words, x.words, len))
1795: words[len++] = 0;
1796: ival = len;
1797: }
1798:
1799:
1800: private void setNegative()
1801: {
1802: setNegative(this);
1803: }
1804:
1805: private static BigInteger abs(BigInteger x)
1806: {
1807: return x.isNegative() ? neg(x) : x;
1808: }
1809:
1810: public BigInteger abs()
1811: {
1812: return abs(this);
1813: }
1814:
1815: private static BigInteger neg(BigInteger x)
1816: {
1817: if (x.words == null && x.ival != Integer.MIN_VALUE)
1818: return valueOf(- x.ival);
1819: BigInteger result = new BigInteger(0);
1820: result.setNegative(x);
1821: return result.canonicalize();
1822: }
1823:
1824: public BigInteger negate()
1825: {
1826: return neg(this);
1827: }
1828:
1829:
1832: public int bitLength()
1833: {
1834: if (words == null)
1835: return MPN.intLength(ival);
1836: return MPN.intLength(words, ival);
1837: }
1838:
1839: public byte[] toByteArray()
1840: {
1841:
1842:
1843:
1844: byte[] bytes = new byte[(bitLength() + 1 + 7) / 8];
1845: int nbytes = bytes.length;
1846:
1847: int wptr = 0;
1848: int word;
1849:
1850:
1851:
1852: while (nbytes > 4)
1853: {
1854: word = words[wptr++];
1855: for (int i = 4; i > 0; --i, word >>= 8)
1856: bytes[--nbytes] = (byte) word;
1857: }
1858:
1859:
1860: word = (words == null) ? ival : words[wptr];
1861: for ( ; nbytes > 0; word >>= 8)
1862: bytes[--nbytes] = (byte) word;
1863:
1864: return bytes;
1865: }
1866:
1867:
1870: private static int swappedOp(int op)
1871: {
1872: return
1873: "\000\001\004\005\002\003\006\007\010\011\014\015\012\013\016\017"
1874: .charAt(op);
1875: }
1876:
1877:
1878: private static BigInteger bitOp(int op, BigInteger x, BigInteger y)
1879: {
1880: switch (op)
1881: {
1882: case 0: return ZERO;
1883: case 1: return x.and(y);
1884: case 3: return x;
1885: case 5: return y;
1886: case 15: return valueOf(-1);
1887: }
1888: BigInteger result = new BigInteger();
1889: setBitOp(result, op, x, y);
1890: return result.canonicalize();
1891: }
1892:
1893:
1894: private static void setBitOp(BigInteger result, int op,
1895: BigInteger x, BigInteger y)
1896: {
1897: if (y.words == null) ;
1898: else if (x.words == null || x.ival < y.ival)
1899: {
1900: BigInteger temp = x; x = y; y = temp;
1901: op = swappedOp(op);
1902: }
1903: int xi;
1904: int yi;
1905: int xlen, ylen;
1906: if (y.words == null)
1907: {
1908: yi = y.ival;
1909: ylen = 1;
1910: }
1911: else
1912: {
1913: yi = y.words[0];
1914: ylen = y.ival;
1915: }
1916: if (x.words == null)
1917: {
1918: xi = x.ival;
1919: xlen = 1;
1920: }
1921: else
1922: {
1923: xi = x.words[0];
1924: xlen = x.ival;
1925: }
1926: if (xlen > 1)
1927: result.realloc(xlen);
1928: int[] w = result.words;
1929: int i = 0;
1930:
1931:
1932:
1933:
1934: int finish = 0;
1935: int ni;
1936: switch (op)
1937: {
1938: case 0:
1939: ni = 0;
1940: break;
1941: case 1:
1942: for (;;)
1943: {
1944: ni = xi & yi;
1945: if (i+1 >= ylen) break;
1946: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
1947: }
1948: if (yi < 0) finish = 1;
1949: break;
1950: case 2:
1951: for (;;)
1952: {
1953: ni = xi & ~yi;
1954: if (i+1 >= ylen) break;
1955: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
1956: }
1957: if (yi >= 0) finish = 1;
1958: break;
1959: case 3:
1960: ni = xi;
1961: finish = 1;
1962: break;
1963: case 4:
1964: for (;;)
1965: {
1966: ni = ~xi & yi;
1967: if (i+1 >= ylen) break;
1968: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
1969: }
1970: if (yi < 0) finish = 2;
1971: break;
1972: case 5:
1973: for (;;)
1974: {
1975: ni = yi;
1976: if (i+1 >= ylen) break;
1977: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
1978: }
1979: break;
1980: case 6:
1981: for (;;)
1982: {
1983: ni = xi ^ yi;
1984: if (i+1 >= ylen) break;
1985: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
1986: }
1987: finish = yi < 0 ? 2 : 1;
1988: break;
1989: case 7:
1990: for (;;)
1991: {
1992: ni = xi | yi;
1993: if (i+1 >= ylen) break;
1994: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
1995: }
1996: if (yi >= 0) finish = 1;
1997: break;
1998: case 8:
1999: for (;;)
2000: {
2001: ni = ~(xi | yi);
2002: if (i+1 >= ylen) break;
2003: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2004: }
2005: if (yi >= 0) finish = 2;
2006: break;
2007: case 9:
2008: for (;;)
2009: {
2010: ni = ~(xi ^ yi);
2011: if (i+1 >= ylen) break;
2012: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2013: }
2014: finish = yi >= 0 ? 2 : 1;
2015: break;
2016: case 10:
2017: for (;;)
2018: {
2019: ni = ~yi;
2020: if (i+1 >= ylen) break;
2021: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2022: }
2023: break;
2024: case 11:
2025: for (;;)
2026: {
2027: ni = xi | ~yi;
2028: if (i+1 >= ylen) break;
2029: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2030: }
2031: if (yi < 0) finish = 1;
2032: break;
2033: case 12:
2034: ni = ~xi;
2035: finish = 2;
2036: break;
2037: case 13:
2038: for (;;)
2039: {
2040: ni = ~xi | yi;
2041: if (i+1 >= ylen) break;
2042: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2043: }
2044: if (yi >= 0) finish = 2;
2045: break;
2046: case 14:
2047: for (;;)
2048: {
2049: ni = ~(xi & yi);
2050: if (i+1 >= ylen) break;
2051: w[i++] = ni; xi = x.words[i]; yi = y.words[i];
2052: }
2053: if (yi < 0) finish = 2;
2054: break;
2055: default:
2056: case 15:
2057: ni = -1;
2058: break;
2059: }
2060:
2061:
2062: if (i+1 == xlen)
2063: finish = 0;
2064: switch (finish)
2065: {
2066: case 0:
2067: if (i == 0 && w == null)
2068: {
2069: result.ival = ni;
2070: return;
2071: }
2072: w[i++] = ni;
2073: break;
2074: case 1: w[i] = ni; while (++i < xlen) w[i] = x.words[i]; break;
2075: case 2: w[i] = ni; while (++i < xlen) w[i] = ~x.words[i]; break;
2076: }
2077: result.ival = i;
2078: }
2079:
2080:
2081: private static BigInteger and(BigInteger x, int y)
2082: {
2083: if (x.words == null)
2084: return valueOf(x.ival & y);
2085: if (y >= 0)
2086: return valueOf(x.words[0] & y);
2087: int len = x.ival;
2088: int[] words = new int[len];
2089: words[0] = x.words[0] & y;
2090: while (--len > 0)
2091: words[len] = x.words[len];
2092: return make(words, x.ival);
2093: }
2094:
2095:
2096: public BigInteger and(BigInteger y)
2097: {
2098: if (y.words == null)
2099: return and(this, y.ival);
2100: else if (words == null)
2101: return and(y, ival);
2102:
2103: BigInteger x = this;
2104: if (ival < y.ival)
2105: {
2106: BigInteger temp = this; x = y; y = temp;
2107: }
2108: int i;
2109: int len = y.isNegative() ? x.ival : y.ival;
2110: int[] words = new int[len];
2111: for (i = 0; i < y.ival; i++)
2112: words[i] = x.words[i] & y.words[i];
2113: for ( ; i < len; i++)
2114: words[i] = x.words[i];
2115: return make(words, len);
2116: }
2117:
2118:
2119: public BigInteger or(BigInteger y)
2120: {
2121: return bitOp(7, this, y);
2122: }
2123:
2124:
2125: public BigInteger xor(BigInteger y)
2126: {
2127: return bitOp(6, this, y);
2128: }
2129:
2130:
2131: public BigInteger not()
2132: {
2133: return bitOp(12, this, ZERO);
2134: }
2135:
2136: public BigInteger andNot(BigInteger val)
2137: {
2138: return and(val.not());
2139: }
2140:
2141: public BigInteger clearBit(int n)
2142: {
2143: if (n < 0)
2144: throw new ArithmeticException();
2145:
2146: return and(ONE.shiftLeft(n).not());
2147: }
2148:
2149: public BigInteger setBit(int n)
2150: {
2151: if (n < 0)
2152: throw new ArithmeticException();
2153:
2154: return or(ONE.shiftLeft(n));
2155: }
2156:
2157: public boolean testBit(int n)
2158: {
2159: if (n < 0)
2160: throw new ArithmeticException();
2161:
2162: return !and(ONE.shiftLeft(n)).isZero();
2163: }
2164:
2165: public BigInteger flipBit(int n)
2166: {
2167: if (n < 0)
2168: throw new ArithmeticException();
2169:
2170: return xor(ONE.shiftLeft(n));
2171: }
2172:
2173: public int getLowestSetBit()
2174: {
2175: if (isZero())
2176: return -1;
2177:
2178: if (words == null)
2179: return MPN.findLowestBit(ival);
2180: else
2181: return MPN.findLowestBit(words);
2182: }
2183:
2184:
2185: private static final byte[] bit4_count = { 0, 1, 1, 2, 1, 2, 2, 3,
2186: 1, 2, 2, 3, 2, 3, 3, 4};
2187:
2188: private static int bitCount(int i)
2189: {
2190: int count = 0;
2191: while (i != 0)
2192: {
2193: count += bit4_count[i & 15];
2194: i >>>= 4;
2195: }
2196: return count;
2197: }
2198:
2199: private static int bitCount(int[] x, int len)
2200: {
2201: int count = 0;
2202: while (--len >= 0)
2203: count += bitCount(x[len]);
2204: return count;
2205: }
2206:
2207:
2209: public int bitCount()
2210: {
2211: int i, x_len;
2212: int[] x_words = words;
2213: if (x_words == null)
2214: {
2215: x_len = 1;
2216: i = bitCount(ival);
2217: }
2218: else
2219: {
2220: x_len = ival;
2221: i = bitCount(x_words, x_len);
2222: }
2223: return isNegative() ? x_len * 32 - i : i;
2224: }
2225:
2226: private void readObject(ObjectInputStream s)
2227: throws IOException, ClassNotFoundException
2228: {
2229: s.defaultReadObject();
2230: if (magnitude.length == 0 || signum == 0)
2231: {
2232: this.ival = 0;
2233: this.words = null;
2234: }
2235: else
2236: {
2237: words = byteArrayToIntArray(magnitude, signum < 0 ? -1 : 0);
2238: BigInteger result = make(words, words.length);
2239: this.ival = result.ival;
2240: this.words = result.words;
2241: }
2242: }
2243:
2244: private void writeObject(ObjectOutputStream s)
2245: throws IOException, ClassNotFoundException
2246: {
2247: signum = signum();
2248: magnitude = signum == 0 ? new byte[0] : toByteArray();
2249: s.defaultWriteObject();
2250: }
2251: }