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