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