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