Source for java.math.BigInteger

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