Source code

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