001/* 002 * $Id$ 003 */ 004 005package edu.jas.arith; 006 007 008import java.io.Reader; 009import java.util.ArrayList; 010import java.util.Iterator; 011import java.util.List; 012import java.util.Random; 013 014import edu.jas.kern.StringUtil; 015import edu.jas.structure.GcdRingElem; 016import edu.jas.structure.NotInvertibleException; 017import edu.jas.structure.RingFactory; 018 019 020/** 021 * BigInteger class to make java.math.BigInteger available with RingElem 022 * respectively the GcdRingElem interface. Objects of this class are immutable. 023 * The SAC2 static methods are also provided. 024 * @author Heinz Kredel 025 * @see java.math.BigInteger 026 */ 027 028public final class BigInteger 029 implements GcdRingElem<BigInteger>, RingFactory<BigInteger>, Iterable<BigInteger>, Rational { 030 031 032 /** 033 * The data structure. 034 */ 035 public final java.math.BigInteger val; 036 037 038 private final static Random random = new Random(); 039 040 041 /** 042 * The constant 0. 043 */ 044 public final static BigInteger ZERO = new BigInteger(java.math.BigInteger.ZERO); 045 046 047 /** 048 * The constant 1. 049 */ 050 public final static BigInteger ONE = new BigInteger(java.math.BigInteger.ONE); 051 052 053 /** 054 * The constant 2. 055 */ 056 public final static BigInteger TWO = new BigInteger(2); 057 058 059 /** 060 * Constructor for BigInteger from math.BigInteger. 061 * @param a java.math.BigInteger. 062 */ 063 public BigInteger(java.math.BigInteger a) { 064 val = a; 065 } 066 067 068 /** 069 * Constructor for BigInteger from long. 070 * @param a long. 071 */ 072 public BigInteger(long a) { 073 val = new java.math.BigInteger(String.valueOf(a)); 074 } 075 076 077 /** 078 * Constructor for BigInteger from String. 079 * @param s String. 080 */ 081 public BigInteger(String s) { 082 val = new java.math.BigInteger(s.trim()); 083 } 084 085 086 /** 087 * Constructor for BigInteger without parameters. 088 */ 089 public BigInteger() { 090 val = java.math.BigInteger.ZERO; 091 } 092 093 094 /** 095 * Get the value. 096 * @return val java.math.BigInteger. 097 */ 098 public java.math.BigInteger getVal() { 099 return val; 100 } 101 102 103 /** 104 * Get the value as long. 105 * @return val as long. 106 */ 107 public long longValue() { 108 return val.longValue(); 109 } 110 111 112 /** 113 * Get the value as long. 114 * @return val as long if val fits in long. 115 */ 116 public long longValueExact() { 117 return val.longValueExact(); 118 } 119 120 121 /** 122 * Get the corresponding element factory. 123 * @return factory for this Element. 124 * @see edu.jas.structure.Element#factory() 125 */ 126 public BigInteger factory() { 127 return this; 128 } 129 130 131 /** 132 * Get a list of the generating elements. 133 * @return list of generators for the algebraic structure. 134 * @see edu.jas.structure.ElemFactory#generators() 135 */ 136 public List<BigInteger> generators() { 137 List<BigInteger> g = new ArrayList<BigInteger>(1); 138 g.add(getONE()); 139 return g; 140 } 141 142 143 /** 144 * Is this structure finite or infinite. 145 * @return true if this structure is finite, else false. 146 * @see edu.jas.structure.ElemFactory#isFinite() 147 */ 148 public boolean isFinite() { 149 return false; 150 } 151 152 153 /** 154 * Clone this. 155 * @see java.lang.Object#clone() 156 */ 157 @Override 158 public BigInteger copy() { 159 return new BigInteger(val); 160 } 161 162 163 /** 164 * Copy BigInteger element c. 165 * @param c BigInteger. 166 * @return a copy of c. 167 */ 168 public BigInteger copy(BigInteger c) { 169 return new BigInteger(c.val); 170 } 171 172 173 /** 174 * Get the zero element. 175 * @return 0. 176 */ 177 public BigInteger getZERO() { 178 return ZERO; 179 } 180 181 182 /** 183 * Get the one element. 184 * @return 1. 185 */ 186 public BigInteger getONE() { 187 return ONE; 188 } 189 190 191 /** 192 * Query if this ring is commutative. 193 * @return true. 194 */ 195 public boolean isCommutative() { 196 return true; 197 } 198 199 200 /** 201 * Query if this ring is associative. 202 * @return true. 203 */ 204 public boolean isAssociative() { 205 return true; 206 } 207 208 209 /** 210 * Query if this ring is a field. 211 * @return false. 212 */ 213 public boolean isField() { 214 return false; 215 } 216 217 218 /** 219 * Characteristic of this ring. 220 * @return characteristic of this ring. 221 */ 222 public java.math.BigInteger characteristic() { 223 return java.math.BigInteger.ZERO; 224 } 225 226 227 /** 228 * Get a BigInteger element from a math.BigInteger. 229 * @param a math.BigInteger. 230 * @return a as BigInteger. 231 */ 232 public BigInteger fromInteger(java.math.BigInteger a) { 233 return new BigInteger(a); 234 } 235 236 237 /** 238 * Get a BigInteger element from a math.BigInteger. 239 * @param a math.BigInteger. 240 * @return a as BigInteger. 241 */ 242 public static BigInteger valueOf(java.math.BigInteger a) { 243 return new BigInteger(a); 244 } 245 246 247 /** 248 * Get a BigInteger element from long. 249 * @param a long. 250 * @return a as BigInteger. 251 */ 252 public BigInteger fromInteger(long a) { 253 return new BigInteger(a); 254 } 255 256 257 /** 258 * Get a BigInteger element from long. 259 * @param a long. 260 * @return a as BigInteger. 261 */ 262 public static BigInteger valueOf(long a) { 263 return new BigInteger(a); 264 } 265 266 267 /** 268 * Is BigInteger number zero. 269 * @return If this is 0 then true is returned, else false. 270 * @see edu.jas.structure.RingElem#isZERO() 271 */ 272 public boolean isZERO() { 273 return val.signum() == 0; //equals(java.math.BigInteger.ZERO); 274 } 275 276 277 /** 278 * Is BigInteger number one. 279 * @see edu.jas.structure.RingElem#isONE() 280 */ 281 public boolean isONE() { 282 return val.equals(java.math.BigInteger.ONE); 283 } 284 285 286 /** 287 * Is BigInteger number unit. 288 * @see edu.jas.structure.RingElem#isUnit() 289 */ 290 public boolean isUnit() { 291 return (this.isONE() || this.negate().isONE()); 292 } 293 294 295 /** 296 * Get the String representation. 297 * @see java.lang.Object#toString() 298 */ 299 @Override 300 public String toString() { 301 return val.toString(); 302 } 303 304 305 /** 306 * Get a scripting compatible string representation. 307 * @return script compatible representation for this Element. 308 * @see edu.jas.structure.Element#toScript() 309 */ 310 @Override 311 public String toScript() { 312 // Python case 313 return toString(); 314 } 315 316 317 /** 318 * Get a scripting compatible string representation of the factory. 319 * @return script compatible representation for this ElemFactory. 320 * @see edu.jas.structure.Element#toScriptFactory() 321 */ 322 @Override 323 public String toScriptFactory() { 324 // Python case 325 return "ZZ()"; 326 } 327 328 329 /** 330 * Compare to BigInteger b. 331 * @param b BigInteger. 332 * @return 0 if this == b, 1 if this > b, -1 if this < b. 333 */ 334 @Override 335 public int compareTo(BigInteger b) { 336 return val.compareTo(b.val); 337 } 338 339 340 /** 341 * Integer comparison. 342 * @param A BigInteger. 343 * @param B BigInteger. 344 * @return 0 if A == B, 1 if A > B, -1 if A < B. 345 */ 346 public static int ICOMP(BigInteger A, BigInteger B) { 347 if (A == null) 348 return -B.signum(); 349 return A.compareTo(B); 350 } 351 352 353 /** 354 * Comparison with any other object. 355 * @see java.lang.Object#equals(java.lang.Object) 356 */ 357 @Override 358 public boolean equals(Object b) { 359 if (!(b instanceof BigInteger)) { 360 return false; 361 } 362 BigInteger bi = (BigInteger) b; 363 return val.equals(bi.val); 364 } 365 366 367 /** 368 * Hash code for this BigInteger. 369 * @see java.lang.Object#hashCode() 370 */ 371 @Override 372 public int hashCode() { 373 return val.hashCode(); 374 } 375 376 377 /** 378 * Absolute value of this. 379 * @see edu.jas.structure.RingElem#abs() 380 */ 381 public BigInteger abs() { 382 return new BigInteger(val.abs()); 383 } 384 385 386 /** 387 * Absolute value. 388 * @param A BigInteger. 389 * @return abs(A). 390 */ 391 public static BigInteger IABS(BigInteger A) { 392 if (A == null) { 393 throw new IllegalArgumentException("null A not allowed"); 394 } 395 return A.abs(); 396 } 397 398 399 /* Negative value of this. 400 * @see edu.jas.structure.RingElem#negate() 401 */ 402 public BigInteger negate() { 403 return new BigInteger(val.negate()); 404 } 405 406 407 /** 408 * Negative value. 409 * @param A BigInteger. 410 * @return -A. 411 */ 412 public static BigInteger INEG(BigInteger A) { 413 if (A == null) { 414 throw new IllegalArgumentException("null A not allowed"); 415 } 416 return A.negate(); 417 } 418 419 420 /** 421 * signum. 422 * @see edu.jas.structure.RingElem#signum() 423 */ 424 public int signum() { 425 return val.signum(); 426 } 427 428 429 /** 430 * Integer signum. 431 * @param A BigInteger. 432 * @return signum(A). 433 */ 434 public static int ISIGN(BigInteger A) { 435 if (A == null) 436 return 0; 437 return A.signum(); 438 } 439 440 441 /** 442 * BigInteger subtract. 443 * @param S BigInteger. 444 * @return this-S. 445 */ 446 public BigInteger subtract(BigInteger S) { 447 return new BigInteger(val.subtract(S.val)); 448 } 449 450 451 /** 452 * BigInteger subtract. 453 * @param A BigInteger. 454 * @param B BigInteger. 455 * @return A-B. 456 */ 457 public static BigInteger IDIF(BigInteger A, BigInteger B) { 458 if (A == null) 459 return B.negate(); 460 return A.subtract(B); 461 } 462 463 464 /** 465 * BigInteger divide. 466 * @param S BigInteger. 467 * @return this/S. 468 */ 469 public BigInteger divide(BigInteger S) { 470 return new BigInteger(val.divide(S.val)); 471 } 472 473 474 /** 475 * BigInteger divide. 476 * @param A BigInteger. 477 * @param B BigInteger. 478 * @return A/B. 479 */ 480 public static BigInteger IQ(BigInteger A, BigInteger B) { 481 if (A == null) { 482 throw new IllegalArgumentException("null A not allowed"); 483 } 484 return A.divide(B); 485 } 486 487 488 /** 489 * Integer inverse. R is a non-zero integer. S=1/R if defined else throws 490 * not invertible exception. 491 * @see edu.jas.structure.RingElem#inverse() 492 */ 493 public BigInteger inverse() { 494 if (this.isONE() || this.negate().isONE()) { 495 return this; 496 } 497 //return ZERO; 498 throw new NotInvertibleException("element not invertible " + this + " :: BigInteger"); 499 } 500 501 502 /** 503 * BigInteger remainder. 504 * @param S BigInteger. 505 * @return this - (this/S)*S. 506 */ 507 public BigInteger remainder(BigInteger S) { 508 return new BigInteger(val.remainder(S.val)); 509 } 510 511 512 /** 513 * BigInteger remainder. 514 * @param A BigInteger. 515 * @param B BigInteger. 516 * @return A - (A/B)*B. 517 */ 518 public static BigInteger IREM(BigInteger A, BigInteger B) { 519 if (A == null) { 520 throw new IllegalArgumentException("null A not allowed"); 521 } 522 return A.remainder(B); 523 } 524 525 526 /** 527 * BigInteger compute quotient and remainder. Throws an exception, if S == 528 * 0. 529 * @param S BigInteger. 530 * @return BigInteger[] { q, r } with this = q S + r and 0 ≤ r < |S|. 531 */ 532 //@Override 533 public BigInteger[] quotientRemainder(BigInteger S) { 534 BigInteger[] qr = new BigInteger[2]; 535 java.math.BigInteger[] C = val.divideAndRemainder(S.val); 536 qr[0] = new BigInteger(C[0]); 537 qr[1] = new BigInteger(C[1]); 538 return qr; 539 } 540 541 542 /** 543 * Integer quotient and remainder. A and B are integers, B ne 0. Q is the 544 * quotient, integral part of A/B, and R is the remainder A-B*Q. Throws an 545 * exception, if B == 0. 546 * @param A BigInteger. 547 * @param B BigInteger. 548 * @return BigInteger[] { q, r } with A = q B + r and 0 ≤ r < |B| 549 */ 550 public static BigInteger[] IQR(BigInteger A, BigInteger B) { 551 if (A == null) { 552 throw new IllegalArgumentException("null A not allowed"); 553 } 554 return A.quotientRemainder(B); 555 } 556 557 558 /** 559 * BigInteger greatest common divisor. 560 * @param S BigInteger. 561 * @return gcd(this,S). 562 */ 563 public BigInteger gcd(BigInteger S) { 564 return new BigInteger(val.gcd(S.val)); 565 } 566 567 568 /** 569 * BigInteger extended greatest common divisor. 570 * @param S BigInteger. 571 * @return [ gcd(this,S), a, b ] with a*this + b*S = gcd(this,S). 572 */ 573 public BigInteger[] egcd(BigInteger S) { 574 BigInteger[] ret = new BigInteger[3]; 575 ret[0] = null; 576 ret[1] = null; 577 ret[2] = null; 578 if (S == null || S.isZERO()) { 579 ret[0] = this; 580 return ret; 581 } 582 if (this.isZERO()) { 583 ret[0] = S; 584 return ret; 585 } 586 //System.out.println("this = " + this + ", S = " + S); 587 BigInteger[] qr; 588 BigInteger q = this; 589 BigInteger r = S; 590 BigInteger c1 = ONE; 591 BigInteger d1 = ZERO; 592 BigInteger c2 = ZERO; 593 BigInteger d2 = ONE; 594 BigInteger x1; 595 BigInteger x2; 596 while (!r.isZERO()) { 597 qr = q.quotientRemainder(r); 598 q = qr[0]; 599 x1 = c1.subtract(q.multiply(d1)); 600 x2 = c2.subtract(q.multiply(d2)); 601 c1 = d1; 602 c2 = d2; 603 d1 = x1; 604 d2 = x2; 605 q = r; 606 r = qr[1]; 607 } 608 //System.out.println("q = " + q + "\n c1 = " + c1 + "\n c2 = " + c2); 609 if (q.signum() < 0) { 610 q = q.negate(); 611 c1 = c1.negate(); 612 c2 = c2.negate(); 613 } 614 ret[0] = q; 615 ret[1] = c1; 616 ret[2] = c2; 617 return ret; 618 } 619 620 621 /** 622 * BigInteger greatest common divisor. 623 * @param A BigInteger. 624 * @param B BigInteger. 625 * @return gcd(A,B). 626 */ 627 public static BigInteger IGCD(BigInteger A, BigInteger B) { 628 if (A == null) { 629 throw new IllegalArgumentException("null A not allowed"); 630 } 631 return A.gcd(B); 632 } 633 634 635 /** 636 * BigInteger random. 637 * @param n such that 0 ≤ r ≤ (2<sup>n</sup>-1). 638 * @return r, a random BigInteger. 639 */ 640 public BigInteger random(int n) { 641 return random(n, random); 642 } 643 644 645 /** 646 * BigInteger random. 647 * @param n such that 0 ≤ r ≤ (2<sup>n</sup>-1). 648 * @param rnd is a source for random bits. 649 * @return r, a random BigInteger. 650 */ 651 public BigInteger random(int n, Random rnd) { 652 java.math.BigInteger r = new java.math.BigInteger(n, rnd); 653 if (rnd.nextBoolean()) { 654 r = r.negate(); 655 } 656 return new BigInteger(r); 657 } 658 659 660 /** 661 * BigInteger random. 662 * @param NL such that 0 ≤ r ≤ (2<sup>n</sup>-1). 663 * @return r, a random BigInteger. 664 */ 665 public static BigInteger IRAND(int NL) { 666 return ONE.random(NL, random); 667 } 668 669 670 /** 671 * BigInteger multiply. 672 * @param S BigInteger. 673 * @return this*S. 674 */ 675 public BigInteger multiply(BigInteger S) { 676 return new BigInteger(val.multiply(S.val)); 677 } 678 679 680 /** 681 * BigInteger shift left. 682 * @param n bits to shift. 683 * @return this << n. 684 */ 685 public BigInteger shiftLeft(int n) { 686 return new BigInteger(val.shiftLeft(n)); 687 } 688 689 690 /** 691 * BigInteger multiply. 692 * @param A BigInteger. 693 * @param B BigInteger. 694 * @return A*B. 695 */ 696 public static BigInteger IPROD(BigInteger A, BigInteger B) { 697 if (A == null) { 698 throw new IllegalArgumentException("null A not allowed"); 699 } 700 return A.multiply(B); 701 } 702 703 704 /** 705 * BigInteger summation. 706 * @param S BigInteger. 707 * @return this+S. 708 */ 709 public BigInteger sum(BigInteger S) { 710 return new BigInteger(val.add(S.val)); 711 } 712 713 714 /** 715 * BigInteger addition. 716 * @param A BigInteger. 717 * @param B BigInteger. 718 * @return A+B. 719 */ 720 public static BigInteger ISUM(BigInteger A, BigInteger B) { 721 if (A == null) { 722 throw new IllegalArgumentException("null A not allowed"); 723 } 724 return A.sum(B); 725 } 726 727 728 /** 729 * BigInteger parse from String. 730 * @param s String. 731 * @return Biginteger from s. 732 */ 733 public BigInteger parse(String s) { 734 return new BigInteger(s); 735 } 736 737 738 /** 739 * BigInteger parse from Reader. 740 * @param r Reader. 741 * @return next Biginteger from r. 742 */ 743 public BigInteger parse(Reader r) { 744 return parse(StringUtil.nextString(r)); 745 } 746 747 748 /** 749 * Get the decimal representation. 750 * @return decimal. 751 */ 752 public BigDecimal getDecimal() { 753 return new BigDecimal(val); 754 } 755 756 757 /** 758 * Return a BigRational approximation of this Element. 759 * @return a BigRational approximation of this. 760 */ 761 public BigRational getRational() { 762 return new BigRational(val); 763 } 764 765 766 /** 767 * Returns the number of bits in the representation of this BigInteger, 768 * including a sign bit. For positive BigIntegers, this is equivalent to 769 * {@code (ceil(log2(this+1))+1)}.) 770 * @return number of bits in the representation of this BigInteger, 771 * including a sign bit. 772 */ 773 public long bitLength() { 774 long n = val.bitLength(); 775 //System.out.println("sign(val) = " + val.signum()); 776 if (val.signum() < 0) { 777 n++; 778 } 779 return ++n; 780 } 781 782 783 /** 784 * Returns the number of bits in the representation of a Long, including a 785 * sign bit. 786 * @param v value. 787 * @return number of bits in the representation of a Long, including a sign 788 * bit. 789 */ 790 public static long bitLength(long v) { // compare BigInteger.bitLengthForInt 791 long n = 64 - Long.numberOfLeadingZeros(v); 792 return ++n; 793 } 794 795 796 private boolean nonNegative = true; 797 798 799 /** 800 * Set the iteration algorithm to all elements. 801 */ 802 public void setAllIterator() { 803 nonNegative = false; 804 } 805 806 807 /** 808 * Set the iteration algorithm to non-negative elements. 809 */ 810 public void setNonNegativeIterator() { 811 nonNegative = true; 812 } 813 814 815 /** 816 * Get a BigInteger iterator. 817 * @return a iterator over all integers. 818 */ 819 public Iterator<BigInteger> iterator() { 820 return new BigIntegerIterator(nonNegative); 821 } 822 823} 824 825 826/** 827 * Big integer iterator. 828 * @author Heinz Kredel 829 */ 830class BigIntegerIterator implements Iterator<BigInteger> { 831 832 833 /** 834 * data structure. 835 */ 836 java.math.BigInteger curr; 837 838 839 final boolean nonNegative; 840 841 842 /** 843 * BigInteger iterator constructor. 844 */ 845 public BigIntegerIterator() { 846 this(false); 847 } 848 849 850 /** 851 * BigInteger iterator constructor. 852 * @param nn true for an iterator over non-negative longs, false for all 853 * elements iterator. 854 */ 855 public BigIntegerIterator(boolean nn) { 856 curr = java.math.BigInteger.ZERO; 857 nonNegative = nn; 858 } 859 860 861 /** 862 * Test for availability of a next element. 863 * @return true if the iteration has more elements, else false. 864 */ 865 public boolean hasNext() { 866 return true; 867 } 868 869 870 /** 871 * Get next integer. 872 * @return next integer. 873 */ 874 public synchronized BigInteger next() { 875 BigInteger i = new BigInteger(curr); 876 if (nonNegative) { 877 curr = curr.add(java.math.BigInteger.ONE); 878 } else if (curr.signum() > 0 && !nonNegative) { 879 curr = curr.negate(); 880 } else { 881 curr = curr.negate().add(java.math.BigInteger.ONE); 882 } 883 return i; 884 } 885 886 887 /** 888 * Remove an element if allowed. 889 */ 890 public void remove() { 891 throw new UnsupportedOperationException("cannot remove elements"); 892 } 893}