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: