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