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