Source for java.math.BigInteger

   1: /* java.math.BigInteger -- Arbitary precision integers
   2:    Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2005, 2006  Free Software Foundation, Inc.
   3: 
   4: This file is part of GNU Classpath.
   5: 
   6: GNU Classpath is free software; you can redistribute it and/or modify
   7: it under the terms of the GNU General Public License as published by
   8: the Free Software Foundation; either version 2, or (at your option)
   9: any later version.
  10:  
  11: GNU Classpath is distributed in the hope that it will be useful, but
  12: WITHOUT ANY WARRANTY; without even the implied warranty of
  13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14: General Public License for more details.
  15: 
  16: You should have received a copy of the GNU General Public License
  17: along with GNU Classpath; see the file COPYING.  If not, write to the
  18: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  19: 02110-1301 USA.
  20: 
  21: Linking this library statically or dynamically with other modules is
  22: making a combined work based on this library.  Thus, the terms and
  23: conditions of the GNU General Public License cover the whole
  24: combination.
  25: 
  26: As a special exception, the copyright holders of this library give you
  27: permission to link this library with independent modules to produce an
  28: executable, regardless of the license terms of these independent
  29: modules, and to copy and distribute the resulting executable under
  30: terms of your choice, provided that you also meet, for each linked
  31: independent module, the terms and conditions of the license of that
  32: module.  An independent module is a module which is not derived from
  33: or based on this library.  If you modify this library, you may extend
  34: this exception to your version of the library, but you are not
  35: obligated to do so.  If you do not wish to do so, delete this
  36: exception statement from your version. */
  37: 
  38: 
  39: package java.math;
  40: 
  41: import gnu.java.math.MPN;
  42: 
  43: import java.io.IOException;
  44: import java.io.ObjectInputStream;
  45: import java.io.ObjectOutputStream;
  46: import java.util.Random;
  47: 
  48: /**
  49:  * Written using on-line Java Platform 1.2 API Specification, as well
  50:  * as "The Java Class Libraries", 2nd edition (Addison-Wesley, 1998) and
  51:  * "Applied Cryptography, Second Edition" by Bruce Schneier (Wiley, 1996).
  52:  * 
  53:  * Based primarily on IntNum.java BitOps.java by Per Bothner (per@bothner.com)
  54:  * (found in Kawa 1.6.62).
  55:  *
  56:  * @author Warren Levy (warrenl@cygnus.com)
  57:  * @date December 20, 1999.
  58:  * @status believed complete and correct.
  59:  */
  60: public class BigInteger extends Number implements Comparable<BigInteger>
  61: {
  62:   /** All integers are stored in 2's-complement form.
  63:    * If words == null, the ival is the value of this BigInteger.
  64:    * Otherwise, the first ival elements of words make the value
  65:    * of this BigInteger, stored in little-endian order, 2's-complement form. */
  66:   private transient int ival;
  67:   private transient int[] words;
  68: 
  69:   // Serialization fields.
  70:   private int bitCount = -1;
  71:   private int bitLength = -1;
  72:   private int firstNonzeroByteNum = -2;
  73:   private int lowestSetBit = -2;
  74:   private byte[] magnitude;
  75:   private int signum;
  76:   private static final long serialVersionUID = -8287574255936472291L;
  77: 
  78: 
  79:   /** We pre-allocate integers in the range minFixNum..maxFixNum. 
  80:    * Note that we must at least preallocate 0, 1, and 10.  */
  81:   private static final int minFixNum = -100;
  82:   private static final int maxFixNum = 1024;
  83:   private static final int numFixNum = maxFixNum-minFixNum+1;
  84:   private static final BigInteger[] smallFixNums = new BigInteger[numFixNum];
  85: 
  86:   static
  87:   {
  88:     for (int i = numFixNum;  --i >= 0; )
  89:       smallFixNums[i] = new BigInteger(i + minFixNum);
  90:   }
  91: 
  92:   /**
  93:    * The constant zero as a BigInteger.
  94:    * @since 1.2
  95:    */
  96:   public static final BigInteger ZERO = smallFixNums[0 - minFixNum];
  97: 
  98:   /**
  99:    * The constant one as a BigInteger.
 100:    * @since 1.2
 101:    */
 102:   public static final BigInteger ONE = smallFixNums[1 - minFixNum];
 103: 
 104:   /**
 105:    * The constant ten as a BigInteger.
 106:    * @since 1.5
 107:    */
 108:   public static final BigInteger TEN = smallFixNums[10 - minFixNum];
 109: 
 110:   /* Rounding modes: */
 111:   private static final int FLOOR = 1;
 112:   private static final int CEILING = 2;
 113:   private static final int TRUNCATE = 3;
 114:   private static final int ROUND = 4;
 115: 
 116:   /** When checking the probability of primes, it is most efficient to
 117:    * first check the factoring of small primes, so we'll use this array.
 118:    */
 119:   private static final int[] primes =
 120:     {   2,   3,   5,   7,  11,  13,  17,  19,  23,  29,  31,  37,  41,  43,
 121:        47,  53,  59,  61,  67,  71,  73,  79,  83,  89,  97, 101, 103, 107,
 122:       109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181,
 123:       191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251 };
 124: 
 125:   /** HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Table 4.4. */
 126:   private static final int[] k =
 127:       {100,150,200,250,300,350,400,500,600,800,1250, Integer.MAX_VALUE};
 128:   private static final int[] t =
 129:       { 27, 18, 15, 12,  9,  8,  7,  6,  5,  4,   3, 2};
 130: 
 131:   private BigInteger()
 132:   {
 133:   }
 134: 
 135:   /* Create a new (non-shared) BigInteger, and initialize to an int. */
 136:   private BigInteger(int value)
 137:   {
 138:     ival = value;
 139:   }
 140: 
 141:   public BigInteger(String val, int radix)
 142:   {
 143:     BigInteger result = valueOf(val, radix);
 144:     this.ival = result.ival;
 145:     this.words = result.words;
 146:   }
 147: 
 148:   public BigInteger(String val)
 149:   {
 150:     this(val, 10);
 151:   }
 152: 
 153:   /* Create a new (non-shared) BigInteger, and initialize from a byte array. */
 154:   public BigInteger(byte[] val)
 155:   {
 156:     if (val == null || val.length < 1)
 157:       throw new NumberFormatException();
 158: 
 159:     words = byteArrayToIntArray(val, val[0] < 0 ? -1 : 0);
 160:     BigInteger result = make(words, words.length);
 161:     this.ival = result.ival;
 162:     this.words = result.words;
 163:   }
 164: 
 165:   public BigInteger(int signum, byte[] magnitude)
 166:   {
 167:     if (magnitude == null || signum > 1 || signum < -1)
 168:       throw new NumberFormatException();
 169: 
 170:     if (signum == 0)
 171:       {
 172:     int i;
 173:     for (i = magnitude.length - 1; i >= 0 && magnitude[i] == 0; --i)
 174:       ;
 175:     if (i >= 0)
 176:       throw new NumberFormatException();
 177:         return;
 178:       }
 179: 
 180:     // Magnitude is always positive, so don't ever pass a sign of -1.
 181:     words = byteArrayToIntArray(magnitude, 0);
 182:     BigInteger result = make(words, words.length);
 183:     this.ival = result.ival;
 184:     this.words = result.words;
 185: 
 186:     if (signum < 0)
 187:       setNegative();
 188:   }
 189: 
 190:   public BigInteger(int numBits, Random rnd)
 191:   {
 192:     if (numBits < 0)
 193:       throw new IllegalArgumentException();
 194: 
 195:     init(numBits, rnd);
 196:   }
 197: 
 198:   private void init(int numBits, Random rnd)
 199:   {
 200:     int highbits = numBits & 31;
 201:     // minimum number of bytes to store the above number of bits
 202:     int highBitByteCount = (highbits + 7) / 8;
 203:     // number of bits to discard from the last byte
 204:     int discardedBitCount = highbits % 8;
 205:     if (discardedBitCount != 0)
 206:       discardedBitCount = 8 - discardedBitCount;
 207:     byte[] highBitBytes = new byte[highBitByteCount];
 208:     if (highbits > 0)
 209:       {
 210:         rnd.nextBytes(highBitBytes);
 211:         highbits = (highBitBytes[highBitByteCount - 1] & 0xFF) >>> discardedBitCount;
 212:         for (int i = highBitByteCount - 2; i >= 0; i--)
 213:           highbits = (highbits << 8) | (highBitBytes[i] & 0xFF);
 214:       }
 215:     int nwords = numBits / 32;
 216: 
 217:     while (highbits == 0 && nwords > 0)
 218:       {
 219:     highbits = rnd.nextInt();
 220:     --nwords;
 221:       }
 222:     if (nwords == 0 && highbits >= 0)
 223:       {
 224:     ival = highbits;
 225:       }
 226:     else
 227:       {
 228:     ival = highbits < 0 ? nwords + 2 : nwords + 1;
 229:     words = new int[ival];
 230:     words[nwords] = highbits;
 231:     while (--nwords >= 0)
 232:       words[nwords] = rnd.nextInt();
 233:       }
 234:   }
 235: 
 236:   public BigInteger(int bitLength, int certainty, Random rnd)
 237:   {
 238:     this(bitLength, rnd);
 239: 
 240:     // Keep going until we find a probable prime.
 241:     BigInteger result;
 242:     while (true)
 243:       {
 244:         // ...but first ensure that BI has bitLength bits
 245:         result = setBit(bitLength - 1);
 246:         this.ival = result.ival;
 247:         this.words = result.words;
 248:     if (isProbablePrime(certainty))
 249:       return;
 250: 
 251:     init(bitLength, rnd);
 252:       }
 253:   }
 254: 
 255:   /** 
 256:    *  Return a BigInteger that is bitLength bits long with a
 257:    *  probability < 2^-100 of being composite.
 258:    *
 259:    *  @param bitLength length in bits of resulting number
 260:    *  @param rnd random number generator to use
 261:    *  @throws ArithmeticException if bitLength < 2
 262:    *  @since 1.4
 263:    */
 264:   public static BigInteger probablePrime(int bitLength, Random rnd)
 265:   {
 266:     if (bitLength < 2)
 267:       throw new ArithmeticException();
 268: 
 269:     return new BigInteger(bitLength, 100, rnd);
 270:   }
 271: 
 272:   /** Return a (possibly-shared) BigInteger with a given long value. */
 273:   public static BigInteger valueOf(long val)
 274:   {
 275:     if (val >= minFixNum && val <= maxFixNum)
 276:       return smallFixNums[(int) val - minFixNum];
 277:     int i = (int) val;
 278:     if ((long) i == val)
 279:       return new BigInteger(i);
 280:     BigInteger result = alloc(2);
 281:     result.ival = 2;
 282:     result.words[0] = i;
 283:     result.words[1] = (int)(val >> 32);
 284:     return result;
 285:   }
 286: 
 287:   /** Make a canonicalized BigInteger from an array of words.
 288:    * The array may be reused (without copying). */
 289:   private static BigInteger make(int[] words, int len)
 290:   {
 291:     if (words == null)
 292:       return valueOf(len);
 293:     len = BigInteger.wordsNeeded(words, len);
 294:     if (len <= 1)
 295:       return len == 0 ? ZERO : valueOf(words[0]);
 296:     BigInteger num = new BigInteger();
 297:     num.words = words;
 298:     num.ival = len;
 299:     return num;
 300:   }
 301: 
 302:   /** Convert a big-endian byte array to a little-endian array of words. */
 303:   private static int[] byteArrayToIntArray(byte[] bytes, int sign)
 304:   {
 305:     // Determine number of words needed.
 306:     int[] words = new int[bytes.length/4 + 1];
 307:     int nwords = words.length;
 308: 
 309:     // Create a int out of modulo 4 high order bytes.
 310:     int bptr = 0;
 311:     int word = sign;
 312:     for (int i = bytes.length % 4; i > 0; --i, bptr++)
 313:       word = (word << 8) | (bytes[bptr] & 0xff);
 314:     words[--nwords] = word;
 315: 
 316:     // Elements remaining in byte[] are a multiple of 4.
 317:     while (nwords > 0)
 318:       words[--nwords] = bytes[bptr++] << 24 |
 319:             (bytes[bptr++] & 0xff) << 16 |
 320:             (bytes[bptr++] & 0xff) << 8 |
 321:             (bytes[bptr++] & 0xff);
 322:     return words;
 323:   }
 324: 
 325:   /** Allocate a new non-shared BigInteger.
 326:    * @param nwords number of words to allocate
 327:    */
 328:   private static BigInteger alloc(int nwords)
 329:   {
 330:     BigInteger result = new BigInteger();
 331:     if (nwords > 1)
 332:     result.words = new int[nwords];
 333:     return result;
 334:   }
 335: 
 336:   /** Change words.length to nwords.
 337:    * We allow words.length to be upto nwords+2 without reallocating.
 338:    */
 339:   private void realloc(int nwords)
 340:   {
 341:     if (nwords == 0)
 342:       {
 343:     if (words != null)
 344:       {
 345:         if (ival > 0)
 346:           ival = words[0];
 347:         words = null;
 348:       }
 349:       }
 350:     else if (words == null
 351:          || words.length < nwords
 352:          || words.length > nwords + 2)
 353:       {
 354:     int[] new_words = new int [nwords];
 355:     if (words == null)
 356:       {
 357:         new_words[0] = ival;
 358:         ival = 1;
 359:       }
 360:     else
 361:       {
 362:         if (nwords < ival)
 363:           ival = nwords;
 364:         System.arraycopy(words, 0, new_words, 0, ival);
 365:       }
 366:     words = new_words;
 367:       }
 368:   }
 369: 
 370:   private boolean isNegative()
 371:   {
 372:     return (words == null ? ival : words[ival - 1]) < 0;
 373:   }
 374: 
 375:   public int signum()
 376:   {
 377:     if (ival == 0 && words == null)
 378:       return 0;
 379:     int top = words == null ? ival : words[ival-1];
 380:     return top < 0 ? -1 : 1;
 381:   }
 382: 
 383:   private static int compareTo(BigInteger x, BigInteger y)
 384:   {
 385:     if (x.words == null && y.words == null)
 386:       return x.ival < y.ival ? -1 : x.ival > y.ival ? 1 : 0;
 387:     boolean x_negative = x.isNegative();
 388:     boolean y_negative = y.isNegative();
 389:     if (x_negative != y_negative)
 390:       return x_negative ? -1 : 1;
 391:     int x_len = x.words == null ? 1 : x.ival;
 392:     int y_len = y.words == null ? 1 : y.ival;
 393:     if (x_len != y_len)
 394:       return (x_len > y_len) != x_negative ? 1 : -1;
 395:     return MPN.cmp(x.words, y.words, x_len);
 396:   }
 397: 
 398:   /** @since 1.2 */
 399:   public int compareTo(BigInteger val)
 400:   {
 401:     return compareTo(this, val);
 402:   }
 403: 
 404:   public BigInteger min(BigInteger val)
 405:   {
 406:     return compareTo(this, val) < 0 ? this : val;
 407:   }
 408: 
 409:   public BigInteger max(BigInteger val)
 410:   {
 411:     return compareTo(this, val) > 0 ? this : val;
 412:   }
 413: 
 414:   private boolean isZero()
 415:   {
 416:     return words == null && ival == 0;
 417:   }
 418: 
 419:   private boolean isOne()
 420:   {
 421:     return words == null && ival == 1;
 422:   }
 423: 
 424:   /** Calculate how many words are significant in words[0:len-1].
 425:    * Returns the least value x such that x>0 && words[0:x-1]==words[0:len-1],
 426:    * when words is viewed as a 2's complement integer.
 427:    */
 428:   private static int wordsNeeded(int[] words, int len)
 429:   {
 430:     int i = len;
 431:     if (i > 0)
 432:       {
 433:     int word = words[--i];
 434:     if (word == -1)
 435:       {
 436:         while (i > 0 && (word = words[i - 1]) < 0)
 437:           {
 438:         i--;
 439:         if (word != -1) break;
 440:           }
 441:       }
 442:     else
 443:       {
 444:         while (word == 0 && i > 0 && (word = words[i - 1]) >= 0)  i--;
 445:       }
 446:       }
 447:     return i + 1;
 448:   }
 449: 
 450:   private BigInteger canonicalize()
 451:   {
 452:     if (words != null
 453:     && (ival = BigInteger.wordsNeeded(words, ival)) <= 1)
 454:       {
 455:     if (ival == 1)
 456:       ival = words[0];
 457:     words = null;
 458:       }
 459:     if (words == null && ival >= minFixNum && ival <= maxFixNum)
 460:       return smallFixNums[ival - minFixNum];
 461:     return this;
 462:   }
 463: 
 464:   /** Add two ints, yielding a BigInteger. */
 465:   private static BigInteger add(int x, int y)
 466:   {
 467:     return valueOf((long) x + (long) y);
 468:   }
 469: 
 470:   /** Add a BigInteger and an int, yielding a new BigInteger. */
 471:   private static BigInteger add(BigInteger x, int y)
 472:   {
 473:     if (x.words == null)
 474:       return BigInteger.add(x.ival, y);
 475:     BigInteger result = new BigInteger(0);
 476:     result.setAdd(x, y);
 477:     return result.canonicalize();
 478:   }
 479: 
 480:   /** Set this to the sum of x and y.
 481:    * OK if x==this. */
 482:   private void setAdd(BigInteger x, int y)
 483:   {
 484:     if (x.words == null)
 485:       {
 486:     set((long) x.ival + (long) y);
 487:     return;
 488:       }
 489:     int len = x.ival;
 490:     realloc(len + 1);
 491:     long carry = y;
 492:     for (int i = 0;  i < len;  i++)
 493:       {
 494:     carry += ((long) x.words[i] & 0xffffffffL);
 495:     words[i] = (int) carry;
 496:     carry >>= 32;
 497:       }
 498:     if (x.words[len - 1] < 0)
 499:       carry--;
 500:     words[len] = (int) carry;
 501:     ival = wordsNeeded(words, len + 1);
 502:   }
 503: 
 504:   /** Destructively add an int to this. */
 505:   private void setAdd(int y)
 506:   {
 507:     setAdd(this, y);
 508:   }
 509: 
 510:   /** Destructively set the value of this to a long. */
 511:   private void set(long y)
 512:   {
 513:     int i = (int) y;
 514:     if ((long) i == y)
 515:       {
 516:     ival = i;
 517:     words = null;
 518:       }
 519:     else
 520:       {
 521:     realloc(2);
 522:     words[0] = i;
 523:     words[1] = (int) (y >> 32);
 524:     ival = 2;
 525:       }
 526:   }
 527: 
 528:   /** Destructively set the value of this to the given words.
 529:   * The words array is reused, not copied. */
 530:   private void set(int[] words, int length)
 531:   {
 532:     this.ival = length;
 533:     this.words = words;
 534:   }
 535: 
 536:   /** Destructively set the value of this to that of y. */
 537:   private void set(BigInteger y)
 538:   {
 539:     if (y.words == null)
 540:       set(y.ival);
 541:     else if (this != y)
 542:       {
 543:     realloc(y.ival);
 544:     System.arraycopy(y.words, 0, words, 0, y.ival);
 545:     ival = y.ival;
 546:       }
 547:   }
 548: 
 549:   /** Add two BigIntegers, yielding their sum as another BigInteger. */
 550:   private static BigInteger add(BigInteger x, BigInteger y, int k)
 551:   {
 552:     if (x.words == null && y.words == null)
 553:       return valueOf((long) k * (long) y.ival + (long) x.ival);
 554:     if (k != 1)
 555:       {
 556:     if (k == -1)
 557:       y = BigInteger.neg(y);
 558:     else
 559:       y = BigInteger.times(y, valueOf(k));
 560:       }
 561:     if (x.words == null)
 562:       return BigInteger.add(y, x.ival);
 563:     if (y.words == null)
 564:       return BigInteger.add(x, y.ival);
 565:     // Both are big
 566:     if (y.ival > x.ival)
 567:       { // Swap so x is longer then y.
 568:     BigInteger tmp = x;  x = y;  y = tmp;
 569:       }
 570:     BigInteger result = alloc(x.ival + 1);
 571:     int i = y.ival;
 572:     long carry = MPN.add_n(result.words, x.words, y.words, i);
 573:     long y_ext = y.words[i - 1] < 0 ? 0xffffffffL : 0;
 574:     for (; i < x.ival;  i++)
 575:       {
 576:     carry += ((long) x.words[i] & 0xffffffffL) + y_ext;
 577:     result.words[i] = (int) carry;
 578:     carry >>>= 32;
 579:       }
 580:     if (x.words[i - 1] < 0)
 581:       y_ext--;
 582:     result.words[i] = (int) (carry + y_ext);
 583:     result.ival = i+1;
 584:     return result.canonicalize();
 585:   }
 586: 
 587:   public BigInteger add(BigInteger val)
 588:   {
 589:     return add(this, val, 1);
 590:   }
 591: 
 592:   public BigInteger subtract(BigInteger val)
 593:   {
 594:     return add(this, val, -1);
 595:   }
 596: 
 597:   private static BigInteger times(BigInteger x, int y)
 598:   {
 599:     if (y == 0)
 600:       return ZERO;
 601:     if (y == 1)
 602:       return x;
 603:     int[] xwords = x.words;
 604:     int xlen = x.ival;
 605:     if (xwords == null)
 606:       return valueOf((long) xlen * (long) y);
 607:     boolean negative;
 608:     BigInteger result = BigInteger.alloc(xlen + 1);
 609:     if (xwords[xlen - 1] < 0)
 610:       {
 611:     negative = true;
 612:     negate(result.words, xwords, xlen);
 613:     xwords = result.words;
 614:       }
 615:     else
 616:       negative = false;
 617:     if (y < 0)
 618:       {
 619:     negative = !negative;
 620:     y = -y;
 621:       }
 622:     result.words[xlen] = MPN.mul_1(result.words, xwords, xlen, y);
 623:     result.ival = xlen + 1;
 624:     if (negative)
 625:       result.setNegative();
 626:     return result.canonicalize();
 627:   }
 628: 
 629:   private static BigInteger times(BigInteger x, BigInteger y)
 630:   {
 631:     if (y.words == null)
 632:       return times(x, y.ival);
 633:     if (x.words == null)
 634:       return times(y, x.ival);
 635:     boolean negative = false;
 636:     int[] xwords;
 637:     int[] ywords;
 638:     int xlen = x.ival;
 639:     int ylen = y.ival;
 640:     if (x.isNegative())
 641:       {
 642:     negative = true;
 643:     xwords = new int[xlen];
 644:     negate(xwords, x.words, xlen);
 645:       }
 646:     else
 647:       {
 648:     negative = false;
 649:     xwords = x.words;
 650:       }
 651:     if (y.isNegative())
 652:       {
 653:     negative = !negative;
 654:     ywords = new int[ylen];
 655:     negate(ywords, y.words, ylen);
 656:       }
 657:     else
 658:       ywords = y.words;
 659:     // Swap if x is shorter then y.
 660:     if (xlen < ylen)
 661:       {
 662:     int[] twords = xwords;  xwords = ywords;  ywords = twords;
 663:     int tlen = xlen;  xlen = ylen;  ylen = tlen;
 664:       }
 665:     BigInteger result = BigInteger.alloc(xlen+ylen);
 666:     MPN.mul(result.words, xwords, xlen, ywords, ylen);
 667:     result.ival = xlen+ylen;
 668:     if (negative)
 669:       result.setNegative();
 670:     return result.canonicalize();
 671:   }
 672: 
 673:   public BigInteger multiply(BigInteger y)
 674:   {
 675:     return times(this, y);
 676:   }
 677: 
 678:   private static void divide(long x, long y,
 679:                  BigInteger quotient, BigInteger remainder,
 680:                  int rounding_mode)
 681:   {
 682:     boolean xNegative, yNegative;
 683:     if (x < 0)
 684:       {
 685:     xNegative = true;
 686:     if (x == Long.MIN_VALUE)
 687:       {
 688:         divide(valueOf(x), valueOf(y),
 689:            quotient, remainder, rounding_mode);
 690:         return;
 691:       }
 692:     x = -x;
 693:       }
 694:     else
 695:       xNegative = false;
 696: 
 697:     if (y < 0)
 698:       {
 699:     yNegative = true;
 700:     if (y == Long.MIN_VALUE)
 701:       {
 702:         if (rounding_mode == TRUNCATE)
 703:           { // x != Long.Min_VALUE implies abs(x) < abs(y)
 704:         if (quotient != null)
 705:           quotient.set(0);
 706:         if (remainder != null)
 707:           remainder.set(x);
 708:           }
 709:         else
 710:           divide(valueOf(x), valueOf(y),
 711:               quotient, remainder, rounding_mode);
 712:         return;
 713:       }
 714:     y = -y;
 715:       }
 716:     else
 717:       yNegative = false;
 718: 
 719:     long q = x / y;
 720:     long r = x % y;
 721:     boolean qNegative = xNegative ^ yNegative;
 722: 
 723:     boolean add_one = false;
 724:     if (r != 0)
 725:       {
 726:     switch (rounding_mode)
 727:       {
 728:       case TRUNCATE:
 729:         break;
 730:       case CEILING:
 731:       case FLOOR:
 732:         if (qNegative == (rounding_mode == FLOOR))
 733:           add_one = true;
 734:         break;
 735:       case ROUND:
 736:         add_one = r > ((y - (q & 1)) >> 1);
 737:         break;
 738:       }
 739:       }
 740:     if (quotient != null)
 741:       {
 742:     if (add_one)
 743:       q++;
 744:     if (qNegative)
 745:       q = -q;
 746:     quotient.set(q);
 747:       }
 748:     if (remainder != null)
 749:       {
 750:     // The remainder is by definition: X-Q*Y
 751:     if (add_one)
 752:       {
 753:         // Subtract the remainder from Y.
 754:         r = y - r;
 755:         // In this case, abs(Q*Y) > abs(X).
 756:         // So sign(remainder) = -sign(X).
 757:         xNegative = ! xNegative;
 758:       }
 759:     else
 760:       {
 761:         // If !add_one, then: abs(Q*Y) <= abs(X).
 762:         // So sign(remainder) = sign(X).
 763:       }
 764:     if (xNegative)
 765:       r = -r;
 766:     remainder.set(r);
 767:       }
 768:   }
 769: 
 770:   /** Divide two integers, yielding quotient and remainder.
 771:    * @param x the numerator in the division
 772:    * @param y the denominator in the division
 773:    * @param quotient is set to the quotient of the result (iff quotient!=null)
 774:    * @param remainder is set to the remainder of the result
 775:    *  (iff remainder!=null)
 776:    * @param rounding_mode one of FLOOR, CEILING, TRUNCATE, or ROUND.
 777:    */
 778:   private static void divide(BigInteger x, BigInteger y,
 779:                  BigInteger quotient, BigInteger remainder,
 780:                  int rounding_mode)
 781:   {
 782:     if ((x.words == null || x.ival <= 2)
 783:     && (y.words == null || y.ival <= 2))
 784:       {
 785:     long x_l = x.longValue();
 786:     long y_l = y.longValue();
 787:     if (x_l != Long.MIN_VALUE && y_l != Long.MIN_VALUE)
 788:       {
 789:         divide(x_l, y_l, quotient, remainder, rounding_mode);
 790:         return;
 791:       }
 792:       }
 793: 
 794:     boolean xNegative = x.isNegative();
 795:     boolean yNegative = y.isNegative();
 796:     boolean qNegative = xNegative ^ yNegative;
 797: 
 798:     int ylen = y.words == null ? 1 : y.ival;
 799:     int[] ywords = new int[ylen];
 800:     y.getAbsolute(ywords);
 801:     while (ylen > 1 && ywords[ylen - 1] == 0)  ylen--;
 802: 
 803:     int xlen = x.words == null ? 1 : x.ival;
 804:     int[] xwords = new int[xlen+2];
 805:     x.getAbsolute(xwords);
 806:     while (xlen > 1 && xwords[xlen-1] == 0)  xlen--;
 807: 
 808:     int qlen, rlen;
 809: 
 810:     int cmpval = MPN.cmp(xwords, xlen, ywords, ylen);
 811:     if (cmpval < 0)  // abs(x) < abs(y)
 812:       { // quotient = 0;  remainder = num.
 813:     int[] rwords = xwords;  xwords = ywords;  ywords = rwords;
 814:     rlen = xlen;  qlen = 1;  xwords[0] = 0;
 815:       }
 816:     else if (cmpval == 0)  // abs(x) == abs(y)
 817:       {
 818:     xwords[0] = 1;  qlen = 1;  // quotient = 1
 819:     ywords[0] = 0;  rlen = 1;  // remainder = 0;
 820:       }
 821:     else if (ylen == 1)
 822:       {
 823:     qlen = xlen;
 824:     // Need to leave room for a word of leading zeros if dividing by 1
 825:     // and the dividend has the high bit set.  It might be safe to
 826:     // increment qlen in all cases, but it certainly is only necessary
 827:     // in the following case.
 828:     if (ywords[0] == 1 && xwords[xlen-1] < 0)
 829:       qlen++;
 830:     rlen = 1;
 831:     ywords[0] = MPN.divmod_1(xwords, xwords, xlen, ywords[0]);
 832:       }
 833:     else  // abs(x) > abs(y)
 834:       {
 835:     // Normalize the denominator, i.e. make its most significant bit set by
 836:     // shifting it normalization_steps bits to the left.  Also shift the
 837:     // numerator the same number of steps (to keep the quotient the same!).
 838: 
 839:     int nshift = MPN.count_leading_zeros(ywords[ylen - 1]);
 840:     if (nshift != 0)
 841:       {
 842:         // Shift up the denominator setting the most significant bit of
 843:         // the most significant word.
 844:         MPN.lshift(ywords, 0, ywords, ylen, nshift);
 845: 
 846:         // Shift up the numerator, possibly introducing a new most
 847:         // significant word.
 848:         int x_high = MPN.lshift(xwords, 0, xwords, xlen, nshift);
 849:         xwords[xlen++] = x_high;
 850:       }
 851: 
 852:     if (xlen == ylen)
 853:       xwords[xlen++] = 0;
 854:     MPN.divide(xwords, xlen, ywords, ylen);
 855:     rlen = ylen;
 856:     MPN.rshift0 (ywords, xwords, 0, rlen, nshift);
 857: 
 858:     qlen = xlen + 1 - ylen;
 859:     if (quotient != null)
 860:       {
 861:         for (int i = 0;  i < qlen;  i++)
 862:           xwords[i] = xwords[i+ylen];
 863:       }
 864:       }
 865: 
 866:     if (ywords[rlen-1] < 0)
 867:       {
 868:         ywords[rlen] = 0;
 869:         rlen++;
 870:       }
 871: 
 872:     // Now the quotient is in xwords, and the remainder is in ywords.
 873: 
 874:     boolean add_one = false;
 875:     if (rlen > 1 || ywords[0] != 0)
 876:       { // Non-zero remainder i.e. in-exact quotient.
 877:     switch (rounding_mode)
 878:       {
 879:       case TRUNCATE:
 880:         break;
 881:       case CEILING:
 882:       case FLOOR:
 883:         if (qNegative == (rounding_mode == FLOOR))
 884:           add_one = true;
 885:         break;
 886:       case ROUND:
 887:         // int cmp = compareTo(remainder<<1, abs(y));
 888:         BigInteger tmp = remainder == null ? new BigInteger() : remainder;
 889:         tmp.set(ywords, rlen);
 890:         tmp = shift(tmp, 1);
 891:         if (yNegative)
 892:           tmp.setNegative();
 893:         int cmp = compareTo(tmp, y);
 894:         // Now cmp == compareTo(sign(y)*(remainder<<1), y)
 895:         if (yNegative)
 896:           cmp = -cmp;
 897:         add_one = (cmp == 1) || (cmp == 0 && (xwords[0]&1) != 0);
 898:       }
 899:       }
 900:     if (quotient != null)
 901:       {
 902:     quotient.set(xwords, qlen);
 903:     if (qNegative)
 904:       {
 905:         if (add_one)  // -(quotient + 1) == ~(quotient)
 906:           quotient.setInvert();
 907:         else
 908:           quotient.setNegative();
 909:       }
 910:     else if (add_one)
 911:       quotient.setAdd(1);
 912:       }
 913:     if (remainder != null)
 914:       {
 915:     // The remainder is by definition: X-Q*Y
 916:     remainder.set(ywords, rlen);
 917:     if (add_one)
 918:       {
 919:         // Subtract the remainder from Y:
 920:         // abs(R) = abs(Y) - abs(orig_rem) = -(abs(orig_rem) - abs(Y)).
 921:         BigInteger tmp;
 922:         if (y.words == null)
 923:           {
 924:         tmp = remainder;
 925:         tmp.set(yNegative ? ywords[0] + y.ival : ywords[0] - y.ival);
 926:           }
 927:         else
 928:           tmp = BigInteger.add(remainder, y, yNegative ? 1 : -1);
 929:         // Now tmp <= 0.
 930:         // In this case, abs(Q) = 1 + floor(abs(X)/abs(Y)).
 931:         // Hence, abs(Q*Y) > abs(X).
 932:         // So sign(remainder) = -sign(X).
 933:         if (xNegative)
 934:           remainder.setNegative(tmp);
 935:         else
 936:           remainder.set(tmp);
 937:       }
 938:     else
 939:       {
 940:         // If !add_one, then: abs(Q*Y) <= abs(X).
 941:         // So sign(remainder) = sign(X).
 942:         if (xNegative)
 943:           remainder.setNegative();
 944:       }
 945:       }
 946:   }
 947: 
 948:   public BigInteger divide(BigInteger val)
 949:   {
 950:     if (val.isZero())
 951:       throw new ArithmeticException("divisor is zero");
 952: 
 953:     BigInteger quot = new BigInteger();
 954:     divide(this, val, quot, null, TRUNCATE);
 955:     return quot.canonicalize();
 956:   }
 957: 
 958:   public BigInteger remainder(BigInteger val)
 959:   {
 960:     if (val.isZero())
 961:       throw new ArithmeticException("divisor is zero");
 962: 
 963:     BigInteger rem = new BigInteger();
 964:     divide(this, val, null, rem, TRUNCATE);
 965:     return rem.canonicalize();
 966:   }
 967: 
 968:   public BigInteger[] divideAndRemainder(BigInteger val)
 969:   {
 970:     if (val.isZero())
 971:       throw new ArithmeticException("divisor is zero");
 972: 
 973:     BigInteger[] result = new BigInteger[2];
 974:     result[0] = new BigInteger();
 975:     result[1] = new BigInteger();
 976:     divide(this, val, result[0], result[1], TRUNCATE);
 977:     result[0].canonicalize();
 978:     result[1].canonicalize();
 979:     return result;
 980:   }
 981: 
 982:   public BigInteger mod(BigInteger m)
 983:   {
 984:     if (m.isNegative() || m.isZero())
 985:       throw new ArithmeticException("non-positive modulus");
 986: 
 987:     BigInteger rem = new BigInteger();
 988:     divide(this, m, null, rem, FLOOR);
 989:     return rem.canonicalize();
 990:   }
 991: 
 992:   /** Calculate the integral power of a BigInteger.
 993:    * @param exponent the exponent (must be non-negative)
 994:    */
 995:   public BigInteger pow(int exponent)
 996:   {
 997:     if (exponent <= 0)
 998:       {
 999:     if (exponent == 0)
1000:       return ONE;
1001:       throw new ArithmeticException("negative exponent");
1002:       }
1003:     if (isZero())
1004:       return this;
1005:     int plen = words == null ? 1 : ival;  // Length of pow2.
1006:     int blen = ((bitLength() * exponent) >> 5) + 2 * plen;
1007:     boolean negative = isNegative() && (exponent & 1) != 0;
1008:     int[] pow2 = new int [blen];
1009:     int[] rwords = new int [blen];
1010:     int[] work = new int [blen];
1011:     getAbsolute(pow2);    // pow2 = abs(this);
1012:     int rlen = 1;
1013:     rwords[0] = 1; // rwords = 1;
1014:     for (;;)  // for (i = 0;  ; i++)
1015:       {
1016:     // pow2 == this**(2**i)
1017:     // prod = this**(sum(j=0..i-1, (exponent>>j)&1))
1018:     if ((exponent & 1) != 0)
1019:       { // r *= pow2
1020:         MPN.mul(work, pow2, plen, rwords, rlen);
1021:         int[] temp = work;  work = rwords;  rwords = temp;
1022:         rlen += plen;
1023:         while (rwords[rlen - 1] == 0)  rlen--;
1024:       }
1025:     exponent >>= 1;
1026:     if (exponent == 0)
1027:       break;
1028:     // pow2 *= pow2;
1029:     MPN.mul(work, pow2, plen, pow2, plen);
1030:     int[] temp = work;  work = pow2;  pow2 = temp;  // swap to avoid a copy
1031:     plen *= 2;
1032:     while (pow2[plen - 1] == 0)  plen--;
1033:       }
1034:     if (rwords[rlen - 1] < 0)
1035:       rlen++;
1036:     if (negative)
1037:       negate(rwords, rwords, rlen);
1038:     return BigInteger.make(rwords, rlen);
1039:   }
1040: 
1041:   private static int[] euclidInv(int a, int b, int prevDiv)
1042:   {
1043:     if (b == 0)
1044:       throw new ArithmeticException("not invertible");
1045: 
1046:     if (b == 1)
1047:     // Success:  values are indeed invertible!
1048:     // Bottom of the recursion reached; start unwinding.
1049:     return new int[] { -prevDiv, 1 };
1050: 
1051:     int[] xy = euclidInv(b, a % b, a / b);    // Recursion happens here.
1052:     a = xy[0]; // use our local copy of 'a' as a work var
1053:     xy[0] = a * -prevDiv + xy[1];
1054:     xy[1] = a;
1055:     return xy;
1056:   }
1057: 
1058:   private static void euclidInv(BigInteger a, BigInteger b,
1059:                                 BigInteger prevDiv, BigInteger[] xy)
1060:   {
1061:     if (b.isZero())
1062:       throw new ArithmeticException("not invertible");
1063: 
1064:     if (b.isOne())
1065:       {
1066:     // Success:  values are indeed invertible!
1067:     // Bottom of the recursion reached; start unwinding.
1068:     xy[0] = neg(prevDiv);
1069:         xy[1] = ONE;
1070:     return;
1071:       }
1072: 
1073:     // Recursion happens in the following conditional!
1074: 
1075:     // If a just contains an int, then use integer math for the rest.
1076:     if (a.words == null)
1077:       {
1078:         int[] xyInt = euclidInv(b.ival, a.ival % b.ival, a.ival / b.ival);
1079:     xy[0] = new BigInteger(xyInt[0]);
1080:         xy[1] = new BigInteger(xyInt[1]);
1081:       }
1082:     else
1083:       {
1084:     BigInteger rem = new BigInteger();
1085:     BigInteger quot = new BigInteger();
1086:     divide(a, b, quot, rem, FLOOR);
1087:         // quot and rem may not be in canonical form. ensure
1088:         rem.canonicalize();
1089:         quot.canonicalize();
1090:     euclidInv(b, rem, quot, xy);
1091:       }
1092: 
1093:     BigInteger t = xy[0];
1094:     xy[0] = add(xy[1], times(t, prevDiv), -1);
1095:     xy[1] = t;
1096:   }
1097: 
1098:   public BigInteger modInverse(BigInteger y)
1099:   {
1100:     if (y.isNegative() || y.isZero())
1101:       throw new ArithmeticException("non-positive modulo");
1102: 
1103:     // Degenerate cases.
1104:     if (y.isOne())
1105:       return ZERO;
1106:     if (isOne())
1107:       return ONE;
1108: 
1109:     // Use Euclid's algorithm as in gcd() but do this recursively
1110:     // rather than in a loop so we can use the intermediate results as we
1111:     // unwind from the recursion.
1112:     // Used http://www.math.nmsu.edu/~crypto/EuclideanAlgo.html as reference.
1113:     BigInteger result = new BigInteger();
1114:     boolean swapped = false;
1115: 
1116:     if (y.words == null)
1117:       {
1118:     // The result is guaranteed to be less than the modulus, y (which is
1119:     // an int), so simplify this by working with the int result of this
1120:     // modulo y.  Also, if this is negative, make it positive via modulo
1121:     // math.  Note that BigInteger.mod() must be used even if this is
1122:     // already an int as the % operator would provide a negative result if
1123:     // this is negative, BigInteger.mod() never returns negative values.
1124:         int xval = (words != null || isNegative()) ? mod(y).ival : ival;
1125:         int yval = y.ival;
1126: 
1127:     // Swap values so x > y.
1128:     if (yval > xval)
1129:       {
1130:         int tmp = xval; xval = yval; yval = tmp;
1131:         swapped = true;
1132:       }
1133:     // Normally, the result is in the 2nd element of the array, but
1134:     // if originally x < y, then x and y were swapped and the result
1135:     // is in the 1st element of the array.
1136:     result.ival =
1137:       euclidInv(yval, xval % yval, xval / yval)[swapped ? 0 : 1];
1138: 
1139:     // Result can't be negative, so make it positive by adding the
1140:     // original modulus, y.ival (not the possibly "swapped" yval).
1141:     if (result.ival < 0)
1142:       result.ival += y.ival;
1143:       }
1144:     else
1145:       {
1146:     // As above, force this to be a positive value via modulo math.
1147:     BigInteger x = isNegative() ? this.mod(y) : this;
1148: 
1149:     // Swap values so x > y.
1150:     if (x.compareTo(y) < 0)
1151:       {
1152:         result = x; x = y; y = result; // use 'result' as a work var
1153:         swapped = true;
1154:       }
1155:     // As above (for ints), result will be in the 2nd element unless
1156:     // the original x and y were swapped.
1157:     BigInteger rem = new BigInteger();
1158:     BigInteger quot = new BigInteger();
1159:     divide(x, y, quot, rem, FLOOR);
1160:         // quot and rem may not be in canonical form. ensure
1161:         rem.canonicalize();
1162:         quot.canonicalize();
1163:     BigInteger[] xy = new BigInteger[2];
1164:     euclidInv(y, rem, quot, xy);
1165:     result = swapped ? xy[0] : xy[1];
1166: 
1167:     // Result can't be negative, so make it positive by adding the
1168:     // original modulus, y (which is now x if they were swapped).
1169:     if (result.isNegative())
1170:       result = add(result, swapped ? x : y, 1);
1171:       }
1172:     
1173:     return result;
1174:   }
1175: 
1176:   public BigInteger modPow(BigInteger exponent, BigInteger m)
1177:   {
1178:     if (m.isNegative() || m.isZero())
1179:       throw new ArithmeticException("non-positive modulo");
1180: 
1181:     if (exponent.isNegative())
1182:       return modInverse(m).modPow(exponent.negate(), m);
1183:     if (exponent.isOne())
1184:       return mod(m);
1185: 
1186:     // To do this naively by first raising this to the power of exponent
1187:     // and then performing modulo m would be extremely expensive, especially
1188:     // for very large numbers.  The solution is found in Number Theory
1189:     // where a combination of partial powers and moduli can be done easily.
1190:     //
1191:     // We'll use the algorithm for Additive Chaining which can be found on
1192:     // p. 244 of "Applied Cryptography, Second Edition" by Bruce Schneier.
1193:     BigInteger s = ONE;
1194:     BigInteger t = this;
1195:     BigInteger u = exponent;
1196: 
1197:     while (!u.isZero())
1198:       {
1199:     if (u.and(ONE).isOne())
1200:       s = times(s, t).mod(m);
1201:     u = u.shiftRight(1);
1202:     t = times(t, t).mod(m);
1203:       }
1204: 
1205:     return s;
1206:   }
1207: 
1208:   /** Calculate Greatest Common Divisor for non-negative ints. */
1209:   private static int gcd(int a, int b)
1210:   {
1211:     // Euclid's algorithm, copied from libg++.
1212:     int tmp;
1213:     if (b > a)
1214:       {
1215:     tmp = a; a = b; b = tmp;
1216:       }
1217:     for(;;)
1218:       {
1219:     if (b == 0)
1220:       return a;
1221:         if (b == 1)
1222:       return b;
1223:         tmp = b;
1224:         b = a % b;
1225:         a = tmp;
1226:       }
1227:       }
1228: 
1229:   public BigInteger gcd(BigInteger y)
1230:   {
1231:     int xval = ival;
1232:     int yval = y.ival;
1233:     if (words == null)
1234:       {
1235:     if (xval == 0)
1236:       return abs(y);
1237:     if (y.words == null
1238:         && xval != Integer.MIN_VALUE && yval != Integer.MIN_VALUE)
1239:       {
1240:         if (xval < 0)
1241:           xval = -xval;
1242:         if (yval < 0)
1243:           yval = -yval;
1244:         return valueOf(gcd(xval, yval));
1245:       }
1246:     xval = 1;
1247:       }
1248:     if (y.words == null)
1249:       {
1250:     if (yval == 0)
1251:       return abs(this);
1252:     yval = 1;
1253:       }
1254:     int len = (xval > yval ? xval : yval) + 1;
1255:     int[] xwords = new int[len];
1256:     int[] ywords = new int[len];
1257:     getAbsolute(xwords);
1258:     y.getAbsolute(ywords);
1259:     len = MPN.gcd(xwords, ywords, len);
1260:     BigInteger result = new BigInteger(0);
1261:     result.ival = len;
1262:     result.words = xwords;
1263:     return result.canonicalize();
1264:   }
1265: 
1266:   /**
1267:    * <p>Returns <code>true</code> if this BigInteger is probably prime,
1268:    * <code>false</code> if it's definitely composite. If <code>certainty</code>
1269:    * is <code><= 0</code>, <code>true</code> is returned.</p>
1270:    *
1271:    * @param certainty a measure of the uncertainty that the caller is willing
1272:    * to tolerate: if the call returns <code>true</code> the probability that
1273:    * this BigInteger is prime exceeds <code>(1 - 1/2<sup>certainty</sup>)</code>.
1274:    * The execution time of this method is proportional to the value of this
1275:    * parameter.
1276:    * @return <code>true</code> if this BigInteger is probably prime,
1277:    * <code>false</code> if it's definitely composite.
1278:    */
1279:   public boolean isProbablePrime(int certainty)
1280:   {
1281:     if (certainty < 1)
1282:       return true;
1283: 
1284:     /** We'll use the Rabin-Miller algorithm for doing a probabilistic
1285:      * primality test.  It is fast, easy and has faster decreasing odds of a
1286:      * composite passing than with other tests.  This means that this
1287:      * method will actually have a probability much greater than the
1288:      * 1 - .5^certainty specified in the JCL (p. 117), but I don't think
1289:      * anyone will complain about better performance with greater certainty.
1290:      *
1291:      * The Rabin-Miller algorithm can be found on pp. 259-261 of "Applied
1292:      * Cryptography, Second Edition" by Bruce Schneier.
1293:      */
1294: 
1295:     // First rule out small prime factors
1296:     BigInteger rem = new BigInteger();
1297:     int i;
1298:     for (i = 0; i < primes.length; i++)
1299:       {
1300:     if (words == null && ival == primes[i])
1301:       return true;
1302: 
1303:         divide(this, smallFixNums[primes[i] - minFixNum], null, rem, TRUNCATE);
1304:         if (rem.canonicalize().isZero())
1305:       return false;
1306:       }
1307: 
1308:     // Now perform the Rabin-Miller test.
1309: 
1310:     // Set b to the number of times 2 evenly divides (this - 1).
1311:     // I.e. 2^b is the largest power of 2 that divides (this - 1).
1312:     BigInteger pMinus1 = add(this, -1);
1313:     int b = pMinus1.getLowestSetBit();
1314: 
1315:     // Set m such that this = 1 + 2^b * m.
1316:     BigInteger m = pMinus1.divide(valueOf(2L << b - 1));
1317: 
1318:     // The HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Note
1319:     // 4.49 (controlling the error probability) gives the number of trials
1320:     // for an error probability of 1/2**80, given the number of bits in the
1321:     // number to test.  we shall use these numbers as is if/when 'certainty'
1322:     // is less or equal to 80, and twice as much if it's greater.
1323:     int bits = this.bitLength();
1324:     for (i = 0; i < k.length; i++)
1325:       if (bits <= k[i])
1326:         break;
1327:     int trials = t[i];
1328:     if (certainty > 80)
1329:       trials *= 2;
1330:     BigInteger z;
1331:     for (int t = 0; t < trials; t++)
1332:       {
1333:         // The HAC (Handbook of Applied Cryptography), Alfred Menezes & al.
1334:         // Remark 4.28 states: "...A strategy that is sometimes employed
1335:         // is to fix the bases a to be the first few primes instead of
1336:         // choosing them at random.
1337:     z = smallFixNums[primes[t] - minFixNum].modPow(m, this);
1338:     if (z.isOne() || z.equals(pMinus1))
1339:       continue;            // Passes the test; may be prime.
1340: 
1341:     for (i = 0; i < b; )
1342:       {
1343:         if (z.isOne())
1344:           return false;
1345:         i++;
1346:         if (z.equals(pMinus1))
1347:           break;            // Passes the test; may be prime.
1348: 
1349:         z = z.modPow(valueOf(2), this);
1350:       }
1351: 
1352:     if (i == b && !z.equals(pMinus1))
1353:       return false;
1354:       }
1355:     return true;
1356:   }
1357: 
1358:   private void setInvert()
1359:   {
1360:     if (words == null)
1361:       ival = ~ival;
1362:     else
1363:       {
1364:     for (int i = ival;  --i >= 0; )
1365:       words[i] = ~words[i];
1366:       }
1367:   }
1368: 
1369:   private void setShiftLeft(BigInteger x, int count)
1370:   {
1371:     int[] xwords;
1372:     int xlen;
1373:     if (x.words == null)
1374:       {
1375:     if (count < 32)
1376:       {
1377:         set((long) x.ival << count);
1378:         return;
1379:       }
1380:     xwords = new int[1];
1381:     xwords[0] = x.ival;
1382:     xlen = 1;
1383:       }
1384:     else
1385:       {
1386:     xwords = x.words;
1387:     xlen = x.ival;
1388:       }
1389:     int word_count = count >> 5;
1390:     count &= 31;
1391:     int new_len = xlen + word_count;
1392:     if (count == 0)
1393:       {
1394:     realloc(new_len);
1395:     for (int i = xlen;  --i >= 0; )
1396:       words[i+word_count] = xwords[i];
1397:       }
1398:     else
1399:       {
1400:     new_len++;
1401:     realloc(new_len);
1402:     int shift_out = MPN.lshift(words, word_count, xwords, xlen, count);
1403:     count = 32 - count;
1404:     words[new_len-1] = (shift_out << count) >> count;  // sign-extend.
1405:       }
1406:     ival = new_len;
1407:     for (int i = word_count;  --i >= 0; )
1408:       words[i] = 0;
1409:   }
1410: 
1411:   private void setShiftRight(BigInteger x, int count)
1412:   {
1413:     if (x.words == null)
1414:       set(count < 32 ? x.ival >> count : x.ival < 0 ? -1 : 0);
1415:     else if (count == 0)
1416:       set(x);
1417:     else
1418:       {
1419:     boolean neg = x.isNegative();
1420:     int word_count = count >> 5;
1421:     count &= 31;
1422:     int d_len = x.ival - word_count;
1423:     if (d_len <= 0)
1424:       set(neg ? -1 : 0);
1425:     else
1426:       {
1427:         if (words == null || words.length < d_len)
1428:           realloc(d_len);
1429:         MPN.rshift0 (words, x.words, word_count, d_len, count);
1430:         ival = d_len;
1431:         if (neg)
1432:           words[d_len-1] |= -2 << (31 - count);
1433:       }
1434:       }
1435:   }
1436: 
1437:   private void setShift(BigInteger x, int count)
1438:   {
1439:     if (count > 0)
1440:       setShiftLeft(x, count);
1441:     else
1442:       setShiftRight(x, -count);
1443:   }
1444: 
1445:   private static BigInteger shift(BigInteger x, int count)
1446:   {
1447:     if (x.words == null)
1448:       {
1449:     if (count <= 0)
1450:       return valueOf(count > -32 ? x.ival >> (-count) : x.ival < 0 ? -1 : 0);
1451:     if (count < 32)
1452:       return valueOf((long) x.ival << count);
1453:       }
1454:     if (count == 0)
1455:       return x;
1456:     BigInteger result = new BigInteger(0);
1457:     result.setShift(x, count);
1458:     return result.canonicalize();
1459:   }
1460: 
1461:   public BigInteger shiftLeft(int n)
1462:   {
1463:     return shift(this, n);
1464:   }
1465: 
1466:   public BigInteger shiftRight(int n)
1467:   {
1468:     return shift(this, -n);
1469:   }
1470: 
1471:   private void format(int radix, StringBuffer buffer)
1472:   {
1473:     if (words == null)
1474:       buffer.append(Integer.toString(ival, radix));
1475:     else if (ival <= 2)
1476:       buffer.append(Long.toString(longValue(), radix));
1477:     else
1478:       {
1479:     boolean neg = isNegative();
1480:     int[] work;
1481:     if (neg || radix != 16)
1482:       {
1483:         work = new int[ival];
1484:         getAbsolute(work);
1485:       }
1486:     else
1487:       work = words;
1488:     int len = ival;
1489: 
1490:     if (radix == 16)
1491:       {
1492:         if (neg)
1493:           buffer.append('-');
1494:         int buf_start = buffer.length();
1495:         for (int i = len;  --i >= 0; )
1496:           {
1497:         int word = work[i];
1498:         for (int j = 8;  --j >= 0; )
1499:           {
1500:             int hex_digit = (word >> (4 * j)) & 0xF;
1501:             // Suppress leading zeros:
1502:             if (hex_digit > 0 || buffer.length() > buf_start)
1503:               buffer.append(Character.forDigit(hex_digit, 16));
1504:           }
1505:           }
1506:       }
1507:     else
1508:       {
1509:         int i = buffer.length();
1510:         for (;;)
1511:           {
1512:         int digit = MPN.divmod_1(work, work, len, radix);
1513:         buffer.append(Character.forDigit(digit, radix));
1514:         while (len > 0 && work[len-1] == 0) len--;
1515:         if (len == 0)
1516:           break;
1517:           }
1518:         if (neg)
1519:           buffer.append('-');
1520:         /* Reverse buffer. */
1521:         int j = buffer.length() - 1;
1522:         while (i < j)
1523:           {
1524:         char tmp = buffer.charAt(i);
1525:         buffer.setCharAt(i, buffer.charAt(j));
1526:         buffer.setCharAt(j, tmp);
1527:         i++;  j--;
1528:           }
1529:       }
1530:       }
1531:   }
1532: 
1533:   public String toString()
1534:   {
1535:     return toString(10);
1536:   }
1537: 
1538:   public String toString(int radix)
1539:   {
1540:     if (words == null)
1541:       return Integer.toString(ival, radix);
1542:     if (ival <= 2)
1543:       return Long.toString(longValue(), radix);
1544:     int buf_size = ival * (MPN.chars_per_word(radix) + 1);
1545:     StringBuffer buffer = new StringBuffer(buf_size);
1546:     format(radix, buffer);
1547:     return buffer.toString();
1548:   }
1549: 
1550:   public int intValue()
1551:   {
1552:     if (words == null)
1553:       return ival;
1554:     return words[0];
1555:   }
1556: 
1557:   public long longValue()
1558:   {
1559:     if (words == null)
1560:       return ival;
1561:     if (ival == 1)
1562:       return words[0];
1563:     return ((long)words[1] << 32) + ((long)words[0] & 0xffffffffL);
1564:   }
1565: 
1566:   public int hashCode()
1567:   {
1568:     // FIXME: May not match hashcode of JDK.
1569:     return words == null ? ival : (words[0] + words[ival - 1]);
1570:   }
1571: 
1572:   /* Assumes x and y are both canonicalized. */
1573:   private static boolean equals(BigInteger x, BigInteger y)
1574:   {
1575:     if (x.words == null && y.words == null)
1576:       return x.ival == y.ival;
1577:     if (x.words == null || y.words == null || x.ival != y.ival)
1578:       return false;
1579:     for (int i = x.ival; --i >= 0; )
1580:       {
1581:     if (x.words[i] != y.words[i])
1582:       return false;
1583:       }
1584:     return true;
1585:   }
1586: 
1587:   /* Assumes this and obj are both canonicalized. */
1588:   public boolean equals(Object obj)
1589:   {
1590:     if (! (obj instanceof BigInteger))
1591:       return false;
1592:     return equals(this, (BigInteger) obj);
1593:   }
1594: 
1595:   private static BigInteger valueOf(String s, int radix)
1596:        throws NumberFormatException
1597:   {
1598:     int len = s.length();
1599:     // Testing (len < MPN.chars_per_word(radix)) would be more accurate,
1600:     // but slightly more expensive, for little practical gain.
1601:     if (len <= 15 && radix <= 16)
1602:       return valueOf(Long.parseLong(s, radix));
1603: 
1604:     int i, digit;
1605:     boolean negative;
1606:     byte[] bytes;
1607:     char ch = s.charAt(0);
1608:     if (ch == '-')
1609:       {
1610:         negative = true;
1611:         i = 1;
1612:         bytes = new byte[len - 1];
1613:       }
1614:     else
1615:       {
1616:         negative = false;
1617:         i = 0;
1618:         bytes = new byte[len];
1619:       }
1620:     int byte_len = 0;
1621:     for ( ; i < len;  i++)
1622:       {
1623:         ch = s.charAt(i);
1624:         digit = Character.digit(ch, radix);
1625:         if (digit < 0)
1626:           throw new NumberFormatException();
1627:         bytes[byte_len++] = (byte) digit;
1628:       }
1629:     return valueOf(bytes, byte_len, negative, radix);
1630:   }
1631: 
1632:   private static BigInteger valueOf(byte[] digits, int byte_len,
1633:                     boolean negative, int radix)
1634:   {
1635:     int chars_per_word = MPN.chars_per_word(radix);
1636:     int[] words = new int[byte_len / chars_per_word + 1];
1637:     int size = MPN.set_str(words, digits, byte_len, radix);
1638:     if (size == 0)
1639:       return ZERO;
1640:     if (words[size-1] < 0)
1641:       words[size++] = 0;
1642:     if (negative)
1643:       negate(words, words, size);
1644:     return make(words, size);
1645:   }
1646: 
1647:   public double doubleValue()
1648:   {
1649:     if (words == null)
1650:       return (double) ival;
1651:     if (ival <= 2)
1652:       return (double) longValue();
1653:     if (isNegative())
1654:       return neg(this).roundToDouble(0, true, false);
1655:       return roundToDouble(0, false, false);
1656:   }
1657: 
1658:   public float floatValue()
1659:   {
1660:     return (float) doubleValue();
1661:   }
1662: 
1663:   /** Return true if any of the lowest n bits are one.
1664:    * (false if n is negative).  */
1665:   private boolean checkBits(int n)
1666:   {
1667:     if (n <= 0)
1668:       return false;
1669:     if (words == null)
1670:       return n > 31 || ((ival & ((1 << n) - 1)) != 0);
1671:     int i;
1672:     for (i = 0; i < (n >> 5) ; i++)
1673:       if (words[i] != 0)
1674:     return true;
1675:     return (n & 31) != 0 && (words[i] & ((1 << (n & 31)) - 1)) != 0;
1676:   }
1677: 
1678:   /** Convert a semi-processed BigInteger to double.
1679:    * Number must be non-negative.  Multiplies by a power of two, applies sign,
1680:    * and converts to double, with the usual java rounding.
1681:    * @param exp power of two, positive or negative, by which to multiply
1682:    * @param neg true if negative
1683:    * @param remainder true if the BigInteger is the result of a truncating
1684:    * division that had non-zero remainder.  To ensure proper rounding in
1685:    * this case, the BigInteger must have at least 54 bits.  */
1686:   private double roundToDouble(int exp, boolean neg, boolean remainder)
1687:   {
1688:     // Compute length.
1689:     int il = bitLength();
1690: 
1691:     // Exponent when normalized to have decimal point directly after
1692:     // leading one.  This is stored excess 1023 in the exponent bit field.
1693:     exp += il - 1;
1694: 
1695:     // Gross underflow.  If exp == -1075, we let the rounding
1696:     // computation determine whether it is minval or 0 (which are just
1697:     // 0x0000 0000 0000 0001 and 0x0000 0000 0000 0000 as bit
1698:     // patterns).
1699:     if (exp < -1075)
1700:       return neg ? -0.0 : 0.0;
1701: 
1702:     // gross overflow
1703:     if (exp > 1023)
1704:       return neg ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
1705: 
1706:     // number of bits in mantissa, including the leading one.
1707:     // 53 unless it's denormalized
1708:     int ml = (exp >= -1022 ? 53 : 53 + exp + 1022);
1709: 
1710:     // Get top ml + 1 bits.  The extra one is for rounding.
1711:     long m;
1712:     int excess_bits = il - (ml + 1);
1713:     if (excess_bits > 0)
1714:       m = ((words == null) ? ival >> excess_bits
1715:        : MPN.rshift_long(words, ival, excess_bits));
1716:     else
1717:       m = longValue() << (- excess_bits);
1718: 
1719:     // Special rounding for maxval.  If the number exceeds maxval by
1720:     // any amount, even if it's less than half a step, it overflows.
1721:     if (exp == 1023 && ((m >> 1) == (1L << 53) - 1))
1722:       {
1723:     if (remainder || checkBits(il - ml))
1724:       return neg ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
1725:     else
1726:       return neg ? - Double.MAX_VALUE : Double.MAX_VALUE;
1727:       }
1728: 
1729:     // Normal round-to-even rule: round up if the bit dropped is a one, and
1730:     // the bit above it or any of the bits below it is a one.
1731:     if ((m & 1) == 1
1732:     && ((m & 2) == 2 || remainder || checkBits(excess_bits)))
1733:       {
1734:     m += 2;
1735:     // Check if we overflowed the mantissa
1736:     if ((m & (1L << 54)) != 0)
1737:       {
1738:         exp++;
1739:         // renormalize
1740:         m >>= 1;
1741:       }
1742:     // Check if a denormalized mantissa was just rounded up to a
1743:     // normalized one.
1744:     else if (ml == 52 && (m & (1L << 53)) != 0)
1745:       exp++;
1746:       }
1747:     
1748:     // Discard the rounding bit
1749:     m >>= 1;
1750: 
1751:     long bits_sign = neg ? (1L << 63) : 0;
1752:     exp += 1023;
1753:     long bits_exp = (exp <= 0) ? 0 : ((long)exp) << 52;
1754:     long bits_mant = m & ~(1L << 52);
1755:     return Double.longBitsToDouble(bits_sign | bits_exp | bits_mant);
1756:   }
1757: 
1758:   /** Copy the abolute value of this into an array of words.
1759:    * Assumes words.length >= (this.words == null ? 1 : this.ival).
1760:    * Result is zero-extended, but need not be a valid 2's complement number.
1761:    */
1762:   private void getAbsolute(int[] words)
1763:   {
1764:     int len;
1765:     if (this.words == null)
1766:       {
1767:     len = 1;
1768:     words[0] = this.ival;
1769:       }
1770:     else
1771:       {
1772:     len = this.ival;
1773:     for (int i = len;  --i >= 0; )
1774:       words[i] = this.words[i];
1775:       }
1776:     if (words[len - 1] < 0)
1777:       negate(words, words, len);
1778:     for (int i = words.length;  --i > len; )
1779:       words[i] = 0;
1780:   }
1781: 
1782:   /** Set dest[0:len-1] to the negation of src[0:len-1].
1783:    * Return true if overflow (i.e. if src is -2**(32*len-1)).
1784:    * Ok for src==dest. */
1785:   private static boolean negate(int[] dest, int[] src, int len)
1786:   {
1787:     long carry = 1;
1788:     boolean negative = src[len-1] < 0;
1789:     for (int i = 0;  i < len;  i++)
1790:       {
1791:         carry += ((long) (~src[i]) & 0xffffffffL);
1792:         dest[i] = (int) carry;
1793:         carry >>= 32;
1794:       }
1795:     return (negative && dest[len-1] < 0);
1796:   }
1797: 
1798:   /** Destructively set this to the negative of x.
1799:    * It is OK if x==this.*/
1800:   private void setNegative(BigInteger x)
1801:   {
1802:     int len = x.ival;
1803:     if (x.words == null)
1804:       {
1805:     if (len == Integer.MIN_VALUE)
1806:       set(- (long) len);
1807:     else
1808:       set(-len);
1809:     return;
1810:       }
1811:     realloc(len + 1);
1812:     if (negate(words, x.words, len))
1813:       words[len++] = 0;
1814:     ival = len;
1815:   }
1816: 
1817:   /** Destructively negate this. */
1818:   private void setNegative()
1819:   {
1820:     setNegative(this);
1821:   }
1822: 
1823:   private static BigInteger abs(BigInteger x)
1824:   {
1825:     return x.isNegative() ? neg(x) : x;
1826:   }
1827: 
1828:   public BigInteger abs()
1829:   {
1830:     return abs(this);
1831:   }
1832: 
1833:   private static BigInteger neg(BigInteger x)
1834:   {
1835:     if (x.words == null && x.ival != Integer.MIN_VALUE)
1836:       return valueOf(- x.ival);
1837:     BigInteger result = new BigInteger(0);
1838:     result.setNegative(x);
1839:     return result.canonicalize();
1840:   }
1841: 
1842:   public BigInteger negate()
1843:   {
1844:     return neg(this);
1845:   }
1846: 
1847:   /** Calculates ceiling(log2(this < 0 ? -this : this+1))
1848:    * See Common Lisp: the Language, 2nd ed, p. 361.
1849:    */
1850:   public int bitLength()
1851:   {
1852:     if (words == null)
1853:       return MPN.intLength(ival);
1854:       return MPN.intLength(words, ival);
1855:   }
1856: 
1857:   public byte[] toByteArray()
1858:   {
1859:     // Determine number of bytes needed.  The method bitlength returns
1860:     // the size without the sign bit, so add one bit for that and then
1861:     // add 7 more to emulate the ceil function using integer math.
1862:     byte[] bytes = new byte[(bitLength() + 1 + 7) / 8];
1863:     int nbytes = bytes.length;
1864: 
1865:     int wptr = 0;
1866:     int word;
1867: 
1868:     // Deal with words array until one word or less is left to process.
1869:     // If BigInteger is an int, then it is in ival and nbytes will be <= 4.
1870:     while (nbytes > 4)
1871:       {
1872:     word = words[wptr++];
1873:     for (int i = 4; i > 0; --i, word >>= 8)
1874:           bytes[--nbytes] = (byte) word;
1875:       }
1876: 
1877:     // Deal with the last few bytes.  If BigInteger is an int, use ival.
1878:     word = (words == null) ? ival : words[wptr];
1879:     for ( ; nbytes > 0; word >>= 8)
1880:       bytes[--nbytes] = (byte) word;
1881: 
1882:     return bytes;
1883:   }
1884: 
1885:   /** Return the boolean opcode (for bitOp) for swapped operands.
1886:    * I.e. bitOp(swappedOp(op), x, y) == bitOp(op, y, x).
1887:    */
1888:   private static int swappedOp(int op)
1889:   {
1890:     return
1891:     "\000\001\004\005\002\003\006\007\010\011\014\015\012\013\016\017"
1892:     .charAt(op);
1893:   }
1894: 
1895:   /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
1896:   private static BigInteger bitOp(int op, BigInteger x, BigInteger y)
1897:   {
1898:     switch (op)
1899:       {
1900:         case 0:  return ZERO;
1901:         case 1:  return x.and(y);
1902:         case 3:  return x;
1903:         case 5:  return y;
1904:         case 15: return valueOf(-1);
1905:       }
1906:     BigInteger result = new BigInteger();
1907:     setBitOp(result, op, x, y);
1908:     return result.canonicalize();
1909:   }
1910: 
1911:   /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
1912:   private static void setBitOp(BigInteger result, int op,
1913:                    BigInteger x, BigInteger y)
1914:   {
1915:     if ((y.words != null) && (x.words == null || x.ival < y.ival))
1916:       {
1917:     BigInteger temp = x;  x = y;  y = temp;
1918:     op = swappedOp(op);
1919:       }
1920:     int xi;
1921:     int yi;
1922:     int xlen, ylen;
1923:     if (y.words == null)
1924:       {
1925:     yi = y.ival;
1926:     ylen = 1;
1927:       }
1928:     else
1929:       {
1930:     yi = y.words[0];
1931:     ylen = y.ival;
1932:       }
1933:     if (x.words == null)
1934:       {
1935:     xi = x.ival;
1936:     xlen = 1;
1937:       }
1938:     else
1939:       {
1940:     xi = x.words[0];
1941:     xlen = x.ival;
1942:       }
1943:     if (xlen > 1)
1944:       result.realloc(xlen);
1945:     int[] w = result.words;
1946:     int i = 0;
1947:     // Code for how to handle the remainder of x.
1948:     // 0:  Truncate to length of y.
1949:     // 1:  Copy rest of x.
1950:     // 2:  Invert rest of x.
1951:     int finish = 0;
1952:     int ni;
1953:     switch (op)
1954:       {
1955:       case 0:  // clr
1956:     ni = 0;
1957:     break;
1958:       case 1: // and
1959:     for (;;)
1960:       {
1961:         ni = xi & yi;
1962:         if (i+1 >= ylen) break;
1963:         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
1964:       }
1965:     if (yi < 0) finish = 1;
1966:     break;
1967:       case 2: // andc2
1968:     for (;;)
1969:       {
1970:         ni = xi & ~yi;
1971:         if (i+1 >= ylen) break;
1972:         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
1973:       }
1974:     if (yi >= 0) finish = 1;
1975:     break;
1976:       case 3:  // copy x
1977:     ni = xi;
1978:     finish = 1;  // Copy rest
1979:     break;
1980:       case 4: // andc1
1981:     for (;;)
1982:       {
1983:         ni = ~xi & yi;
1984:         if (i+1 >= ylen) break;
1985:         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
1986:       }
1987:     if (yi < 0) finish = 2;
1988:     break;
1989:       case 5: // copy y
1990:     for (;;)
1991:       {
1992:         ni = yi;
1993:         if (i+1 >= ylen) break;
1994:         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
1995:       }
1996:     break;
1997:       case 6:  // xor
1998:     for (;;)
1999:       {
2000:         ni = xi ^ yi;
2001:         if (i+1 >= ylen) break;
2002:         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
2003:       }
2004:     finish = yi < 0 ? 2 : 1;
2005:     break;
2006:       case 7:  // ior
2007:     for (;;)
2008:       {
2009:         ni = xi | yi;
2010:         if (i+1 >= ylen) break;
2011:         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
2012:       }
2013:     if (yi >= 0) finish = 1;
2014:     break;
2015:       case 8:  // nor
2016:     for (;;)
2017:       {
2018:         ni = ~(xi | yi);
2019:         if (i+1 >= ylen) break;
2020:         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
2021:       }
2022:     if (yi >= 0)  finish = 2;
2023:     break;
2024:       case 9:  // eqv [exclusive nor]
2025:     for (;;)
2026:       {
2027:         ni = ~(xi ^ yi);
2028:         if (i+1 >= ylen) break;
2029:         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
2030:       }
2031:     finish = yi >= 0 ? 2 : 1;
2032:     break;
2033:       case 10:  // c2
2034:     for (;;)
2035:       {
2036:         ni = ~yi;
2037:         if (i+1 >= ylen) break;
2038:         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
2039:       }
2040:     break;
2041:       case 11:  // orc2
2042:     for (;;)
2043:       {
2044:         ni = xi | ~yi;
2045:         if (i+1 >= ylen) break;
2046:         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
2047:       }
2048:     if (yi < 0)  finish = 1;
2049:     break;
2050:       case 12:  // c1
2051:     ni = ~xi;
2052:     finish = 2;
2053:     break;
2054:       case 13:  // orc1
2055:     for (;;)
2056:       {
2057:         ni = ~xi | yi;
2058:         if (i+1 >= ylen) break;
2059:         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
2060:       }
2061:     if (yi >= 0) finish = 2;
2062:     break;
2063:       case 14:  // nand
2064:     for (;;)
2065:       {
2066:         ni = ~(xi & yi);
2067:         if (i+1 >= ylen) break;
2068:         w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
2069:       }
2070:     if (yi < 0) finish = 2;
2071:     break;
2072:       default:
2073:       case 15:  // set
2074:     ni = -1;
2075:     break;
2076:       }
2077:     // Here i==ylen-1; w[0]..w[i-1] have the correct result;
2078:     // and ni contains the correct result for w[i+1].
2079:     if (i+1 == xlen)
2080:       finish = 0;
2081:     switch (finish)
2082:       {
2083:       case 0:
2084:     if (i == 0 && w == null)
2085:       {
2086:         result.ival = ni;
2087:         return;
2088:       }
2089:     w[i++] = ni;
2090:     break;
2091:       case 1:  w[i] = ni;  while (++i < xlen)  w[i] = x.words[i];  break;
2092:       case 2:  w[i] = ni;  while (++i < xlen)  w[i] = ~x.words[i];  break;
2093:       }
2094:     result.ival = i;
2095:   }
2096: 
2097:   /** Return the logical (bit-wise) "and" of a BigInteger and an int. */
2098:   private static BigInteger and(BigInteger x, int y)
2099:   {
2100:     if (x.words == null)
2101:       return valueOf(x.ival & y);
2102:     if (y >= 0)
2103:       return valueOf(x.words[0] & y);
2104:     int len = x.ival;
2105:     int[] words = new int[len];
2106:     words[0] = x.words[0] & y;
2107:     while (--len > 0)
2108:       words[len] = x.words[len];
2109:     return make(words, x.ival);
2110:   }
2111: 
2112:   /** Return the logical (bit-wise) "and" of two BigIntegers. */
2113:   public BigInteger and(BigInteger y)
2114:   {
2115:     if (y.words == null)
2116:       return and(this, y.ival);
2117:     else if (words == null)
2118:       return and(y, ival);
2119: 
2120:     BigInteger x = this;
2121:     if (ival < y.ival)
2122:       {
2123:         BigInteger temp = this;  x = y;  y = temp;
2124:       }
2125:     int i;
2126:     int len = y.isNegative() ? x.ival : y.ival;
2127:     int[] words = new int[len];
2128:     for (i = 0;  i < y.ival;  i++)
2129:       words[i] = x.words[i] & y.words[i];
2130:     for ( ; i < len;  i++)
2131:       words[i] = x.words[i];
2132:     return make(words, len);
2133:   }
2134: 
2135:   /** Return the logical (bit-wise) "(inclusive) or" of two BigIntegers. */
2136:   public BigInteger or(BigInteger y)
2137:   {
2138:     return bitOp(7, this, y);
2139:   }
2140: 
2141:   /** Return the logical (bit-wise) "exclusive or" of two BigIntegers. */
2142:   public BigInteger xor(BigInteger y)
2143:   {
2144:     return bitOp(6, this, y);
2145:   }
2146: 
2147:   /** Return the logical (bit-wise) negation of a BigInteger. */
2148:   public BigInteger not()
2149:   {
2150:     return bitOp(12, this, ZERO);
2151:   }
2152: 
2153:   public BigInteger andNot(BigInteger val)
2154:   {
2155:     return and(val.not());
2156:   }
2157: 
2158:   public BigInteger clearBit(int n)
2159:   {
2160:     if (n < 0)
2161:       throw new ArithmeticException();
2162: 
2163:     return and(ONE.shiftLeft(n).not());
2164:   }
2165: 
2166:   public BigInteger setBit(int n)
2167:   {
2168:     if (n < 0)
2169:       throw new ArithmeticException();
2170: 
2171:     return or(ONE.shiftLeft(n));
2172:   }
2173: 
2174:   public boolean testBit(int n)
2175:   {
2176:     if (n < 0)
2177:       throw new ArithmeticException();
2178: 
2179:     return !and(ONE.shiftLeft(n)).isZero();
2180:   }
2181: 
2182:   public BigInteger flipBit(int n)
2183:   {
2184:     if (n < 0)
2185:       throw new ArithmeticException();
2186: 
2187:     return xor(ONE.shiftLeft(n));
2188:   }
2189: 
2190:   public int getLowestSetBit()
2191:   {
2192:     if (isZero())
2193:       return -1;
2194: 
2195:     if (words == null)
2196:       return MPN.findLowestBit(ival);
2197:     else
2198:       return MPN.findLowestBit(words);
2199:   }
2200: 
2201:   // bit4count[I] is number of '1' bits in I.
2202:   private static final byte[] bit4_count = { 0, 1, 1, 2,  1, 2, 2, 3,
2203:                          1, 2, 2, 3,  2, 3, 3, 4};
2204: 
2205:   private static int bitCount(int i)
2206:   {
2207:     int count = 0;
2208:     while (i != 0)
2209:       {
2210:     count += bit4_count[i & 15];
2211:     i >>>= 4;
2212:       }
2213:     return count;
2214:   }
2215: 
2216:   private static int bitCount(int[] x, int len)
2217:   {
2218:     int count = 0;
2219:     while (--len >= 0)
2220:       count += bitCount(x[len]);
2221:     return count;
2222:   }
2223: 
2224:   /** Count one bits in a BigInteger.
2225:    * If argument is negative, count zero bits instead. */
2226:   public int bitCount()
2227:   {
2228:     int i, x_len;
2229:     int[] x_words = words;
2230:     if (x_words == null)
2231:       {
2232:     x_len = 1;
2233:     i = bitCount(ival);
2234:       }
2235:     else
2236:       {
2237:     x_len = ival;
2238:     i = bitCount(x_words, x_len);
2239:       }
2240:     return isNegative() ? x_len * 32 - i : i;
2241:   }
2242: 
2243:   private void readObject(ObjectInputStream s)
2244:     throws IOException, ClassNotFoundException
2245:   {
2246:     s.defaultReadObject();
2247:     if (magnitude.length == 0 || signum == 0)
2248:       {
2249:         this.ival = 0;
2250:         this.words = null;
2251:       }
2252:     else
2253:       {
2254:         words = byteArrayToIntArray(magnitude, signum < 0 ? -1 : 0);
2255:         BigInteger result = make(words, words.length);
2256:         this.ival = result.ival;
2257:         this.words = result.words;        
2258:       }    
2259:   }
2260: 
2261:   private void writeObject(ObjectOutputStream s)
2262:     throws IOException, ClassNotFoundException
2263:   {
2264:     signum = signum();
2265:     magnitude = signum == 0 ? new byte[0] : toByteArray();
2266:     s.defaultWriteObject();
2267:   }
2268: }