001/*
002 * $Id$
003 */
004
005package edu.jas.arith;
006
007
008import java.io.Reader;
009import java.math.BigInteger;
010import java.math.MathContext;
011import java.util.ArrayList;
012import java.util.Collections;
013import java.util.HashSet;
014import java.util.Iterator;
015import java.util.List;
016import java.util.Random;
017import java.util.Set;
018
019import edu.jas.kern.Scripting;
020import edu.jas.kern.StringUtil;
021import edu.jas.structure.GcdRingElem;
022import edu.jas.structure.RingFactory;
023
024
025/**
026 * Immutable arbitrary-precision rational numbers. BigRational class based on
027 * BigInteger and implementing the RingElem interface. BigInteger is from
028 * java.math in the implementation. The SAC2 static methods are also provided.
029 * @author Heinz Kredel
030 */
031
032public final class BigRational implements GcdRingElem<BigRational>, RingFactory<BigRational>, Rational,
033                Iterable<BigRational> {
034
035
036    /**
037     * Numerator part of the data structure.
038     */
039    public final BigInteger num;
040
041
042    /**
043     * Denominator part of the data structure.
044     */
045    public final BigInteger den;
046
047
048    /**
049     * The Constant 0.
050     */
051    public final static BigRational ZERO = new BigRational(BigInteger.ZERO);
052
053
054    /**
055     * The Constant 1.
056     */
057    public final static BigRational ONE = new BigRational(BigInteger.ONE);
058
059
060    /**
061     * The Constant 1/2.
062     */
063    public final static BigRational HALF = new BigRational(1, 2);
064
065
066    private final static Random random = new Random();
067
068
069    /**
070     * Constructor for a BigRational from math.BigIntegers.
071     * @param n math.BigInteger.
072     * @param d math.BigInteger.
073     */
074    protected BigRational(BigInteger n, BigInteger d) {
075        // assert gcd(n,d) == 1
076        num = n;
077        den = d;
078    }
079
080
081    /**
082     * Constructor for a BigRational from math.BigIntegers.
083     * @param n math.BigInteger.
084     */
085    public BigRational(BigInteger n) {
086        num = n;
087        den = BigInteger.ONE; // be aware of static initialization order
088    }
089
090
091    /**
092     * Constructor for a BigRational from jas.arith.BigIntegers.
093     * @param n edu.jas.arith.BigInteger.
094     */
095    public BigRational(edu.jas.arith.BigInteger n) {
096        this(n.getVal());
097    }
098
099
100    /**
101     * Constructor for a BigRational from jas.arith.BigIntegers.
102     * @param n edu.jas.arith.BigInteger.
103     * @param d edu.jas.arith.BigInteger.
104     */
105    public BigRational(edu.jas.arith.BigInteger n, edu.jas.arith.BigInteger d) {
106        BigInteger nu = n.getVal();
107        BigInteger de = d.getVal();
108        BigRational r = RNRED(nu, de);
109        num = r.num;
110        den = r.den;
111    }
112
113
114    /**
115     * Constructor for a BigRational from longs.
116     * @param n long.
117     * @param d long.
118     */
119    public BigRational(long n, long d) {
120        BigInteger nu = BigInteger.valueOf(n);
121        BigInteger de = BigInteger.valueOf(d);
122        BigRational r = RNRED(nu, de);
123        num = r.num;
124        den = r.den;
125    }
126
127
128    /**
129     * Constructor for a BigRational from longs.
130     * @param n long.
131     */
132    public BigRational(long n) {
133        num = BigInteger.valueOf(n);
134        den = BigInteger.ONE;
135    }
136
137
138    /**
139     * Constructor for a BigRational with no arguments.
140     */
141    public BigRational() {
142        num = BigInteger.ZERO;
143        den = BigInteger.ONE;
144    }
145
146
147    /**
148     * Constructor for a BigRational from String.
149     * @param s String.
150     * @throws NumberFormatException
151     */
152    public BigRational(String s) throws NumberFormatException {
153        if (s == null) {
154            num = BigInteger.ZERO;
155            den = BigInteger.ONE;
156            return;
157        }
158        if (s.length() == 0) {
159            num = BigInteger.ZERO;
160            den = BigInteger.ONE;
161            return;
162        }
163        BigInteger n;
164        BigInteger d;
165        s = s.trim();
166        int i = s.indexOf('/');
167        if (i < 0) {
168            i = s.indexOf('.');
169            if (i < 0) {
170                num = new BigInteger(s);
171                den = BigInteger.ONE;
172                return;
173            }
174            if (s.charAt(0) == '-') { // case -0.11111
175                n = new BigInteger(s.substring(1, i));
176            } else {
177                n = new BigInteger(s.substring(0, i));
178            }
179            BigRational r = new BigRational(n);
180            d = new BigInteger(s.substring(i + 1, s.length()));
181            int j = s.length() - i - 1;
182            //System.out.println("j = " + j);
183            //System.out.println("n = " + n);
184            //System.out.println("d = " + d);
185            BigRational z = new BigRational(1, 10);
186            z = z.power(j); //Power.<BigRational> positivePower(z, j);
187            BigRational f = new BigRational(d);
188            f = f.multiply(z);
189            r = r.sum(f);
190            if (s.charAt(0) == '-') {
191                num = r.num.negate();
192            } else {
193                num = r.num;
194            }
195            den = r.den;
196        } else {
197            String sn = s.substring(0, i);
198            String sd = s.substring(i + 1, s.length());
199            BigRational r;
200            if (s.indexOf(".") < 0) { // all integers
201                n = new BigInteger(sn);
202                d = new BigInteger(sd);
203                r = RNRED(n, d);
204            } else { // integers or decimal fractions
205                BigRational rn = new BigRational(sn);
206                BigRational rd = new BigRational(sd);
207                r = rn.divide(rd);
208            }
209            num = r.num;
210            den = r.den;
211            return;
212        }
213    }
214
215
216    /**
217     * Get the corresponding element factory.
218     * @return factory for this Element.
219     * @see edu.jas.structure.Element#factory()
220     */
221    public BigRational factory() {
222        return this;
223    }
224
225
226    /**
227     * Get a list of the generating elements.
228     * @return list of generators for the algebraic structure.
229     * @see edu.jas.structure.ElemFactory#generators()
230     */
231    public List<BigRational> generators() {
232        List<BigRational> g = new ArrayList<BigRational>(1);
233        g.add(getONE());
234        return g;
235    }
236
237
238    /**
239     * Is this structure finite or infinite.
240     * @return true if this structure is finite, else false.
241     * @see edu.jas.structure.ElemFactory#isFinite()
242     */
243    public boolean isFinite() {
244        return false;
245    }
246
247
248    /**
249     * Clone this.
250     * @see java.lang.Object#clone()
251     */
252    @Override
253    public BigRational copy() {
254        return new BigRational(num, den);
255    }
256
257
258    /**
259     * Copy BigRational element c.
260     * @param c BigRational.
261     * @return a copy of c.
262     */
263    public BigRational copy(BigRational c) {
264        return new BigRational(c.num, c.den);
265    }
266
267
268    /**
269     * Return a BigRational approximation of this Element.
270     * @return a BigRational approximation of this.
271     * @see edu.jas.arith.Rational#getRational()
272     */
273    public BigRational getRational() {
274        return this;
275    }
276
277
278    /**
279     * Get the numerator.
280     * @return num.
281     */
282    public BigInteger numerator() {
283        return num;
284    }
285
286
287    /**
288     * Get the denominator.
289     * @return den.
290     */
291    public BigInteger denominator() {
292        return den;
293    }
294
295
296    /**
297     * Get the string representation.
298     * @see java.lang.Object#toString()
299     */
300    @Override
301    public String toString() {
302        if (Scripting.getPrecision() >= 0) {
303            return toString(Scripting.getPrecision());
304        }
305        StringBuffer s = new StringBuffer();
306        s.append(num);
307        if (!den.equals(BigInteger.ONE)) {
308            s.append("/").append(den);
309        }
310        return s.toString();
311    }
312
313
314    /**
315     * Get the decimal string representation with given precision.
316     * @param n precision.
317     * @return decimal approximation.
318     */
319    public String toString(int n) {
320        if (n < 0) {
321            return toString();
322        }
323        java.math.MathContext mc = new java.math.MathContext(n);
324        BigDecimal d = new BigDecimal(this, mc);
325        return d.toString();
326    }
327
328
329    /**
330     * Get the decimal representation.
331     * @return decimal.
332     */
333    public BigDecimal getDecimal() {
334        BigDecimal d = new BigDecimal(this);
335        return d;
336    }
337
338
339    /**
340     * Get this as a <tt>double</tt>.
341     * @return this as a <tt>double</tt>
342     * @see java.lang.Number#doubleValue()
343     */
344    public double doubleValue() {
345        BigDecimal d = new BigDecimal(this, MathContext.DECIMAL64);
346        return d.doubleValue();
347    }
348
349
350    /**
351     * Get a scripting compatible string representation.
352     * @return script compatible representation for this Element.
353     * @see edu.jas.structure.Element#toScript()
354     */
355    @Override
356    public String toScript() {
357        // Python case: (num,den) or num 
358        // Ruby case: num/den or num 
359        StringBuffer s = new StringBuffer();
360        if (den.equals(BigInteger.ONE)) {
361            s.append(num.toString());
362            return s.toString();
363        }
364        if (Scripting.getPrecision() >= 0) {
365            return toString(Scripting.getPrecision());
366        }
367        switch (Scripting.getLang()) {
368        case Python:
369            s.append("(");
370            s.append(num.toString());
371            s.append(",");
372            s.append(den.toString());
373            s.append(")");
374            break;
375        case Ruby:
376        default:
377            s.append(num.toString());
378            s.append("/");
379            s.append(den.toString());
380        }
381        return s.toString();
382    }
383
384
385    /**
386     * Get a scripting compatible string representation of the factory.
387     * @return script compatible representation for this ElemFactory.
388     * @see edu.jas.structure.Element#toScriptFactory()
389     */
390    @Override
391    public String toScriptFactory() {
392        // Python and Ruby case
393        return "QQ()";
394    }
395
396
397    /**
398     * Get the zero element.
399     * @return 0 as BigRational.
400     */
401    public BigRational getZERO() {
402        return ZERO;
403    }
404
405
406    /**
407     * Get the one element.
408     * @return 1 as BigRational.
409     */
410    public BigRational getONE() {
411        return ONE;
412    }
413
414
415    /**
416     * Query if this ring is commutative.
417     * @return true.
418     */
419    public boolean isCommutative() {
420        return true;
421    }
422
423
424    /**
425     * Query if this ring is associative.
426     * @return true.
427     */
428    public boolean isAssociative() {
429        return true;
430    }
431
432
433    /**
434     * Query if this ring is a field.
435     * @return true.
436     */
437    public boolean isField() {
438        return true;
439    }
440
441
442    /**
443     * Characteristic of this ring.
444     * @return characteristic of this ring.
445     */
446    public java.math.BigInteger characteristic() {
447        return BigInteger.ZERO;
448    }
449
450
451    /**
452     * Get a BigRational element from a math.BigInteger.
453     * @param a math.BigInteger.
454     * @return BigRational from a.
455     */
456    public BigRational fromInteger(BigInteger a) {
457        return new BigRational(a);
458    }
459
460
461    /**
462     * Get a BigRational element from a arith.BigInteger.
463     * @param a arith.BigInteger.
464     * @return BigRational from a.
465     */
466    public BigRational fromInteger(edu.jas.arith.BigInteger a) {
467        return new BigRational(a);
468    }
469
470
471    /**
472     * Get a BigRational element from a math.BigInteger.
473     * @param a math.BigInteger.
474     * @return BigRational from a.
475     */
476    public static BigRational valueOf(BigInteger a) {
477        return new BigRational(a);
478    }
479
480
481    /**
482     * Get a BigRational element from a long.
483     * @param a long.
484     * @return BigRational from a.
485     */
486    public BigRational fromInteger(long a) {
487        return new BigRational(a);
488    }
489
490
491    /**
492     * Get a BigRational element from a long.
493     * @param a long.
494     * @return BigRational from a.
495     */
496    public static BigRational valueOf(long a) {
497        return new BigRational(a);
498    }
499
500
501    /**
502     * Is BigRational zero.
503     * @return If this is 0 then true is returned, else false.
504     * @see edu.jas.structure.RingElem#isZERO()
505     */
506    public boolean isZERO() {
507        return num.signum() == 0; //equals(BigInteger.ZERO);
508    }
509
510
511    /**
512     * Is BigRational one.
513     * @return If this is 1 then true is returned, else false.
514     * @see edu.jas.structure.RingElem#isONE()
515     */
516    public boolean isONE() {
517        return num.equals(den);
518    }
519
520
521    /**
522     * Is BigRational unit.
523     * @return If this is a unit then true is returned, else false.
524     * @see edu.jas.structure.RingElem#isUnit()
525     */
526    public boolean isUnit() {
527        return !isZERO();
528    }
529
530
531    /**
532     * Is BigRational entier.
533     * @return If this is an integer then true is returned, else false.
534     */
535    public boolean isEntier() {
536        return isZERO() || den.equals(BigInteger.ONE);
537    }
538
539
540    /**
541     * Comparison with any other object.
542     * @see java.lang.Object#equals(java.lang.Object)
543     */
544    @Override
545    public boolean equals(Object b) {
546        if (!(b instanceof BigRational)) {
547            return false;
548        }
549        BigRational br = (BigRational) b;
550        return num.equals(br.num) && den.equals(br.den);
551    }
552
553
554    /**
555     * Hash code for this BigRational.
556     * @see java.lang.Object#hashCode()
557     */
558    @Override
559    public int hashCode() {
560        return 37 * num.hashCode() + den.hashCode();
561    }
562
563
564    /**
565     * Rational number reduction to lowest terms.
566     * @param n BigInteger.
567     * @param d BigInteger.
568     * @return a/b ~ n/d, gcd(a,b) = 1, b &gt; 0.
569     */
570    public static BigRational RNRED(BigInteger n, BigInteger d) {
571        BigInteger num;
572        BigInteger den;
573        if (d.equals(BigInteger.ZERO)) {
574            throw new RuntimeException("rational number denominator is zero");
575        }
576        if (n.equals(BigInteger.ZERO)) {
577            num = n;
578            den = BigInteger.ONE;
579            return new BigRational(num, den);
580        }
581        if (n.equals(d)) {
582            num = BigInteger.ONE;
583            den = BigInteger.ONE;
584            return new BigRational(num, den);
585        }
586        BigInteger c = n.gcd(d);
587        if (c.equals(BigInteger.ONE)) {
588            num = n;
589            den = d;
590        } else {
591            num = n.divide(c);
592            den = d.divide(c);
593        }
594        if (den.signum() < 0) {
595            num = num.negate();
596            den = den.negate();
597        }
598        return new BigRational(num, den);
599    }
600
601
602    /**
603     * Rational number reduction to lowest terms.
604     * @param n BigInteger.
605     * @param d BigInteger.
606     * @return a/b ~ n/d, gcd(a,b) = 1, b &gt; 0.
607     */
608    public static BigRational reduction(BigInteger n, BigInteger d) {
609        return RNRED(n, d);
610    }
611
612
613    /**
614     * Rational number absolute value.
615     * @return the absolute value of this.
616     * @see edu.jas.structure.RingElem#abs()
617     */
618    public BigRational abs() {
619        if (this.signum() >= 0) {
620            return this;
621        }
622        return this.negate();
623    }
624
625
626    /**
627     * Rational number absolute value.
628     * @param R is a rational number.
629     * @return the absolute value of R.
630     */
631    public static BigRational RNABS(BigRational R) {
632        if (R == null)
633            return null;
634        return R.abs();
635    }
636
637
638    /**
639     * Rational number comparison.
640     * @param S BigRational.
641     * @return SIGN(this-S).
642     */
643    @Override
644    public int compareTo(BigRational S) {
645        BigInteger J2Y;
646        BigInteger J3Y;
647        BigInteger R1;
648        BigInteger R2;
649        BigInteger S1;
650        BigInteger S2;
651        int J1Y;
652        int SL;
653        int TL;
654        int RL;
655        if (this.equals(ZERO)) {
656            return -S.signum();
657        }
658        if (S.equals(ZERO)) {
659            return this.signum();
660        }
661        R1 = num; //this.numerator(); 
662        R2 = den; //this.denominator();
663        S1 = S.num;
664        S2 = S.den;
665        RL = R1.signum();
666        SL = S1.signum();
667        J1Y = (RL - SL);
668        TL = (J1Y / 2);
669        if (TL != 0) {
670            return TL;
671        }
672        J3Y = R1.multiply(S2);
673        J2Y = R2.multiply(S1);
674        TL = J3Y.compareTo(J2Y);
675        return TL;
676    }
677
678
679    /**
680     * Rational number comparison.
681     * @param R BigRational.
682     * @param S BigRational.
683     * @return SIGN(R-S).
684     */
685    public static int RNCOMP(BigRational R, BigRational S) {
686        if (R == null)
687            return Integer.MAX_VALUE;
688        return R.compareTo(S);
689    }
690
691
692    /**
693     * Rational number denominator.
694     * @param R BigRational.
695     * @return R.denominator().
696     */
697    public static BigInteger RNDEN(BigRational R) {
698        if (R == null)
699            return null;
700        return R.den;
701    }
702
703
704    /**
705     * Rational number difference.
706     * @param S BigRational.
707     * @return this-S.
708     */
709    public BigRational subtract(BigRational S) {
710        return this.sum(S.negate());
711    }
712
713
714    /**
715     * Rational number difference.
716     * @param R BigRational.
717     * @param S BigRational.
718     * @return R-S.
719     */
720    public static BigRational RNDIF(BigRational R, BigRational S) {
721        if (R == null)
722            return S.negate();
723        return R.subtract(S);
724    }
725
726
727    /**
728     * Rational number decimal write. R is a rational number. n is a
729     * non-negative integer. R is approximated by a decimal fraction D with n
730     * decimal digits following the decimal point and D is written in the output
731     * stream. The inaccuracy of the approximation is at most (1/2)*10**-n.
732     * @param R
733     * @param NL
734     */
735    // If ABS(D) is greater than ABS(R) then the last digit is
736    // followed by a minus sign, if ABS(D) is less than ABS(R) then by a
737    // plus sign. 
738    public static void RNDWR(BigRational R, int NL) {
739        //BigInteger num = R.num;
740        //BigInteger den = R.den;
741        java.math.MathContext mc = new java.math.MathContext(NL);
742        BigDecimal d = new BigDecimal(R, mc);
743        System.out.print(d.toString());
744        return;
745    }
746
747
748    /**
749     * Rational number from integer.
750     * @param A BigInteger.
751     * @return A/1.
752     */
753    public static BigRational RNINT(BigInteger A) {
754        return new BigRational(A);
755    }
756
757
758    /**
759     * Rational number inverse.
760     * @return 1/this.
761     * @see edu.jas.structure.RingElem#inverse()
762     */
763    public BigRational inverse() {
764        BigInteger R1 = num;
765        BigInteger R2 = den;
766        BigInteger S1;
767        BigInteger S2;
768        if (R1.signum() >= 0) {
769            S1 = R2;
770            S2 = R1;
771        } else {
772            S1 = R2.negate();
773            S2 = R1.negate();
774        }
775        return new BigRational(S1, S2);
776    }
777
778
779    /**
780     * Rational number inverse.
781     * @param R BigRational.
782     * @return 1/R.
783     */
784    public static BigRational RNINV(BigRational R) {
785        if (R == null)
786            return null;
787        return R.inverse();
788    }
789
790
791    /**
792     * Rational number negative.
793     * @return -this.
794     * @see edu.jas.structure.RingElem#negate()
795     */
796    public BigRational negate() {
797        BigInteger n = num.negate();
798        return new BigRational(n, den);
799    }
800
801
802    /**
803     * Rational number negative.
804     * @param R BigRational.
805     * @return -R.
806     */
807    public static BigRational RNNEG(BigRational R) {
808        if (R == null)
809            return null;
810        return R.negate();
811    }
812
813
814    /**
815     * Rational number numerator.
816     * @param R BigRational.
817     * @return R.numerator().
818     */
819    public static BigInteger RNNUM(BigRational R) {
820        if (R == null)
821            return null;
822        return R.num;
823    }
824
825
826    /**
827     * Rational number product.
828     * @param S BigRational.
829     * @return this*S.
830     */
831    public BigRational multiply(BigRational S) {
832        BigInteger D1 = null;
833        BigInteger D2 = null;
834        BigInteger R1 = null;
835        BigInteger R2 = null;
836        BigInteger RB1 = null;
837        BigInteger RB2 = null;
838        BigInteger S1 = null;
839        BigInteger S2 = null;
840        BigInteger SB1 = null;
841        BigInteger SB2 = null;
842        BigRational T;
843        BigInteger T1;
844        BigInteger T2;
845        if (this.equals(ZERO) || S.equals(ZERO)) {
846            T = ZERO;
847            return T;
848        }
849        R1 = num; //this.numerator(); 
850        R2 = den; //this.denominator();
851        S1 = S.num;
852        S2 = S.den;
853        if (R2.equals(BigInteger.ONE) && S2.equals(BigInteger.ONE)) {
854            T1 = R1.multiply(S1);
855            T = new BigRational(T1, BigInteger.ONE);
856            return T;
857        }
858        if (R2.equals(BigInteger.ONE)) {
859            if (R1.equals(S2)) {
860                D1 = R1;
861            } else {
862                D1 = R1.gcd(S2);
863            }
864            RB1 = R1.divide(D1);
865            SB2 = S2.divide(D1);
866            T1 = RB1.multiply(S1);
867            T = new BigRational(T1, SB2);
868            return T;
869        }
870        if (S2.equals(BigInteger.ONE)) {
871            if (S1.equals(R2)) {
872                D2 = S1;
873            } else {
874                D2 = S1.gcd(R2);
875            }
876            SB1 = S1.divide(D2);
877            RB2 = R2.divide(D2);
878            T1 = SB1.multiply(R1);
879            T = new BigRational(T1, RB2);
880            return T;
881        }
882        if (R1.equals(S2)) {
883            D1 = R1;
884        } else {
885            D1 = R1.gcd(S2);
886        }
887        RB1 = R1.divide(D1);
888        SB2 = S2.divide(D1);
889        if (S1.equals(R2)) {
890            D2 = S1;
891        } else {
892            D2 = S1.gcd(R2);
893        }
894        SB1 = S1.divide(D2);
895        RB2 = R2.divide(D2);
896        T1 = RB1.multiply(SB1);
897        T2 = RB2.multiply(SB2);
898        T = new BigRational(T1, T2);
899        return T;
900    }
901
902
903    /**
904     * Rational number product.
905     * @param R BigRational.
906     * @param S BigRational.
907     * @return R*S.
908     */
909    public static BigRational RNPROD(BigRational R, BigRational S) {
910        if (R == null) {
911            return R;
912        }
913        return R.multiply(S);
914    }
915
916
917    /**
918     * Rational number quotient.
919     * @param S BigRational.
920     * @return this/S.
921     */
922    public BigRational divide(BigRational S) {
923        return multiply(S.inverse());
924    }
925
926
927    /**
928     * Rational number quotient.
929     * @param R BigRational.
930     * @param S BigRational.
931     * @return R/S.
932     */
933    public static BigRational RNQ(BigRational R, BigRational S) {
934        if (R == null) {
935            return R;
936        }
937        return R.divide(S);
938    }
939
940
941    /**
942     * Rational number remainder.
943     * @param S BigRational.
944     * @return this-(this/S)*S
945     */
946    public BigRational remainder(BigRational S) {
947        if (S.isZERO()) {
948            throw new ArithmeticException("division by zero");
949        }
950        return ZERO;
951    }
952
953
954    /**
955     * Quotient and remainder by division of this by S.
956     * @param S a rational number
957     * @return [this/S, this - (this/S)*S].
958     */
959    public BigRational[] quotientRemainder(BigRational S) {
960        return new BigRational[] { divide(S), ZERO };
961    }
962
963
964    /**
965     * Rational number, random. Random integers A, B and a random sign s are
966     * generated using BigInteger(n,random) and random.nextBoolen(). Then R =
967     * s*A/(B+1), reduced to lowest terms.
968     * @param n such that 0 &le; A, B &le; (2<sup>n</sup>-1).
969     * @return a random BigRational.
970     */
971    public BigRational random(int n) {
972        return random(n, random);
973    }
974
975
976    /**
977     * Rational number, random. Random integers A, B and a random sign s are
978     * generated using BigInteger(n,random) and random.nextBoolen(). Then R =
979     * s*A/(B+1), reduced to lowest terms.
980     * @param n such that 0 &le; A, B &le; (2<sup>n</sup>-1).
981     * @param rnd is a source for random bits.
982     * @return a random BigRational.
983     */
984    public BigRational random(int n, Random rnd) {
985        BigInteger A;
986        BigInteger B;
987        A = new BigInteger(n, rnd); // always positive
988        if (rnd.nextBoolean()) {
989            A = A.negate();
990        }
991        B = new BigInteger(n, rnd); // always positive
992        B = B.add(BigInteger.ONE);
993        return RNRED(A, B);
994    }
995
996
997    /**
998     * Rational number, random. Random integers A, B and a random sign s are
999     * generated using BigInteger(n,random) and random.nextBoolen(). Then R =
1000     * s*A/(B+1), reduced to lowest terms.
1001     * @param NL such that 0 &le; A, B &le; (2<sup>n</sup>-1).
1002     * @return a random BigRational.
1003     */
1004    public static BigRational RNRAND(int NL) {
1005        return ONE.random(NL, random);
1006    }
1007
1008
1009    /**
1010     * Rational number sign.
1011     * @see edu.jas.structure.RingElem#signum()
1012     */
1013    public int signum() {
1014        return num.signum();
1015    }
1016
1017
1018    /**
1019     * Rational number sign.
1020     * @param R BigRational.
1021     * @return R.signum().
1022     */
1023    public static int RNSIGN(BigRational R) {
1024        if (R == null) {
1025            return 0;
1026        }
1027        return R.signum();
1028    }
1029
1030
1031    /**
1032     * Rational number sum.
1033     * @param S BigRational.
1034     * @return this+S.
1035     */
1036    public BigRational sum(BigRational S) {
1037        BigInteger D = null;
1038        BigInteger E, J1Y, J2Y;
1039        BigRational T;
1040        BigInteger R1 = null;
1041        BigInteger R2 = null;
1042        BigInteger RB2 = null;
1043        BigInteger S1 = null;
1044        BigInteger S2 = null;
1045        BigInteger SB2 = null;
1046        BigInteger T1;
1047        BigInteger T2;
1048        if (this.equals(ZERO)) {
1049            return S;
1050        }
1051        if (S.equals(ZERO)) {
1052            return this;
1053        }
1054        R1 = num; //this.numerator(); 
1055        R2 = den; //this.denominator();
1056        S1 = S.num;
1057        S2 = S.den;
1058        if (R2.equals(BigInteger.ONE) && S2.equals(BigInteger.ONE)) {
1059            T1 = R1.add(S1);
1060            T = new BigRational(T1, BigInteger.ONE);
1061            return T;
1062        }
1063        if (R2.equals(BigInteger.ONE)) {
1064            T1 = R1.multiply(S2);
1065            T1 = T1.add(S1);
1066            T = new BigRational(T1, S2);
1067            return T;
1068        }
1069        if (S2.equals(BigInteger.ONE)) {
1070            T1 = R2.multiply(S1);
1071            T1 = T1.add(R1);
1072            T = new BigRational(T1, R2);
1073            return T;
1074        }
1075        if (R2.equals(S2)) {
1076            D = R2;
1077        } else {
1078            D = R2.gcd(S2);
1079        }
1080        if (D.equals(BigInteger.ONE)) {
1081            RB2 = R2;
1082            SB2 = S2;
1083        } else {
1084            RB2 = R2.divide(D);
1085            SB2 = S2.divide(D);
1086        }
1087        J1Y = R1.multiply(SB2);
1088        J2Y = RB2.multiply(S1);
1089        T1 = J1Y.add(J2Y);
1090        if (T1.equals(BigInteger.ZERO)) {
1091            return ZERO;
1092        }
1093        if (!D.equals(BigInteger.ONE)) {
1094            if (T1.equals(D)) {
1095                E = D;
1096            } else {
1097                E = T1.gcd(D);
1098            }
1099            if (!E.equals(BigInteger.ONE)) {
1100                T1 = T1.divide(E);
1101                R2 = R2.divide(E);
1102            }
1103        }
1104        T2 = R2.multiply(SB2);
1105        T = new BigRational(T1, T2);
1106        return T;
1107    }
1108
1109
1110    /**
1111     * Rational number sum.
1112     * @param R BigRational.
1113     * @param S BigRational.
1114     * @return R+S.
1115     */
1116    public static BigRational RNSUM(BigRational R, BigRational S) {
1117        if (R == null) {
1118            return S;
1119        }
1120        return R.sum(S);
1121    }
1122
1123
1124    /**
1125     * Parse rational number from String.
1126     * @param s String.
1127     * @return BigRational from s.
1128     */
1129    public BigRational parse(String s) {
1130        return new BigRational(s);
1131    }
1132
1133
1134    /**
1135     * Parse rational number from Reader.
1136     * @param r Reader.
1137     * @return next BigRational from r.
1138     */
1139    public BigRational parse(Reader r) {
1140        return parse(StringUtil.nextString(r));
1141    }
1142
1143
1144    /**
1145     * Rational number greatest common divisor.
1146     * @param S BigRational.
1147     * @return gcd(this,S).
1148     */
1149    public BigRational gcd(BigRational S) {
1150        if (S == null || S.isZERO()) {
1151            return this;
1152        }
1153        if (this.isZERO()) {
1154            return S;
1155        }
1156        return ONE;
1157    }
1158
1159
1160    /**
1161     * BigRational extended greatest common divisor.
1162     * @param S BigRational.
1163     * @return [ gcd(this,S), a, b ] with a*this + b*S = gcd(this,S).
1164     */
1165    public BigRational[] egcd(BigRational S) {
1166        BigRational[] ret = new BigRational[3];
1167        ret[0] = null;
1168        ret[1] = null;
1169        ret[2] = null;
1170        if (S == null || S.isZERO()) {
1171            ret[0] = this;
1172            return ret;
1173        }
1174        if (this.isZERO()) {
1175            ret[0] = S;
1176            return ret;
1177        }
1178        BigRational half = new BigRational(1, 2);
1179        ret[0] = ONE;
1180        ret[1] = this.inverse().multiply(half);
1181        ret[2] = S.inverse().multiply(half);
1182        return ret;
1183    }
1184
1185
1186    /**
1187     * BigRational ceiling.
1188     * @return ceiling of this.
1189     */
1190    public BigInteger ceil() {
1191        if (isEntier()) {
1192            return num;
1193        }
1194        BigInteger[] qr = num.divideAndRemainder(den);
1195        //System.out.println("ceil: " + this + ", q = " + qr[0] + ", r = " +qr[1]);
1196        BigInteger q = qr[0];
1197        if (qr[1].signum() > 0) {
1198            q = q.add(BigInteger.ONE);
1199        }
1200        return q;
1201    }
1202
1203
1204    /**
1205     * BigRational floor.
1206     * @return floor of this.
1207     */
1208    public BigInteger floor() {
1209        if (isEntier()) {
1210            return num;
1211        }
1212        BigInteger[] qr = num.divideAndRemainder(den);
1213        //System.out.println("floor: " + this + ", q = " + qr[0] + ", r = " +qr[1]);
1214        BigInteger q = qr[0];
1215        if (qr[1].signum() < 0) {
1216            q = q.subtract(BigInteger.ONE);
1217        }
1218        return q;
1219    }
1220
1221
1222    /**
1223     * Returns the number of bits in the representation of this BigRational,
1224     * including a sign bit. For positive BigRational, this is equivalent to
1225     * {@code num.bitLength()+den.bitLength()}.)
1226     * @return number of bits in the representation of this BigRational,
1227     *         including a sign bit.
1228     */
1229    public long bitLength() {
1230        long n = num.bitLength();
1231        if (num.signum() < 0) {
1232            n++;
1233        }
1234        n++;
1235        n += den.bitLength();
1236        // den.signum() > 0
1237        n++;
1238        return n;
1239    }
1240
1241
1242    private boolean nonNegative = true;
1243
1244
1245    private boolean duplicates = true;
1246
1247
1248    /**
1249     * Set the iteration algorithm to all elements.
1250     */
1251    public void setAllIterator() {
1252        nonNegative = false;
1253    }
1254
1255
1256    /**
1257     * Set the iteration algorithm to non-negative elements.
1258     */
1259    public void setNonNegativeIterator() {
1260        nonNegative = true;
1261    }
1262
1263
1264    /**
1265     * Set the iteration algorithm to no duplicate elements.
1266     */
1267    public void setNoDuplicatesIterator() {
1268        duplicates = false;
1269    }
1270
1271
1272    /**
1273     * Set the iteration algorithm to allow duplicate elements.
1274     */
1275    public void setDuplicatesIterator() {
1276        duplicates = true;
1277    }
1278
1279
1280    /**
1281     * Get a BigRational iterator.
1282     * @return a iterator over all rationals.
1283     */
1284    public Iterator<BigRational> iterator() {
1285        if (duplicates) {
1286            return new BigRationalIterator(nonNegative);
1287        }
1288        return new BigRationalUniqueIterator(new BigRationalIterator(nonNegative));
1289    }
1290
1291
1292    /**
1293     * Get a BigRational iterator with no duplicates.
1294     * @return a iterator over all rationals without duplicates.
1295     */
1296    public Iterator<BigRational> uniqueIterator() {
1297        return new BigRationalUniqueIterator(new BigRationalIterator(nonNegative));
1298    }
1299
1300}
1301
1302
1303/**
1304 * Big rational iterator. Uses Cantors diagonal enumeration.
1305 * @author Heinz Kredel
1306 */
1307class BigRationalIterator implements Iterator<BigRational> {
1308
1309
1310    /**
1311     * data structure.
1312     */
1313    BigRational curr;
1314
1315
1316    edu.jas.arith.BigInteger den;
1317
1318
1319    edu.jas.arith.BigInteger num;
1320
1321
1322    Iterator<edu.jas.arith.BigInteger> denit;
1323
1324
1325    Iterator<edu.jas.arith.BigInteger> numit;
1326
1327
1328    List<edu.jas.arith.BigInteger> denlist;
1329
1330
1331    List<edu.jas.arith.BigInteger> numlist;
1332
1333
1334    Iterator<edu.jas.arith.BigInteger> denlistit;
1335
1336
1337    Iterator<edu.jas.arith.BigInteger> numlistit;
1338
1339
1340    final boolean nonNegative;
1341
1342
1343    protected long level;
1344
1345
1346    /**
1347     * BigRational iterator constructor.
1348     */
1349    public BigRationalIterator() {
1350        this(false);
1351    }
1352
1353
1354    /**
1355     * BigRational iterator constructor.
1356     * @param nn indicator for a non-negative iterator, if true, false for an
1357     *            all iterator
1358     */
1359    public BigRationalIterator(boolean nn) {
1360        nonNegative = nn;
1361        curr = edu.jas.arith.BigRational.ZERO;
1362        level = 0;
1363        den = new edu.jas.arith.BigInteger(); // ZERO
1364        num = edu.jas.arith.BigInteger.ONE.copy();
1365        if (nonNegative) {
1366            den.setNonNegativeIterator();
1367        } else {
1368            den.setAllIterator();
1369        }
1370        num.setNonNegativeIterator();
1371        denit = den.iterator();
1372        numit = num.iterator();
1373        denlist = new ArrayList<edu.jas.arith.BigInteger>();
1374        numlist = new ArrayList<edu.jas.arith.BigInteger>();
1375        edu.jas.arith.BigInteger unused = denit.next(); // skip zero denominator
1376        unused = numit.next();
1377        if (unused == null) { // use for findbugs
1378            System.out.println("unused is null");
1379        }
1380        denlist.add(denit.next());
1381        numlist.add(numit.next());
1382        denlistit = denlist.iterator();
1383        numlistit = numlist.iterator();
1384    }
1385
1386
1387    /**
1388     * Test for availability of a next element.
1389     * @return true if the iteration has more elements, else false.
1390     */
1391    public boolean hasNext() {
1392        return true;
1393    }
1394
1395
1396    /**
1397     * Get next rational.
1398     * @return next rational.
1399     */
1400    public synchronized BigRational next() {
1401        BigRational r = curr;
1402        if (denlistit.hasNext() && numlistit.hasNext()) {
1403            BigInteger d = denlistit.next().val;
1404            BigInteger n = numlistit.next().val;
1405            //System.out.println(d + "//" + n);
1406            curr = BigRational.reduction(d, n);
1407            return r;
1408        }
1409        level++;
1410        if (level % 2 == 1) {
1411            Collections.reverse(denlist);
1412        } else {
1413            Collections.reverse(numlist);
1414        }
1415        denlist.add(denit.next());
1416        numlist.add(numit.next());
1417        if (level % 2 == 0) {
1418            Collections.reverse(denlist);
1419        } else {
1420            Collections.reverse(numlist);
1421        }
1422        //System.out.println("denlist = " + denlist);
1423        //System.out.println("numlist = " + numlist);
1424        denlistit = denlist.iterator();
1425        numlistit = numlist.iterator();
1426        BigInteger d = denlistit.next().val;
1427        BigInteger n = numlistit.next().val;
1428        //System.out.println(d + "//" + n);
1429        curr = BigRational.reduction(d, n);
1430        return r;
1431    }
1432
1433
1434    /**
1435     * Remove an element if allowed.
1436     */
1437    public void remove() {
1438        throw new UnsupportedOperationException("cannot remove elements");
1439    }
1440}
1441
1442
1443/**
1444 * Big rational unique iterator. Uses Cantors diagonal enumeration, produces
1445 * distinct elements.
1446 * @author Heinz Kredel
1447 */
1448class BigRationalUniqueIterator implements Iterator<BigRational> {
1449
1450
1451    /**
1452     * data structure.
1453     */
1454    final Set<BigRational> unique;
1455
1456
1457    final Iterator<BigRational> ratit;
1458
1459
1460    /**
1461     * BigRational iterator constructor.
1462     */
1463    public BigRationalUniqueIterator() {
1464        this(BigRational.ONE.iterator());
1465    }
1466
1467
1468    /**
1469     * BigRational iterator constructor.
1470     * @param rit backing rational iterator of non unique elements
1471     */
1472    public BigRationalUniqueIterator(Iterator<BigRational> rit) {
1473        ratit = rit;
1474        unique = new HashSet<BigRational>();
1475    }
1476
1477
1478    /**
1479     * Test for availability of a next element.
1480     * @return true if the iteration has more elements, else false.
1481     */
1482    public synchronized boolean hasNext() {
1483        return ratit.hasNext();
1484    }
1485
1486
1487    /**
1488     * Get next rational.
1489     * @return next rational.
1490     */
1491    public synchronized BigRational next() {
1492        // TODO: use curr = BigRational.reduction(d, n);
1493        // with curr.d == d to avoid unique
1494        BigRational r = ratit.next();
1495        while (unique.contains(r)) {
1496            //System.out.println("duplicate " + r);
1497            r = ratit.next();
1498        }
1499        unique.add(r);
1500        return r;
1501    }
1502
1503
1504    /**
1505     * Remove an element if allowed.
1506     */
1507    public void remove() {
1508        throw new UnsupportedOperationException("cannot remove elements");
1509    }
1510}