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