001 /*
002 * $Id: BigInteger.java 3354 2010-10-23 15:51:37Z kredel $
003 */
004
005 package edu.jas.arith;
006
007 import java.util.Random;
008 import java.io.Reader;
009 import java.util.List;
010 import java.util.ArrayList;
011 import java.util.Iterator;
012
013 import edu.jas.kern.StringUtil;
014 import edu.jas.structure.GcdRingElem;
015 import edu.jas.structure.RingFactory;
016
017
018
019 /**
020 * BigInteger class to make java.math.BigInteger available with RingElem
021 * interface and with the familiar SAC static method names.
022 * Objects of this class are immutable.
023 * @author Heinz Kredel
024 * @see java.math.BigInteger
025 */
026
027 public final class BigInteger implements GcdRingElem<BigInteger>,
028 RingFactory<BigInteger>, Iterable<BigInteger> {
029
030 /** The data structure.
031 */
032 protected final java.math.BigInteger val;
033
034
035 private final static Random random = new Random();
036
037
038 /** The constant 0.
039 */
040 public final static BigInteger ZERO
041 = new BigInteger( java.math.BigInteger.ZERO );
042
043
044 /** The constant 1.
045 */
046 public final static BigInteger ONE
047 = new BigInteger( java.math.BigInteger.ONE );
048
049
050 /**
051 * Constructor for BigInteger from math.BigInteger.
052 * @param a java.math.BigInteger.
053 */
054 public BigInteger(java.math.BigInteger a) {
055 val = a;
056 }
057
058
059 /**
060 * Constructor for BigInteger from long.
061 * @param a long.
062 */
063 public BigInteger(long a) {
064 val = new java.math.BigInteger( String.valueOf(a) );
065 }
066
067
068 /**
069 * Constructor for BigInteger from String.
070 * @param s String.
071 */
072 public BigInteger(String s) {
073 val = new java.math.BigInteger( s.trim() );
074 }
075
076
077 /**
078 * Constructor for BigInteger without parameters.
079 */
080 public BigInteger() {
081 val = java.math.BigInteger.ZERO;
082 }
083
084
085 /** Get the value.
086 * @return val java.math.BigInteger.
087 */
088 public java.math.BigInteger getVal() {
089 return val;
090 }
091
092
093 /** Get the value as long.
094 * @return val as long.
095 */
096 public long longValue() {
097 return val.longValue();
098 }
099
100
101 /**
102 * Get the corresponding element factory.
103 * @return factory for this Element.
104 * @see edu.jas.structure.Element#factory()
105 */
106 public BigInteger factory() {
107 return this;
108 }
109
110
111 /**
112 * Get a list of the generating elements.
113 * @return list of generators for the algebraic structure.
114 * @see edu.jas.structure.ElemFactory#generators()
115 */
116 public List<BigInteger> generators() {
117 List<BigInteger> g = new ArrayList<BigInteger>(1);
118 g.add( getONE() );
119 return g;
120 }
121
122
123 /**
124 * Is this structure finite or infinite.
125 * @return true if this structure is finite, else false.
126 * @see edu.jas.structure.ElemFactory#isFinite()
127 */
128 public boolean isFinite() {
129 return false;
130 }
131
132
133 /** Clone this.
134 * @see java.lang.Object#clone()
135 */
136 @Override
137 public BigInteger clone() {
138 return new BigInteger( val );
139 }
140
141
142 /** Copy BigInteger element c.
143 * @param c BigInteger.
144 * @return a copy of c.
145 */
146 public BigInteger copy(BigInteger c) {
147 return new BigInteger( c.val );
148 }
149
150
151 /** Get the zero element.
152 * @return 0.
153 */
154 public BigInteger getZERO() {
155 return ZERO;
156 }
157
158
159 /** Get the one element.
160 * @return 1.
161 */
162 public BigInteger getONE() {
163 return ONE;
164 }
165
166
167 /**
168 * Query if this ring is commutative.
169 * @return true.
170 */
171 public boolean isCommutative() {
172 return true;
173 }
174
175
176 /**
177 * Query if this ring is associative.
178 * @return true.
179 */
180 public boolean isAssociative() {
181 return true;
182 }
183
184
185 /**
186 * Query if this ring is a field.
187 * @return false.
188 */
189 public boolean isField() {
190 return false;
191 }
192
193
194 /**
195 * Characteristic of this ring.
196 * @return characteristic of this ring.
197 */
198 public java.math.BigInteger characteristic() {
199 return java.math.BigInteger.ZERO;
200 }
201
202
203 /** Get a BigInteger element from a math.BigInteger.
204 * @param a math.BigInteger.
205 * @return a as BigInteger.
206 */
207 public BigInteger fromInteger(java.math.BigInteger a) {
208 return new BigInteger(a);
209 }
210
211
212 /** Get a BigInteger element from a math.BigInteger.
213 * @param a math.BigInteger.
214 * @return a as BigInteger.
215 */
216 public static BigInteger valueOf(java.math.BigInteger a) {
217 return new BigInteger(a);
218 }
219
220
221 /** Get a BigInteger element from long.
222 * @param a long.
223 * @return a as BigInteger.
224 */
225 public BigInteger fromInteger(long a) {
226 return new BigInteger(a);
227 }
228
229
230 /** Get a BigInteger element from long.
231 * @param a long.
232 * @return a as BigInteger.
233 */
234 public static BigInteger valueOf(long a) {
235 return new BigInteger(a);
236 }
237
238
239 /** Is BigInteger number zero.
240 * @return If this is 0 then true is returned, else false.
241 * @see edu.jas.structure.RingElem#isZERO()
242 */
243 public boolean isZERO() {
244 return val.equals( java.math.BigInteger.ZERO );
245 }
246
247
248 /** Is BigInteger number one.
249 * @see edu.jas.structure.RingElem#isONE()
250 */
251 public boolean isONE() {
252 return val.equals( java.math.BigInteger.ONE );
253 }
254
255
256 /** Is BigInteger number unit.
257 * @see edu.jas.structure.RingElem#isUnit()
258 */
259 public boolean isUnit() {
260 return ( this.isONE() || this.negate().isONE() );
261 }
262
263 /** Get the String representation.
264 * @see java.lang.Object#toString()
265 */
266 @Override
267 public String toString() {
268 return val.toString();
269 }
270
271
272 /** Get a scripting compatible string representation.
273 * @return script compatible representation for this Element.
274 * @see edu.jas.structure.Element#toScript()
275 */
276 //JAVA6only: @Override
277 public String toScript() {
278 // Python case
279 return toString();
280 }
281
282
283 /** Get a scripting compatible string representation of the factory.
284 * @return script compatible representation for this ElemFactory.
285 * @see edu.jas.structure.Element#toScriptFactory()
286 */
287 //JAVA6only: @Override
288 public String toScriptFactory() {
289 // Python case
290 return "ZZ()";
291 }
292
293
294 /** Compare to BigInteger b.
295 * @param b BigInteger.
296 * @return 0 if this == b,
297 1 if this > b,
298 -1 if this < b.
299 */
300 //JAVA6only: @Override
301 public int compareTo(BigInteger b) {
302 return val.compareTo( b.val );
303 }
304
305
306 /** Integer comparison.
307 * @param A BigInteger.
308 * @param B BigInteger.
309 * @return 0 if A == B, 1 if A > B, -1 if A < B.
310 */
311 public static int ICOMP(BigInteger A, BigInteger B) {
312 if ( A == null ) return -B.signum();
313 return A.compareTo(B);
314 }
315
316
317 /** Comparison with any other object.
318 * @see java.lang.Object#equals(java.lang.Object)
319 */
320 @Override
321 public boolean equals(Object b) {
322 if ( ! ( b instanceof BigInteger ) ) {
323 return false;
324 }
325 BigInteger bi = (BigInteger)b;
326 return val.equals( bi.val );
327 }
328
329
330 /** Hash code for this BigInteger.
331 * @see java.lang.Object#hashCode()
332 */
333 @Override
334 public int hashCode() {
335 return val.hashCode();
336 }
337
338
339 /** Absolute value of this.
340 * @see edu.jas.structure.RingElem#abs()
341 */
342 public BigInteger abs() {
343 return new BigInteger( val.abs() );
344 }
345
346
347 /** Absolute value.
348 * @param A BigInteger.
349 * @return abs(A).
350 */
351 public static BigInteger IABS(BigInteger A) {
352 if ( A == null ) return null;
353 return A.abs();
354 }
355
356
357 /* Negative value of this.
358 * @see edu.jas.structure.RingElem#negate()
359 */
360 public BigInteger negate() {
361 return new BigInteger( val.negate() );
362 }
363
364
365 /** Negative value.
366 * @param A BigInteger.
367 * @return -A.
368 */
369 public static BigInteger INEG(BigInteger A) {
370 if ( A == null ) return null;
371 return A.negate();
372 }
373
374
375 /** signum.
376 * @see edu.jas.structure.RingElem#signum()
377 */
378 public int signum() {
379 return val.signum();
380 }
381
382
383 /** Integer signum.
384 * @param A BigInteger.
385 * @return signum(A).
386 */
387 public static int ISIGN(BigInteger A) {
388 if ( A == null ) return 0;
389 return A.signum();
390 }
391
392
393 /** BigInteger subtract.
394 * @param S BigInteger.
395 * @return this-S.
396 */
397 public BigInteger subtract(BigInteger S) {
398 return new BigInteger( val.subtract( S.val ) );
399 }
400
401 /** BigInteger subtract.
402 * @param A BigInteger.
403 * @param B BigInteger.
404 * @return A-B.
405 */
406 public static BigInteger IDIF(BigInteger A, BigInteger B) {
407 if ( A == null ) return B.negate();
408 return A.subtract(B);
409 }
410
411
412 /** BigInteger divide.
413 * @param S BigInteger.
414 * @return this/S.
415 */
416 public BigInteger divide(BigInteger S) {
417 return new BigInteger( val.divide( S.val ) );
418 }
419
420 /** BigInteger divide.
421 * @param A BigInteger.
422 * @param B BigInteger.
423 * @return A/B.
424 */
425 public static BigInteger IQ(BigInteger A, BigInteger B) {
426 if ( A == null ) return null;
427 return A.divide(B);
428 }
429
430
431 /** Integer inverse. R is a non-zero integer.
432 S=1/R if defined else 0.
433 * @see edu.jas.structure.RingElem#inverse()
434 */
435 public BigInteger inverse() {
436 if ( this.isONE() || this.negate().isONE() ) {
437 return this;
438 }
439 return ZERO;
440 }
441
442
443 /** BigInteger remainder.
444 * @param S BigInteger.
445 * @return this - (this/S)*S.
446 */
447 public BigInteger remainder(BigInteger S) {
448 return new BigInteger( val.remainder( S.val ) );
449 }
450
451
452 /** BigInteger remainder.
453 * @param A BigInteger.
454 * @param B BigInteger.
455 * @return A - (A/B)*B.
456 */
457 public static BigInteger IREM(BigInteger A, BigInteger B) {
458 if ( A == null ) return null;
459 return A.remainder(B);
460 }
461
462
463 /** BigInteger compute quotient and remainder.
464 * Throws an exception, if S == 0.
465 * @param S BigInteger.
466 * @return BigInteger[] { q, r } with this = q S + r and 0 ≤ r < |S|.
467 */
468 //@Override
469 public BigInteger[] quotientRemainder(BigInteger S) {
470 BigInteger[] qr = new BigInteger[2];
471 java.math.BigInteger[] C = val.divideAndRemainder( S.val );
472 qr[0] = new BigInteger( C[0] );
473 qr[1] = new BigInteger( C[1] );
474 return qr;
475 }
476
477
478 /** BigInteger compute quotient and remainder.
479 * Throws an exception, if S == 0.
480 * @param S BigInteger.
481 * @return BigInteger[] { q, r } with this = q S + r and 0 ≤ r < |S|.
482 * @deprecated use quotientRemainder()
483 */
484 @Deprecated
485 public BigInteger[] divideAndRemainder(BigInteger S) {
486 return quotientRemainder(S);
487 }
488
489
490 /**
491 * Integer quotient and remainder. A and B are integers, B ne 0. Q is
492 * the quotient, integral part of A/B, and R is the remainder A-B*Q.
493 * Throws an exception, if B == 0.
494 * @param A BigInteger.
495 * @param B BigInteger.
496 * @return BigInteger[] { q, r } with A = q B + r and 0 ≤ r < |B|
497 */
498 public static BigInteger[] IQR(BigInteger A, BigInteger B) {
499 if ( A == null ) return null;
500 return A.quotientRemainder(B);
501 }
502
503
504 /** BigInteger greatest common divisor.
505 * @param S BigInteger.
506 * @return gcd(this,S).
507 */
508 public BigInteger gcd(BigInteger S) {
509 return new BigInteger( val.gcd( S.val ) );
510 }
511
512
513 /**
514 * BigInteger extended greatest common divisor.
515 * @param S BigInteger.
516 * @return [ gcd(this,S), a, b ] with a*this + b*S = gcd(this,S).
517 */
518 public BigInteger[] egcd(BigInteger S) {
519 BigInteger[] ret = new BigInteger[3];
520 ret[0] = null;
521 ret[1] = null;
522 ret[2] = null;
523 if ( S == null || S.isZERO() ) {
524 ret[0] = this;
525 return ret;
526 }
527 if ( this.isZERO() ) {
528 ret[0] = S;
529 return ret;
530 }
531 //System.out.println("this = " + this + ", S = " + S);
532 BigInteger[] qr;
533 BigInteger q = this;
534 BigInteger r = S;
535 BigInteger c1 = ONE;
536 BigInteger d1 = ZERO;
537 BigInteger c2 = ZERO;
538 BigInteger d2 = ONE;
539 BigInteger x1;
540 BigInteger x2;
541 while ( !r.isZERO() ) {
542 qr = q.quotientRemainder(r);
543 q = qr[0];
544 x1 = c1.subtract( q.multiply(d1) );
545 x2 = c2.subtract( q.multiply(d2) );
546 c1 = d1; c2 = d2;
547 d1 = x1; d2 = x2;
548 q = r;
549 r = qr[1];
550 }
551 //System.out.println("q = " + q + "\n c1 = " + c1 + "\n c2 = " + c2);
552 if ( q.signum() < 0 ) {
553 q = q.negate();
554 c1 = c1.negate();
555 c2 = c2.negate();
556 }
557 ret[0] = q;
558 ret[1] = c1;
559 ret[2] = c2;
560 return ret;
561 }
562
563
564 /** BigInteger greatest common divisor.
565 * @param A BigInteger.
566 * @param B BigInteger.
567 * @return gcd(A,B).
568 */
569 public static BigInteger IGCD(BigInteger A, BigInteger B) {
570 if ( A == null ) return null;
571 return A.gcd(B);
572 }
573
574
575 /** BigInteger random.
576 * @param n such that 0 ≤ r ≤ (2<sup>n</sup>-1).
577 * @return r, a random BigInteger.
578 */
579 public BigInteger random(int n) {
580 return random(n,random);
581 }
582
583
584 /** BigInteger random.
585 * @param n such that 0 ≤ r ≤ (2<sup>n</sup>-1).
586 * @param rnd is a source for random bits.
587 * @return r, a random BigInteger.
588 */
589 public BigInteger random(int n, Random rnd) {
590 java.math.BigInteger r = new java.math.BigInteger( n, rnd );
591 if ( rnd.nextBoolean() ) {
592 r = r.negate();
593 }
594 return new BigInteger( r );
595 }
596
597
598 /** BigInteger random.
599 * @param NL such that 0 ≤ r ≤ (2<sup>n</sup>-1).
600 * @return r, a random BigInteger.
601 */
602 public static BigInteger IRAND(int NL) {
603 return ONE.random(NL,random);
604 }
605
606
607 /** BigInteger multiply.
608 * @param S BigInteger.
609 * @return this*S.
610 */
611 public BigInteger multiply(BigInteger S) {
612 return new BigInteger( val.multiply( S.val ) );
613 }
614
615
616 /** BigInteger multiply.
617 * @param A BigInteger.
618 * @param B BigInteger.
619 * @return A*B.
620 */
621 public static BigInteger IPROD(BigInteger A, BigInteger B) {
622 if ( A == null ) return null;
623 return A.multiply(B);
624 }
625
626
627 /** BigInteger summation.
628 * @param S BigInteger.
629 * @return this+S.
630 */
631 public BigInteger sum(BigInteger S) {
632 return new BigInteger( val.add( S.val ) );
633 }
634
635
636 /** BigInteger addition.
637 * @param A BigInteger.
638 * @param B BigInteger.
639 * @return A+B.
640 */
641 public static BigInteger ISUM(BigInteger A, BigInteger B) {
642 if ( A == null ) return null;
643 return A.sum(B);
644 }
645
646
647 /** BigInteger parse from String.
648 * @param s String.
649 * @return Biginteger from s.
650 */
651 public BigInteger parse(String s) {
652 return new BigInteger(s);
653 }
654
655
656 /** BigInteger parse from Reader.
657 * @param r Reader.
658 * @return next Biginteger from r.
659 */
660 public BigInteger parse(Reader r) {
661 return parse( StringUtil.nextString(r) );
662 }
663
664
665 private boolean nonNegative = true;
666
667
668 /** Set the iteration algorithm to all elements.
669 */
670 public void setAllIterator() {
671 nonNegative = false;
672 }
673
674
675 /** Set the iteration algorithm to non-negative elements.
676 */
677 public void setNonNegativeIterator() {
678 nonNegative = true;
679 }
680
681
682 /** Get a BigInteger iterator.
683 * @return a iterator over all integers.
684 */
685 public Iterator<BigInteger> iterator() {
686 return new BigIntegerIterator(nonNegative);
687 }
688
689 }
690
691
692 /**
693 * Big integer iterator.
694 * @author Heinz Kredel
695 */
696 class BigIntegerIterator implements Iterator<BigInteger> {
697
698
699 /**
700 * data structure.
701 */
702 java.math.BigInteger curr;
703
704
705 final boolean nonNegative;
706
707
708 /**
709 * BigInteger iterator constructor.
710 */
711 public BigIntegerIterator() {
712 this(false);
713 }
714
715
716 /**
717 * BigInteger iterator constructor.
718 * @param nn true for an iterator over non-negative longs, false for all elements iterator.
719 */
720 public BigIntegerIterator(boolean nn) {
721 curr = java.math.BigInteger.ZERO;
722 nonNegative = nn;
723 }
724
725
726 /**
727 * Test for availability of a next element.
728 * @return true if the iteration has more elements, else false.
729 */
730 public boolean hasNext() {
731 return true;
732 }
733
734
735 /**
736 * Get next integer.
737 * @return next integer.
738 */
739 public synchronized BigInteger next() {
740 BigInteger i = new BigInteger(curr);
741 if ( nonNegative ) {
742 curr = curr.add( java.math.BigInteger.ONE );
743 } else if ( curr.signum() > 0 && ! nonNegative ) {
744 curr = curr.negate();
745 } else {
746 curr = curr.negate().add( java.math.BigInteger.ONE );
747 }
748 return i;
749 }
750
751
752 /**
753 * Remove an element if allowed.
754 */
755 public void remove() {
756 throw new UnsupportedOperationException("cannnot remove elements");
757 }
758 }