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