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