BigInteger.java

/* java.math.BigInteger -- Arbitary precision integers
   Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2005, 2006, 2007  Free Software Foundation, Inc.

This file is part of GNU Classpath.

GNU Classpath is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.

GNU Classpath is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
General Public License for more details.

You should have received a copy of the GNU General Public License
along with GNU Classpath; see the file COPYING.  If not, write to the
Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301 USA.

Linking this library statically or dynamically with other modules is
making a combined work based on this library.  Thus, the terms and
conditions of the GNU General Public License cover the whole
combination.

As a special exception, the copyright holders of this library give you
permission to link this library with independent modules to produce an
executable, regardless of the license terms of these independent
modules, and to copy and distribute the resulting executable under
terms of your choice, provided that you also meet, for each linked
independent module, the terms and conditions of the license of that
module.  An independent module is a module which is not derived from
or based on this library.  If you modify this library, you may extend
this exception to your version of the library, but you are not
obligated to do so.  If you do not wish to do so, delete this
exception statement from your version. */


package java.math;

import gnu.classpath.Configuration;

import gnu.java.lang.CPStringBuilder;
import gnu.java.math.GMP;
import gnu.java.math.MPN;

import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.Random;
import java.util.logging.Logger;

/**
 * Written using on-line Java Platform 1.2 API Specification, as well
 * as "The Java Class Libraries", 2nd edition (Addison-Wesley, 1998) and
 * "Applied Cryptography, Second Edition" by Bruce Schneier (Wiley, 1996).
 *
 * Based primarily on IntNum.java BitOps.java by Per Bothner (per@bothner.com)
 * (found in Kawa 1.6.62).
 *
 * @author Warren Levy (warrenl@cygnus.com)
 * @date December 20, 1999.
 * @status believed complete and correct.
 */
public class BigInteger extends Number implements Comparable<BigInteger>
{
  private static final Logger log = Logger.getLogger(BigInteger.class.getName());

  /** All integers are stored in 2's-complement form.
   * If words == null, the ival is the value of this BigInteger.
   * Otherwise, the first ival elements of words make the value
   * of this BigInteger, stored in little-endian order, 2's-complement form. */
  private transient int ival;
  private transient int[] words;

  // Serialization fields.
  // the first three, although not used in the code, are present for
  // compatibility with older RI versions of this class. DO NOT REMOVE.
  private int bitCount = -1;
  private int bitLength = -1;
  private int lowestSetBit = -2;
  private byte[] magnitude;
  private int signum;
  private static final long serialVersionUID = -8287574255936472291L;


  /** We pre-allocate integers in the range minFixNum..maxFixNum.
   * Note that we must at least preallocate 0, 1, and 10.  */
  private static final int minFixNum = -100;
  private static final int maxFixNum = 1024;
  private static final int numFixNum = maxFixNum-minFixNum+1;
  private static final BigInteger[] smallFixNums;

  /** The alter-ego GMP instance for this. */
  private transient GMP mpz;

  private static final boolean USING_NATIVE = Configuration.WANT_NATIVE_BIG_INTEGER
                                              && initializeLibrary();

  static
  {
    if (USING_NATIVE)
      {
        smallFixNums = null;
        ZERO = valueOf(0L);
        ONE = valueOf(1L);
        TEN = valueOf(10L);
      }
    else
      {
        smallFixNums = new BigInteger[numFixNum];
        for (int i = numFixNum;  --i >= 0; )
          smallFixNums[i] = new BigInteger(i + minFixNum);

        ZERO = smallFixNums[-minFixNum];
        ONE = smallFixNums[1 - minFixNum];
        TEN = smallFixNums[10 - minFixNum];
      }
  }

  /**
   * The constant zero as a BigInteger.
   * @since 1.2
   */
  public static final BigInteger ZERO;

  /**
   * The constant one as a BigInteger.
   * @since 1.2
   */
  public static final BigInteger ONE;

  /**
   * The constant ten as a BigInteger.
   * @since 1.5
   */
  public static final BigInteger TEN;

  /* Rounding modes: */
  private static final int FLOOR = 1;
  private static final int CEILING = 2;
  private static final int TRUNCATE = 3;
  private static final int ROUND = 4;

  /** When checking the probability of primes, it is most efficient to
   * first check the factoring of small primes, so we'll use this array.
   */
  private static final int[] primes =
    {   2,   3,   5,   7,  11,  13,  17,  19,  23,  29,  31,  37,  41,  43,
       47,  53,  59,  61,  67,  71,  73,  79,  83,  89,  97, 101, 103, 107,
      109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181,
      191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251 };

  /** HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Table 4.4. */
  private static final int[] k =
      {100,150,200,250,300,350,400,500,600,800,1250, Integer.MAX_VALUE};
  private static final int[] t =
      { 27, 18, 15, 12,  9,  8,  7,  6,  5,  4,   3, 2};

  private BigInteger()
  {
    super();

    if (USING_NATIVE)
      mpz = new GMP();
  }

  /* Create a new (non-shared) BigInteger, and initialize to an int. */
  private BigInteger(int value)
  {
    super();

    ival = value;
  }

  public BigInteger(String s, int radix)
  {
    this();

    int len = s.length();
    int i, digit;
    boolean negative;
    byte[] bytes;
    char ch = s.charAt(0);
    if (ch == '-')
      {
        negative = true;
        i = 1;
        bytes = new byte[len - 1];
      }
    else
      {
        negative = false;
        i = 0;
        bytes = new byte[len];
      }
    int byte_len = 0;
    for ( ; i < len;  i++)
      {
        ch = s.charAt(i);
        digit = Character.digit(ch, radix);
        if (digit < 0)
          throw new NumberFormatException("Invalid character at position #" + i);
        bytes[byte_len++] = (byte) digit;
      }

    if (USING_NATIVE)
      {
        bytes = null;
        if (mpz.fromString(s, radix) != 0)
          throw new NumberFormatException("String \"" + s
                                          + "\" is NOT a valid number in base "
                                          + radix);
      }
    else
      {
        BigInteger result;
        // Testing (len < MPN.chars_per_word(radix)) would be more accurate,
        // but slightly more expensive, for little practical gain.
        if (len <= 15 && radix <= 16)
          result = valueOf(Long.parseLong(s, radix));
        else
          result = valueOf(bytes, byte_len, negative, radix);

        this.ival = result.ival;
        this.words = result.words;
      }
  }

  public BigInteger(String val)
  {
    this(val, 10);
  }

  /* Create a new (non-shared) BigInteger, and initialize from a byte array. */
  public BigInteger(byte[] val)
  {
    this();

    if (val == null || val.length < 1)
      throw new NumberFormatException();

    if (USING_NATIVE)
      mpz.fromByteArray(val);
    else
      {
        words = byteArrayToIntArray(val, val[0] < 0 ? -1 : 0);
        BigInteger result = make(words, words.length);
        this.ival = result.ival;
        this.words = result.words;
      }
  }

  public BigInteger(int signum, byte[] magnitude)
  {
    this();

    if (magnitude == null || signum > 1 || signum < -1)
      throw new NumberFormatException();

    if (signum == 0)
      {
        int i;
        for (i = magnitude.length - 1; i >= 0 && magnitude[i] == 0; --i)
          ;
        if (i >= 0)
          throw new NumberFormatException();
        return;
      }

    if (USING_NATIVE)
      mpz.fromSignedMagnitude(magnitude, signum == -1);
    else
      {
        // Magnitude is always positive, so don't ever pass a sign of -1.
        words = byteArrayToIntArray(magnitude, 0);
        BigInteger result = make(words, words.length);
        this.ival = result.ival;
        this.words = result.words;

        if (signum < 0)
          setNegative();
      }
  }

  public BigInteger(int numBits, Random rnd)
  {
    this();

    if (numBits < 0)
      throw new IllegalArgumentException();

    init(numBits, rnd);
  }

  private void init(int numBits, Random rnd)
  {
    if (USING_NATIVE)
      {
        int length = (numBits + 7) / 8;
        byte[] magnitude = new byte[length];
        rnd.nextBytes(magnitude);
        int discardedBitCount = numBits % 8;
        if (discardedBitCount != 0)
          {
            discardedBitCount = 8 - discardedBitCount;
            magnitude[0] = (byte)((magnitude[0] & 0xFF) >>> discardedBitCount);
          }
        mpz.fromSignedMagnitude(magnitude, false);
        magnitude = null;
        return;
      }

    int highbits = numBits & 31;
    // minimum number of bytes to store the above number of bits
    int highBitByteCount = (highbits + 7) / 8;
    // number of bits to discard from the last byte
    int discardedBitCount = highbits % 8;
    if (discardedBitCount != 0)
      discardedBitCount = 8 - discardedBitCount;
    byte[] highBitBytes = new byte[highBitByteCount];
    if (highbits > 0)
      {
        rnd.nextBytes(highBitBytes);
        highbits = (highBitBytes[highBitByteCount - 1] & 0xFF) >>> discardedBitCount;
        for (int i = highBitByteCount - 2; i >= 0; i--)
          highbits = (highbits << 8) | (highBitBytes[i] & 0xFF);
      }
    int nwords = numBits / 32;

    while (highbits == 0 && nwords > 0)
      {
        highbits = rnd.nextInt();
        --nwords;
      }
    if (nwords == 0 && highbits >= 0)
      {
        ival = highbits;
      }
    else
      {
        ival = highbits < 0 ? nwords + 2 : nwords + 1;
        words = new int[ival];
        words[nwords] = highbits;
        while (--nwords >= 0)
          words[nwords] = rnd.nextInt();
      }
  }

  public BigInteger(int bitLength, int certainty, Random rnd)
  {
    this();

    BigInteger result = new BigInteger();
    while (true)
      {
        result.init(bitLength, rnd);
        result = result.setBit(bitLength - 1);
        if (result.isProbablePrime(certainty))
          break;
      }

    if (USING_NATIVE)
      mpz.fromBI(result.mpz);
    else
      {
        this.ival = result.ival;
        this.words = result.words;
      }
  }

  /**
   *  Return a BigInteger that is bitLength bits long with a
   *  probability < 2^-100 of being composite.
   *
   *  @param bitLength length in bits of resulting number
   *  @param rnd random number generator to use
   *  @throws ArithmeticException if bitLength < 2
   *  @since 1.4
   */
  public static BigInteger probablePrime(int bitLength, Random rnd)
  {
    if (bitLength < 2)
      throw new ArithmeticException();

    return new BigInteger(bitLength, 100, rnd);
  }

  /** Return a (possibly-shared) BigInteger with a given long value. */
  public static BigInteger valueOf(long val)
  {
    if (USING_NATIVE)
      {
        BigInteger result = new BigInteger();
        result.mpz.fromLong(val);
        return result;
      }

    if (val >= minFixNum && val <= maxFixNum)
      return smallFixNums[(int) val - minFixNum];
    int i = (int) val;
    if ((long) i == val)
      return new BigInteger(i);
    BigInteger result = alloc(2);
    result.ival = 2;
    result.words[0] = i;
    result.words[1] = (int)(val >> 32);
    return result;
  }

  /**
   * @return <code>true</code> if the GMP-based native implementation library
   *         was successfully loaded. Returns <code>false</code> otherwise.
   */
  private static boolean initializeLibrary()
  {
    boolean result;
    try
    {
      System.loadLibrary("javamath");
      GMP.natInitializeLibrary();
      result = true;
    }
    catch (Throwable x)
    {
      result = false;
      if (Configuration.DEBUG)
        {
          log.info("Unable to use native BigInteger: " + x);
          log.info("Will use a pure Java implementation instead");
        }
    }
    return result;
  }

  /** Make a canonicalized BigInteger from an array of words.
   * The array may be reused (without copying). */
  private static BigInteger make(int[] words, int len)
  {
    if (words == null)
      return valueOf(len);
    len = BigInteger.wordsNeeded(words, len);
    if (len <= 1)
      return len == 0 ? ZERO : valueOf(words[0]);
    BigInteger num = new BigInteger();
    num.words = words;
    num.ival = len;
    return num;
  }

  /** Convert a big-endian byte array to a little-endian array of words. */
  private static int[] byteArrayToIntArray(byte[] bytes, int sign)
  {
    // Determine number of words needed.
    int[] words = new int[bytes.length/4 + 1];
    int nwords = words.length;

    // Create a int out of modulo 4 high order bytes.
    int bptr = 0;
    int word = sign;
    for (int i = bytes.length % 4; i > 0; --i, bptr++)
      word = (word << 8) | (bytes[bptr] & 0xff);
    words[--nwords] = word;

    // Elements remaining in byte[] are a multiple of 4.
    while (nwords > 0)
      words[--nwords] = bytes[bptr++] << 24 |
                        (bytes[bptr++] & 0xff) << 16 |
                        (bytes[bptr++] & 0xff) << 8 |
                        (bytes[bptr++] & 0xff);
    return words;
  }

  /** Allocate a new non-shared BigInteger.
   * @param nwords number of words to allocate
   */
  private static BigInteger alloc(int nwords)
  {
    BigInteger result = new BigInteger();
    if (nwords > 1)
    result.words = new int[nwords];
    return result;
  }

  /** Change words.length to nwords.
   * We allow words.length to be upto nwords+2 without reallocating.
   */
  private void realloc(int nwords)
  {
    if (nwords == 0)
      {
        if (words != null)
          {
            if (ival > 0)
              ival = words[0];
            words = null;
          }
      }
    else if (words == null
             || words.length < nwords
             || words.length > nwords + 2)
      {
        int[] new_words = new int [nwords];
        if (words == null)
          {
            new_words[0] = ival;
            ival = 1;
          }
        else
          {
            if (nwords < ival)
              ival = nwords;
            System.arraycopy(words, 0, new_words, 0, ival);
          }
        words = new_words;
      }
  }

  private boolean isNegative()
  {
    return (words == null ? ival : words[ival - 1]) < 0;
  }

  public int signum()
  {
    if (USING_NATIVE)
      return mpz.compare(ZERO.mpz);

    if (ival == 0 && words == null)
      return 0;
    int top = words == null ? ival : words[ival-1];
    return top < 0 ? -1 : 1;
  }

  private static int compareTo(BigInteger x, BigInteger y)
  {
    if (USING_NATIVE)
      {
        int dummy = y.signum; // force NPE check
        return x.mpz.compare(y.mpz);
      }

    if (x.words == null && y.words == null)
      return x.ival < y.ival ? -1 : x.ival > y.ival ? 1 : 0;
    boolean x_negative = x.isNegative();
    boolean y_negative = y.isNegative();
    if (x_negative != y_negative)
      return x_negative ? -1 : 1;
    int x_len = x.words == null ? 1 : x.ival;
    int y_len = y.words == null ? 1 : y.ival;
    if (x_len != y_len)
      return (x_len > y_len) != x_negative ? 1 : -1;
    return MPN.cmp(x.words, y.words, x_len);
  }

  /** @since 1.2 */
  public int compareTo(BigInteger val)
  {
    return compareTo(this, val);
  }

  public BigInteger min(BigInteger val)
  {
    return compareTo(this, val) < 0 ? this : val;
  }

  public BigInteger max(BigInteger val)
  {
    return compareTo(this, val) > 0 ? this : val;
  }

  private boolean isZero()
  {
    return words == null && ival == 0;
  }

  private boolean isOne()
  {
    return words == null && ival == 1;
  }

  /** Calculate how many words are significant in words[0:len-1].
   * Returns the least value x such that x>0 && words[0:x-1]==words[0:len-1],
   * when words is viewed as a 2's complement integer.
   */
  private static int wordsNeeded(int[] words, int len)
  {
    int i = len;
    if (i > 0)
      {
        int word = words[--i];
        if (word == -1)
          {
            while (i > 0 && (word = words[i - 1]) < 0)
              {
                i--;
                if (word != -1) break;
              }
          }
        else
          {
            while (word == 0 && i > 0 && (word = words[i - 1]) >= 0)  i--;
          }
      }
    return i + 1;
  }

  private BigInteger canonicalize()
  {
    if (words != null
        && (ival = BigInteger.wordsNeeded(words, ival)) <= 1)
      {
        if (ival == 1)
          ival = words[0];
        words = null;
      }
    if (words == null && ival >= minFixNum && ival <= maxFixNum)
      return smallFixNums[ival - minFixNum];
    return this;
  }

  /** Add two ints, yielding a BigInteger. */
  private static BigInteger add(int x, int y)
  {
    return valueOf((long) x + (long) y);
  }

  /** Add a BigInteger and an int, yielding a new BigInteger. */
  private static BigInteger add(BigInteger x, int y)
  {
    if (x.words == null)
      return BigInteger.add(x.ival, y);
    BigInteger result = new BigInteger(0);
    result.setAdd(x, y);
    return result.canonicalize();
  }

  /** Set this to the sum of x and y.
   * OK if x==this. */
  private void setAdd(BigInteger x, int y)
  {
    if (x.words == null)
      {
        set((long) x.ival + (long) y);
        return;
      }
    int len = x.ival;
    realloc(len + 1);
    long carry = y;
    for (int i = 0;  i < len;  i++)
      {
        carry += ((long) x.words[i] & 0xffffffffL);
        words[i] = (int) carry;
        carry >>= 32;
      }
    if (x.words[len - 1] < 0)
      carry--;
    words[len] = (int) carry;
    ival = wordsNeeded(words, len + 1);
  }

  /** Destructively add an int to this. */
  private void setAdd(int y)
  {
    setAdd(this, y);
  }

  /** Destructively set the value of this to a long. */
  private void set(long y)
  {
    int i = (int) y;
    if ((long) i == y)
      {
        ival = i;
        words = null;
      }
    else
      {
        realloc(2);
        words[0] = i;
        words[1] = (int) (y >> 32);
        ival = 2;
      }
  }

  /** Destructively set the value of this to the given words.
  * The words array is reused, not copied. */
  private void set(int[] words, int length)
  {
    this.ival = length;
    this.words = words;
  }

  /** Destructively set the value of this to that of y. */
  private void set(BigInteger y)
  {
    if (y.words == null)
      set(y.ival);
    else if (this != y)
      {
        realloc(y.ival);
        System.arraycopy(y.words, 0, words, 0, y.ival);
        ival = y.ival;
      }
  }

  /** Add two BigIntegers, yielding their sum as another BigInteger. */
  private static BigInteger add(BigInteger x, BigInteger y, int k)
  {
    if (x.words == null && y.words == null)
      return valueOf((long) k * (long) y.ival + (long) x.ival);
    if (k != 1)
      {
        if (k == -1)
          y = BigInteger.neg(y);
        else
          y = BigInteger.times(y, valueOf(k));
      }
    if (x.words == null)
      return BigInteger.add(y, x.ival);
    if (y.words == null)
      return BigInteger.add(x, y.ival);
    // Both are big
    if (y.ival > x.ival)
      { // Swap so x is longer then y.
        BigInteger tmp = x;  x = y;  y = tmp;
      }
    BigInteger result = alloc(x.ival + 1);
    int i = y.ival;
    long carry = MPN.add_n(result.words, x.words, y.words, i);
    long y_ext = y.words[i - 1] < 0 ? 0xffffffffL : 0;
    for (; i < x.ival;  i++)
      {
        carry += ((long) x.words[i] & 0xffffffffL) + y_ext;
        result.words[i] = (int) carry;
        carry >>>= 32;
      }
    if (x.words[i - 1] < 0)
      y_ext--;
    result.words[i] = (int) (carry + y_ext);
    result.ival = i+1;
    return result.canonicalize();
  }

  public BigInteger add(BigInteger val)
  {
    if (USING_NATIVE)
      {
        int dummy = val.signum; // force NPE check
        BigInteger result = new BigInteger();
        mpz.add(val.mpz, result.mpz);
        return result;
      }

    return add(this, val, 1);
  }

  public BigInteger subtract(BigInteger val)
  {
    if (USING_NATIVE)
      {
        int dummy = val.signum; // force NPE check
        BigInteger result = new BigInteger();
        mpz.subtract(val.mpz, result.mpz);
        return result;
      }

    return add(this, val, -1);
  }

  private static BigInteger times(BigInteger x, int y)
  {
    if (y == 0)
      return ZERO;
    if (y == 1)
      return x;
    int[] xwords = x.words;
    int xlen = x.ival;
    if (xwords == null)
      return valueOf((long) xlen * (long) y);
    boolean negative;
    BigInteger result = BigInteger.alloc(xlen + 1);
    if (xwords[xlen - 1] < 0)
      {
        negative = true;
        negate(result.words, xwords, xlen);
        xwords = result.words;
      }
    else
      negative = false;
    if (y < 0)
      {
        negative = !negative;
        y = -y;
      }
    result.words[xlen] = MPN.mul_1(result.words, xwords, xlen, y);
    result.ival = xlen + 1;
    if (negative)
      result.setNegative();
    return result.canonicalize();
  }

  private static BigInteger times(BigInteger x, BigInteger y)
  {
    if (y.words == null)
      return times(x, y.ival);
    if (x.words == null)
      return times(y, x.ival);
    boolean negative = false;
    int[] xwords;
    int[] ywords;
    int xlen = x.ival;
    int ylen = y.ival;
    if (x.isNegative())
      {
        negative = true;
        xwords = new int[xlen];
        negate(xwords, x.words, xlen);
      }
    else
      {
        negative = false;
        xwords = x.words;
      }
    if (y.isNegative())
      {
        negative = !negative;
        ywords = new int[ylen];
        negate(ywords, y.words, ylen);
      }
    else
      ywords = y.words;
    // Swap if x is shorter then y.
    if (xlen < ylen)
      {
        int[] twords = xwords;  xwords = ywords;  ywords = twords;
        int tlen = xlen;  xlen = ylen;  ylen = tlen;
      }
    BigInteger result = BigInteger.alloc(xlen+ylen);
    MPN.mul(result.words, xwords, xlen, ywords, ylen);
    result.ival = xlen+ylen;
    if (negative)
      result.setNegative();
    return result.canonicalize();
  }

  public BigInteger multiply(BigInteger y)
  {
    if (USING_NATIVE)
      {
        int dummy = y.signum; // force NPE check
        BigInteger result = new BigInteger();
        mpz.multiply(y.mpz, result.mpz);
        return result;
      }

    return times(this, y);
  }

  private static void divide(long x, long y,
                             BigInteger quotient, BigInteger remainder,
                             int rounding_mode)
  {
    boolean xNegative, yNegative;
    if (x < 0)
      {
        xNegative = true;
        if (x == Long.MIN_VALUE)
          {
            divide(valueOf(x), valueOf(y),
                   quotient, remainder, rounding_mode);
            return;
          }
        x = -x;
      }
    else
      xNegative = false;

    if (y < 0)
      {
        yNegative = true;
        if (y == Long.MIN_VALUE)
          {
            if (rounding_mode == TRUNCATE)
              { // x != Long.Min_VALUE implies abs(x) < abs(y)
                if (quotient != null)
                  quotient.set(0);
                if (remainder != null)
                  remainder.set(x);
              }
            else
              divide(valueOf(x), valueOf(y),
                      quotient, remainder, rounding_mode);
            return;
          }
        y = -y;
      }
    else
      yNegative = false;

    long q = x / y;
    long r = x % y;
    boolean qNegative = xNegative ^ yNegative;

    boolean add_one = false;
    if (r != 0)
      {
        switch (rounding_mode)
          {
          case TRUNCATE:
            break;
          case CEILING:
          case FLOOR:
            if (qNegative == (rounding_mode == FLOOR))
              add_one = true;
            break;
          case ROUND:
            add_one = r > ((y - (q & 1)) >> 1);
            break;
          }
      }
    if (quotient != null)
      {
        if (add_one)
          q++;
        if (qNegative)
          q = -q;
        quotient.set(q);
      }
    if (remainder != null)
      {
        // The remainder is by definition: X-Q*Y
        if (add_one)
          {
            // Subtract the remainder from Y.
            r = y - r;
            // In this case, abs(Q*Y) > abs(X).
            // So sign(remainder) = -sign(X).
            xNegative = ! xNegative;
          }
        else
          {
            // If !add_one, then: abs(Q*Y) <= abs(X).
            // So sign(remainder) = sign(X).
          }
        if (xNegative)
          r = -r;
        remainder.set(r);
      }
  }

  /** Divide two integers, yielding quotient and remainder.
   * @param x the numerator in the division
   * @param y the denominator in the division
   * @param quotient is set to the quotient of the result (iff quotient!=null)
   * @param remainder is set to the remainder of the result
   *  (iff remainder!=null)
   * @param rounding_mode one of FLOOR, CEILING, TRUNCATE, or ROUND.
   */
  private static void divide(BigInteger x, BigInteger y,
                             BigInteger quotient, BigInteger remainder,
                             int rounding_mode)
  {
    if ((x.words == null || x.ival <= 2)
        && (y.words == null || y.ival <= 2))
      {
        long x_l = x.longValue();
        long y_l = y.longValue();
        if (x_l != Long.MIN_VALUE && y_l != Long.MIN_VALUE)
          {
            divide(x_l, y_l, quotient, remainder, rounding_mode);
            return;
          }
      }

    boolean xNegative = x.isNegative();
    boolean yNegative = y.isNegative();
    boolean qNegative = xNegative ^ yNegative;

    int ylen = y.words == null ? 1 : y.ival;
    int[] ywords = new int[ylen];
    y.getAbsolute(ywords);
    while (ylen > 1 && ywords[ylen - 1] == 0)  ylen--;

    int xlen = x.words == null ? 1 : x.ival;
    int[] xwords = new int[xlen+2];
    x.getAbsolute(xwords);
    while (xlen > 1 && xwords[xlen-1] == 0)  xlen--;

    int qlen, rlen;

    int cmpval = MPN.cmp(xwords, xlen, ywords, ylen);
    if (cmpval < 0)  // abs(x) < abs(y)
      { // quotient = 0;  remainder = num.
        int[] rwords = xwords;  xwords = ywords;  ywords = rwords;
        rlen = xlen;  qlen = 1;  xwords[0] = 0;
      }
    else if (cmpval == 0)  // abs(x) == abs(y)
      {
        xwords[0] = 1;  qlen = 1;  // quotient = 1
        ywords[0] = 0;  rlen = 1;  // remainder = 0;
      }
    else if (ylen == 1)
      {
        qlen = xlen;
        // Need to leave room for a word of leading zeros if dividing by 1
        // and the dividend has the high bit set.  It might be safe to
        // increment qlen in all cases, but it certainly is only necessary
        // in the following case.
        if (ywords[0] == 1 && xwords[xlen-1] < 0)
          qlen++;
        rlen = 1;
        ywords[0] = MPN.divmod_1(xwords, xwords, xlen, ywords[0]);
      }
    else  // abs(x) > abs(y)
      {
        // Normalize the denominator, i.e. make its most significant bit set by
        // shifting it normalization_steps bits to the left.  Also shift the
        // numerator the same number of steps (to keep the quotient the same!).

        int nshift = MPN.count_leading_zeros(ywords[ylen - 1]);
        if (nshift != 0)
          {
            // Shift up the denominator setting the most significant bit of
            // the most significant word.
            MPN.lshift(ywords, 0, ywords, ylen, nshift);

            // Shift up the numerator, possibly introducing a new most
            // significant word.
            int x_high = MPN.lshift(xwords, 0, xwords, xlen, nshift);
            xwords[xlen++] = x_high;
          }

        if (xlen == ylen)
          xwords[xlen++] = 0;
        MPN.divide(xwords, xlen, ywords, ylen);
        rlen = ylen;
        MPN.rshift0 (ywords, xwords, 0, rlen, nshift);

        qlen = xlen + 1 - ylen;
        if (quotient != null)
          {
            for (int i = 0;  i < qlen;  i++)
              xwords[i] = xwords[i+ylen];
          }
      }

    if (ywords[rlen-1] < 0)
      {
        ywords[rlen] = 0;
        rlen++;
      }

    // Now the quotient is in xwords, and the remainder is in ywords.

    boolean add_one = false;
    if (rlen > 1 || ywords[0] != 0)
      { // Non-zero remainder i.e. in-exact quotient.
        switch (rounding_mode)
          {
          case TRUNCATE:
            break;
          case CEILING:
          case FLOOR:
            if (qNegative == (rounding_mode == FLOOR))
              add_one = true;
            break;
          case ROUND:
            // int cmp = compareTo(remainder<<1, abs(y));
            BigInteger tmp = remainder == null ? new BigInteger() : remainder;
            tmp.set(ywords, rlen);
            tmp = shift(tmp, 1);
            if (yNegative)
              tmp.setNegative();
            int cmp = compareTo(tmp, y);
            // Now cmp == compareTo(sign(y)*(remainder<<1), y)
            if (yNegative)
              cmp = -cmp;
            add_one = (cmp == 1) || (cmp == 0 && (xwords[0]&1) != 0);
          }
      }
    if (quotient != null)
      {
        quotient.set(xwords, qlen);
        if (qNegative)
          {
            if (add_one)  // -(quotient + 1) == ~(quotient)
              quotient.setInvert();
            else
              quotient.setNegative();
          }
        else if (add_one)
          quotient.setAdd(1);
      }
    if (remainder != null)
      {
        // The remainder is by definition: X-Q*Y
        remainder.set(ywords, rlen);
        if (add_one)
          {
            // Subtract the remainder from Y:
            // abs(R) = abs(Y) - abs(orig_rem) = -(abs(orig_rem) - abs(Y)).
            BigInteger tmp;
            if (y.words == null)
              {
                tmp = remainder;
                tmp.set(yNegative ? ywords[0] + y.ival : ywords[0] - y.ival);
              }
            else
              tmp = BigInteger.add(remainder, y, yNegative ? 1 : -1);
            // Now tmp <= 0.
            // In this case, abs(Q) = 1 + floor(abs(X)/abs(Y)).
            // Hence, abs(Q*Y) > abs(X).
            // So sign(remainder) = -sign(X).
            if (xNegative)
              remainder.setNegative(tmp);
            else
              remainder.set(tmp);
          }
        else
          {
            // If !add_one, then: abs(Q*Y) <= abs(X).
            // So sign(remainder) = sign(X).
            if (xNegative)
              remainder.setNegative();
          }
      }
  }

  public BigInteger divide(BigInteger val)
  {
    if (USING_NATIVE)
      {
        if (val.compareTo(ZERO) == 0)
          throw new ArithmeticException("divisor is zero");

        BigInteger result = new BigInteger();
        mpz.quotient(val.mpz, result.mpz);
        return result;
      }

    if (val.isZero())
      throw new ArithmeticException("divisor is zero");

    BigInteger quot = new BigInteger();
    divide(this, val, quot, null, TRUNCATE);
    return quot.canonicalize();
  }

  public BigInteger remainder(BigInteger val)
  {
    if (USING_NATIVE)
      {
        if (val.compareTo(ZERO) == 0)
          throw new ArithmeticException("divisor is zero");

        BigInteger result = new BigInteger();
        mpz.remainder(val.mpz, result.mpz);
        return result;
      }

    if (val.isZero())
      throw new ArithmeticException("divisor is zero");

    BigInteger rem = new BigInteger();
    divide(this, val, null, rem, TRUNCATE);
    return rem.canonicalize();
  }

  public BigInteger[] divideAndRemainder(BigInteger val)
  {
    if (USING_NATIVE)
      {
        if (val.compareTo(ZERO) == 0)
          throw new ArithmeticException("divisor is zero");

        BigInteger q = new BigInteger();
        BigInteger r = new BigInteger();
        mpz.quotientAndRemainder(val.mpz, q.mpz, r.mpz);
        return new BigInteger[] { q, r };
      }

    if (val.isZero())
      throw new ArithmeticException("divisor is zero");

    BigInteger[] result = new BigInteger[2];
    result[0] = new BigInteger();
    result[1] = new BigInteger();
    divide(this, val, result[0], result[1], TRUNCATE);
    result[0].canonicalize();
    result[1].canonicalize();
    return result;
  }

  public BigInteger mod(BigInteger m)
  {
    if (USING_NATIVE)
      {
        int dummy = m.signum; // force NPE check
        if (m.compareTo(ZERO) < 1)
          throw new ArithmeticException("non-positive modulus");

        BigInteger result = new BigInteger();
        mpz.modulo(m.mpz, result.mpz);
        return result;
      }

    if (m.isNegative() || m.isZero())
      throw new ArithmeticException("non-positive modulus");

    BigInteger rem = new BigInteger();
    divide(this, m, null, rem, FLOOR);
    return rem.canonicalize();
  }

  /** Calculate the integral power of a BigInteger.
   * @param exponent the exponent (must be non-negative)
   */
  public BigInteger pow(int exponent)
  {
    if (exponent <= 0)
      {
        if (exponent == 0)
          return ONE;
          throw new ArithmeticException("negative exponent");
      }

    if (USING_NATIVE)
      {
        BigInteger result = new BigInteger();
        mpz.pow(exponent, result.mpz);
        return result;
      }

    if (isZero())
      return this;
    int plen = words == null ? 1 : ival;  // Length of pow2.
    int blen = ((bitLength() * exponent) >> 5) + 2 * plen;
    boolean negative = isNegative() && (exponent & 1) != 0;
    int[] pow2 = new int [blen];
    int[] rwords = new int [blen];
    int[] work = new int [blen];
    getAbsolute(pow2);  // pow2 = abs(this);
    int rlen = 1;
    rwords[0] = 1; // rwords = 1;
    for (;;)  // for (i = 0;  ; i++)
      {
        // pow2 == this**(2**i)
        // prod = this**(sum(j=0..i-1, (exponent>>j)&1))
        if ((exponent & 1) != 0)
          { // r *= pow2
            MPN.mul(work, pow2, plen, rwords, rlen);
            int[] temp = work;  work = rwords;  rwords = temp;
            rlen += plen;
            while (rwords[rlen - 1] == 0)  rlen--;
          }
        exponent >>= 1;
        if (exponent == 0)
          break;
        // pow2 *= pow2;
        MPN.mul(work, pow2, plen, pow2, plen);
        int[] temp = work;  work = pow2;  pow2 = temp;  // swap to avoid a copy
        plen *= 2;
        while (pow2[plen - 1] == 0)  plen--;
      }
    if (rwords[rlen - 1] < 0)
      rlen++;
    if (negative)
      negate(rwords, rwords, rlen);
    return BigInteger.make(rwords, rlen);
  }

  private static int[] euclidInv(int a, int b, int prevDiv)
  {
    if (b == 0)
      throw new ArithmeticException("not invertible");

    if (b == 1)
        // Success:  values are indeed invertible!
        // Bottom of the recursion reached; start unwinding.
        return new int[] { -prevDiv, 1 };

    int[] xy = euclidInv(b, a % b, a / b);      // Recursion happens here.
    a = xy[0]; // use our local copy of 'a' as a work var
    xy[0] = a * -prevDiv + xy[1];
    xy[1] = a;
    return xy;
  }

  private static void euclidInv(BigInteger a, BigInteger b,
                                BigInteger prevDiv, BigInteger[] xy)
  {
    if (b.isZero())
      throw new ArithmeticException("not invertible");

    if (b.isOne())
      {
        // Success:  values are indeed invertible!
        // Bottom of the recursion reached; start unwinding.
        xy[0] = neg(prevDiv);
        xy[1] = ONE;
        return;
      }

    // Recursion happens in the following conditional!

    // If a just contains an int, then use integer math for the rest.
    if (a.words == null)
      {
        int[] xyInt = euclidInv(b.ival, a.ival % b.ival, a.ival / b.ival);
        xy[0] = new BigInteger(xyInt[0]);
        xy[1] = new BigInteger(xyInt[1]);
      }
    else
      {
        BigInteger rem = new BigInteger();
        BigInteger quot = new BigInteger();
        divide(a, b, quot, rem, FLOOR);
        // quot and rem may not be in canonical form. ensure
        rem.canonicalize();
        quot.canonicalize();
        euclidInv(b, rem, quot, xy);
      }

    BigInteger t = xy[0];
    xy[0] = add(xy[1], times(t, prevDiv), -1);
    xy[1] = t;
  }

  public BigInteger modInverse(BigInteger y)
  {
    if (USING_NATIVE)
      {
        int dummy = y.signum; // force NPE check
        if (mpz.compare(ZERO.mpz) < 1)
          throw new ArithmeticException("non-positive modulo");

        BigInteger result = new BigInteger();
        mpz.modInverse(y.mpz, result.mpz);
        return result;
      }

    if (y.isNegative() || y.isZero())
      throw new ArithmeticException("non-positive modulo");

    // Degenerate cases.
    if (y.isOne())
      return ZERO;
    if (isOne())
      return ONE;

    // Use Euclid's algorithm as in gcd() but do this recursively
    // rather than in a loop so we can use the intermediate results as we
    // unwind from the recursion.
    // Used http://www.math.nmsu.edu/~crypto/EuclideanAlgo.html as reference.
    BigInteger result = new BigInteger();
    boolean swapped = false;

    if (y.words == null)
      {
        // The result is guaranteed to be less than the modulus, y (which is
        // an int), so simplify this by working with the int result of this
        // modulo y.  Also, if this is negative, make it positive via modulo
        // math.  Note that BigInteger.mod() must be used even if this is
        // already an int as the % operator would provide a negative result if
        // this is negative, BigInteger.mod() never returns negative values.
        int xval = (words != null || isNegative()) ? mod(y).ival : ival;
        int yval = y.ival;

        // Swap values so x > y.
        if (yval > xval)
          {
            int tmp = xval; xval = yval; yval = tmp;
            swapped = true;
          }
        // Normally, the result is in the 2nd element of the array, but
        // if originally x < y, then x and y were swapped and the result
        // is in the 1st element of the array.
        result.ival =
          euclidInv(yval, xval % yval, xval / yval)[swapped ? 0 : 1];

        // Result can't be negative, so make it positive by adding the
        // original modulus, y.ival (not the possibly "swapped" yval).
        if (result.ival < 0)
          result.ival += y.ival;
      }
    else
      {
        // As above, force this to be a positive value via modulo math.
        BigInteger x = isNegative() ? this.mod(y) : this;

        // Swap values so x > y.
        if (x.compareTo(y) < 0)
          {
            result = x; x = y; y = result; // use 'result' as a work var
            swapped = true;
          }
        // As above (for ints), result will be in the 2nd element unless
        // the original x and y were swapped.
        BigInteger rem = new BigInteger();
        BigInteger quot = new BigInteger();
        divide(x, y, quot, rem, FLOOR);
        // quot and rem may not be in canonical form. ensure
        rem.canonicalize();
        quot.canonicalize();
        BigInteger[] xy = new BigInteger[2];
        euclidInv(y, rem, quot, xy);
        result = swapped ? xy[0] : xy[1];

        // Result can't be negative, so make it positive by adding the
        // original modulus, y (which is now x if they were swapped).
        if (result.isNegative())
          result = add(result, swapped ? x : y, 1);
      }

    return result;
  }

  public BigInteger modPow(BigInteger exponent, BigInteger m)
  {
    if (USING_NATIVE)
      {
        int dummy = exponent.signum; // force NPE check
        if (m.mpz.compare(ZERO.mpz) < 1)
          throw new ArithmeticException("non-positive modulo");

        BigInteger result = new BigInteger();
        mpz.modPow(exponent.mpz, m.mpz, result.mpz);
        return result;
      }

    if (m.isNegative() || m.isZero())
      throw new ArithmeticException("non-positive modulo");

    if (exponent.isNegative())
      return modInverse(m).modPow(exponent.negate(), m);
    if (exponent.isOne())
      return mod(m);

    // To do this naively by first raising this to the power of exponent
    // and then performing modulo m would be extremely expensive, especially
    // for very large numbers.  The solution is found in Number Theory
    // where a combination of partial powers and moduli can be done easily.
    //
    // We'll use the algorithm for Additive Chaining which can be found on
    // p. 244 of "Applied Cryptography, Second Edition" by Bruce Schneier.
    BigInteger s = ONE;
    BigInteger t = this;
    BigInteger u = exponent;

    while (!u.isZero())
      {
        if (u.and(ONE).isOne())
          s = times(s, t).mod(m);
        u = u.shiftRight(1);
        t = times(t, t).mod(m);
      }

    return s;
  }

  /** Calculate Greatest Common Divisor for non-negative ints. */
  private static int gcd(int a, int b)
  {
    // Euclid's algorithm, copied from libg++.
    int tmp;
    if (b > a)
      {
        tmp = a; a = b; b = tmp;
      }
    for(;;)
      {
        if (b == 0)
          return a;
        if (b == 1)
          return b;
        tmp = b;
            b = a % b;
            a = tmp;
          }
      }

  public BigInteger gcd(BigInteger y)
  {
    if (USING_NATIVE)
      {
        int dummy = y.signum; // force NPE check
        BigInteger result = new BigInteger();
        mpz.gcd(y.mpz, result.mpz);
        return result;
      }

    int xval = ival;
    int yval = y.ival;
    if (words == null)
      {
        if (xval == 0)
          return abs(y);
        if (y.words == null
            && xval != Integer.MIN_VALUE && yval != Integer.MIN_VALUE)
          {
            if (xval < 0)
              xval = -xval;
            if (yval < 0)
              yval = -yval;
            return valueOf(gcd(xval, yval));
          }
        xval = 1;
      }
    if (y.words == null)
      {
        if (yval == 0)
          return abs(this);
        yval = 1;
      }
    int len = (xval > yval ? xval : yval) + 1;
    int[] xwords = new int[len];
    int[] ywords = new int[len];
    getAbsolute(xwords);
    y.getAbsolute(ywords);
    len = MPN.gcd(xwords, ywords, len);
    BigInteger result = new BigInteger(0);
    result.ival = len;
    result.words = xwords;
    return result.canonicalize();
  }

  /**
   * <p>Returns <code>true</code> if this BigInteger is probably prime,
   * <code>false</code> if it's definitely composite. If <code>certainty</code>
   * is <code><= 0</code>, <code>true</code> is returned.</p>
   *
   * @param certainty a measure of the uncertainty that the caller is willing
   * to tolerate: if the call returns <code>true</code> the probability that
   * this BigInteger is prime exceeds <code>(1 - 1/2<sup>certainty</sup>)</code>.
   * The execution time of this method is proportional to the value of this
   * parameter.
   * @return <code>true</code> if this BigInteger is probably prime,
   * <code>false</code> if it's definitely composite.
   */
  public boolean isProbablePrime(int certainty)
  {
    if (certainty < 1)
      return true;

    if (USING_NATIVE)
      return mpz.testPrimality(certainty) != 0;

    /** We'll use the Rabin-Miller algorithm for doing a probabilistic
     * primality test.  It is fast, easy and has faster decreasing odds of a
     * composite passing than with other tests.  This means that this
     * method will actually have a probability much greater than the
     * 1 - .5^certainty specified in the JCL (p. 117), but I don't think
     * anyone will complain about better performance with greater certainty.
     *
     * The Rabin-Miller algorithm can be found on pp. 259-261 of "Applied
     * Cryptography, Second Edition" by Bruce Schneier.
     */

    // First rule out small prime factors
    BigInteger rem = new BigInteger();
    int i;
    for (i = 0; i < primes.length; i++)
      {
        if (words == null && ival == primes[i])
          return true;

        divide(this, smallFixNums[primes[i] - minFixNum], null, rem, TRUNCATE);
        if (rem.canonicalize().isZero())
          return false;
      }

    // Now perform the Rabin-Miller test.

    // Set b to the number of times 2 evenly divides (this - 1).
    // I.e. 2^b is the largest power of 2 that divides (this - 1).
    BigInteger pMinus1 = add(this, -1);
    int b = pMinus1.getLowestSetBit();

    // Set m such that this = 1 + 2^b * m.
    BigInteger m = pMinus1.divide(valueOf(2L).pow(b));

    // The HAC (Handbook of Applied Cryptography), Alfred Menezes & al. Note
    // 4.49 (controlling the error probability) gives the number of trials
    // for an error probability of 1/2**80, given the number of bits in the
    // number to test.  we shall use these numbers as is if/when 'certainty'
    // is less or equal to 80, and twice as much if it's greater.
    int bits = this.bitLength();
    for (i = 0; i < k.length; i++)
      if (bits <= k[i])
        break;
    int trials = t[i];
    if (certainty > 80)
      trials *= 2;
    BigInteger z;
    for (int t = 0; t < trials; t++)
      {
        // The HAC (Handbook of Applied Cryptography), Alfred Menezes & al.
        // Remark 4.28 states: "...A strategy that is sometimes employed
        // is to fix the bases a to be the first few primes instead of
        // choosing them at random.
        z = smallFixNums[primes[t] - minFixNum].modPow(m, this);
        if (z.isOne() || z.equals(pMinus1))
          continue;                     // Passes the test; may be prime.

        for (i = 0; i < b; )
          {
            if (z.isOne())
              return false;
            i++;
            if (z.equals(pMinus1))
              break;                    // Passes the test; may be prime.

            z = z.modPow(valueOf(2), this);
          }

        if (i == b && !z.equals(pMinus1))
          return false;
      }
    return true;
  }

  private void setInvert()
  {
    if (words == null)
      ival = ~ival;
    else
      {
        for (int i = ival;  --i >= 0; )
          words[i] = ~words[i];
      }
  }

  private void setShiftLeft(BigInteger x, int count)
  {
    int[] xwords;
    int xlen;
    if (x.words == null)
      {
        if (count < 32)
          {
            set((long) x.ival << count);
            return;
          }
        xwords = new int[1];
        xwords[0] = x.ival;
        xlen = 1;
      }
    else
      {
        xwords = x.words;
        xlen = x.ival;
      }
    int word_count = count >> 5;
    count &= 31;
    int new_len = xlen + word_count;
    if (count == 0)
      {
        realloc(new_len);
        for (int i = xlen;  --i >= 0; )
          words[i+word_count] = xwords[i];
      }
    else
      {
        new_len++;
        realloc(new_len);
        int shift_out = MPN.lshift(words, word_count, xwords, xlen, count);
        count = 32 - count;
        words[new_len-1] = (shift_out << count) >> count;  // sign-extend.
      }
    ival = new_len;
    for (int i = word_count;  --i >= 0; )
      words[i] = 0;
  }

  private void setShiftRight(BigInteger x, int count)
  {
    if (x.words == null)
      set(count < 32 ? x.ival >> count : x.ival < 0 ? -1 : 0);
    else if (count == 0)
      set(x);
    else
      {
        boolean neg = x.isNegative();
        int word_count = count >> 5;
        count &= 31;
        int d_len = x.ival - word_count;
        if (d_len <= 0)
          set(neg ? -1 : 0);
        else
          {
            if (words == null || words.length < d_len)
              realloc(d_len);
            MPN.rshift0 (words, x.words, word_count, d_len, count);
            ival = d_len;
            if (neg)
              words[d_len-1] |= -2 << (31 - count);
          }
      }
  }

  private void setShift(BigInteger x, int count)
  {
    if (count > 0)
      setShiftLeft(x, count);
    else
      setShiftRight(x, -count);
  }

  private static BigInteger shift(BigInteger x, int count)
  {
    if (x.words == null)
      {
        if (count <= 0)
          return valueOf(count > -32 ? x.ival >> (-count) : x.ival < 0 ? -1 : 0);
        if (count < 32)
          return valueOf((long) x.ival << count);
      }
    if (count == 0)
      return x;
    BigInteger result = new BigInteger(0);
    result.setShift(x, count);
    return result.canonicalize();
  }

  public BigInteger shiftLeft(int n)
  {
    if (n == 0)
      return this;

    if (USING_NATIVE)
      {
        BigInteger result = new BigInteger();
        if (n < 0)
          mpz.shiftRight(-n, result.mpz);
        else
          mpz.shiftLeft(n, result.mpz);
        return result;
      }

    return shift(this, n);
  }

  public BigInteger shiftRight(int n)
  {
    if (n == 0)
      return this;

    if (USING_NATIVE)
      {
        BigInteger result = new BigInteger();
        if (n < 0)
          mpz.shiftLeft(-n, result.mpz);
        else
          mpz.shiftRight(n, result.mpz);
        return result;
      }

    return shift(this, -n);
  }

  private void format(int radix, CPStringBuilder buffer)
  {
    if (words == null)
      buffer.append(Integer.toString(ival, radix));
    else if (ival <= 2)
      buffer.append(Long.toString(longValue(), radix));
    else
      {
        boolean neg = isNegative();
        int[] work;
        if (neg || radix != 16)
          {
            work = new int[ival];
            getAbsolute(work);
          }
        else
          work = words;
        int len = ival;

        if (radix == 16)
          {
            if (neg)
              buffer.append('-');
            int buf_start = buffer.length();
            for (int i = len;  --i >= 0; )
              {
                int word = work[i];
                for (int j = 8;  --j >= 0; )
                  {
                    int hex_digit = (word >> (4 * j)) & 0xF;
                    // Suppress leading zeros:
                    if (hex_digit > 0 || buffer.length() > buf_start)
                      buffer.append(Character.forDigit(hex_digit, 16));
                  }
              }
          }
        else
          {
            int i = buffer.length();
            for (;;)
              {
                int digit = MPN.divmod_1(work, work, len, radix);
                buffer.append(Character.forDigit(digit, radix));
                while (len > 0 && work[len-1] == 0) len--;
                if (len == 0)
                  break;
              }
            if (neg)
              buffer.append('-');
            /* Reverse buffer. */
            int j = buffer.length() - 1;
            while (i < j)
              {
                char tmp = buffer.charAt(i);
                buffer.setCharAt(i, buffer.charAt(j));
                buffer.setCharAt(j, tmp);
                i++;  j--;
              }
          }
      }
  }

  public String toString()
  {
    return toString(10);
  }

  public String toString(int radix)
  {
    if (USING_NATIVE)
      return mpz.toString(radix);

    if (words == null)
      return Integer.toString(ival, radix);
    if (ival <= 2)
      return Long.toString(longValue(), radix);
    int buf_size = ival * (MPN.chars_per_word(radix) + 1);
    CPStringBuilder buffer = new CPStringBuilder(buf_size);
    format(radix, buffer);
    return buffer.toString();
  }

  public int intValue()
  {
    if (USING_NATIVE)
      {
        int result = mpz.absIntValue();
        return mpz.compare(ZERO.mpz) < 0 ? - result : result;
      }

    if (words == null)
      return ival;
    return words[0];
  }

  public long longValue()
  {
    if (USING_NATIVE)
      {
        long result;
        result = (abs().shiftRight(32)).mpz.absIntValue();
        result <<= 32;
        result |= mpz.absIntValue() & 0xFFFFFFFFL;
        return this.compareTo(ZERO) < 0 ? - result : result;
      }

    if (words == null)
      return ival;
    if (ival == 1)
      return words[0];
    return ((long)words[1] << 32) + ((long)words[0] & 0xffffffffL);
  }

  public int hashCode()
  {
    // FIXME: May not match hashcode of JDK.
    if (USING_NATIVE)
      {
        // TODO: profile to decide whether to make it native
        byte[] bytes = this.toByteArray();
        int result = 0;
        for (int i = 0; i < bytes.length; i++)
          result ^= (bytes[i] & 0xFF) << (8 * (i % 4));
        return result;
      }

    return words == null ? ival : (words[0] + words[ival - 1]);
  }

  /* Assumes x and y are both canonicalized. */
  private static boolean equals(BigInteger x, BigInteger y)
  {
    if (USING_NATIVE)
      return x.mpz.compare(y.mpz) == 0;

    if (x.words == null && y.words == null)
      return x.ival == y.ival;
    if (x.words == null || y.words == null || x.ival != y.ival)
      return false;
    for (int i = x.ival; --i >= 0; )
      {
        if (x.words[i] != y.words[i])
          return false;
      }
    return true;
  }

  /* Assumes this and obj are both canonicalized. */
  public boolean equals(Object obj)
  {
    if (! (obj instanceof BigInteger))
      return false;
    return equals(this, (BigInteger) obj);
  }

  private static BigInteger valueOf(byte[] digits, int byte_len,
                                    boolean negative, int radix)
  {
    int chars_per_word = MPN.chars_per_word(radix);
    int[] words = new int[byte_len / chars_per_word + 1];
    int size = MPN.set_str(words, digits, byte_len, radix);
    if (size == 0)
      return ZERO;
    if (words[size-1] < 0)
      words[size++] = 0;
    if (negative)
      negate(words, words, size);
    return make(words, size);
  }

  public double doubleValue()
  {
    if (USING_NATIVE)
      return mpz.doubleValue();

    if (words == null)
      return (double) ival;
    if (ival <= 2)
      return (double) longValue();
    if (isNegative())
      return neg(this).roundToDouble(0, true, false);
      return roundToDouble(0, false, false);
  }

  public float floatValue()
  {
    return (float) doubleValue();
  }

  /** Return true if any of the lowest n bits are one.
   * (false if n is negative).  */
  private boolean checkBits(int n)
  {
    if (n <= 0)
      return false;
    if (words == null)
      return n > 31 || ((ival & ((1 << n) - 1)) != 0);
    int i;
    for (i = 0; i < (n >> 5) ; i++)
      if (words[i] != 0)
        return true;
    return (n & 31) != 0 && (words[i] & ((1 << (n & 31)) - 1)) != 0;
  }

  /** Convert a semi-processed BigInteger to double.
   * Number must be non-negative.  Multiplies by a power of two, applies sign,
   * and converts to double, with the usual java rounding.
   * @param exp power of two, positive or negative, by which to multiply
   * @param neg true if negative
   * @param remainder true if the BigInteger is the result of a truncating
   * division that had non-zero remainder.  To ensure proper rounding in
   * this case, the BigInteger must have at least 54 bits.  */
  private double roundToDouble(int exp, boolean neg, boolean remainder)
  {
    // Compute length.
    int il = bitLength();

    // Exponent when normalized to have decimal point directly after
    // leading one.  This is stored excess 1023 in the exponent bit field.
    exp += il - 1;

    // Gross underflow.  If exp == -1075, we let the rounding
    // computation determine whether it is minval or 0 (which are just
    // 0x0000 0000 0000 0001 and 0x0000 0000 0000 0000 as bit
    // patterns).
    if (exp < -1075)
      return neg ? -0.0 : 0.0;

    // gross overflow
    if (exp > 1023)
      return neg ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;

    // number of bits in mantissa, including the leading one.
    // 53 unless it's denormalized
    int ml = (exp >= -1022 ? 53 : 53 + exp + 1022);

    // Get top ml + 1 bits.  The extra one is for rounding.
    long m;
    int excess_bits = il - (ml + 1);
    if (excess_bits > 0)
      m = ((words == null) ? ival >> excess_bits
           : MPN.rshift_long(words, ival, excess_bits));
    else
      m = longValue() << (- excess_bits);

    // Special rounding for maxval.  If the number exceeds maxval by
    // any amount, even if it's less than half a step, it overflows.
    if (exp == 1023 && ((m >> 1) == (1L << 53) - 1))
      {
        if (remainder || checkBits(il - ml))
          return neg ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
        else
          return neg ? - Double.MAX_VALUE : Double.MAX_VALUE;
      }

    // Normal round-to-even rule: round up if the bit dropped is a one, and
    // the bit above it or any of the bits below it is a one.
    if ((m & 1) == 1
        && ((m & 2) == 2 || remainder || checkBits(excess_bits)))
      {
        m += 2;
        // Check if we overflowed the mantissa
        if ((m & (1L << 54)) != 0)
          {
            exp++;
            // renormalize
            m >>= 1;
          }
        // Check if a denormalized mantissa was just rounded up to a
        // normalized one.
        else if (ml == 52 && (m & (1L << 53)) != 0)
          exp++;
      }

    // Discard the rounding bit
    m >>= 1;

    long bits_sign = neg ? (1L << 63) : 0;
    exp += 1023;
    long bits_exp = (exp <= 0) ? 0 : ((long)exp) << 52;
    long bits_mant = m & ~(1L << 52);
    return Double.longBitsToDouble(bits_sign | bits_exp | bits_mant);
  }

  /** Copy the abolute value of this into an array of words.
   * Assumes words.length >= (this.words == null ? 1 : this.ival).
   * Result is zero-extended, but need not be a valid 2's complement number.
   */
  private void getAbsolute(int[] words)
  {
    int len;
    if (this.words == null)
      {
        len = 1;
        words[0] = this.ival;
      }
    else
      {
        len = this.ival;
        for (int i = len;  --i >= 0; )
          words[i] = this.words[i];
      }
    if (words[len - 1] < 0)
      negate(words, words, len);
    for (int i = words.length;  --i > len; )
      words[i] = 0;
  }

  /** Set dest[0:len-1] to the negation of src[0:len-1].
   * Return true if overflow (i.e. if src is -2**(32*len-1)).
   * Ok for src==dest. */
  private static boolean negate(int[] dest, int[] src, int len)
  {
    long carry = 1;
    boolean negative = src[len-1] < 0;
    for (int i = 0;  i < len;  i++)
      {
        carry += ((long) (~src[i]) & 0xffffffffL);
        dest[i] = (int) carry;
        carry >>= 32;
      }
    return (negative && dest[len-1] < 0);
  }

  /** Destructively set this to the negative of x.
   * It is OK if x==this.*/
  private void setNegative(BigInteger x)
  {
    int len = x.ival;
    if (x.words == null)
      {
        if (len == Integer.MIN_VALUE)
          set(- (long) len);
        else
          set(-len);
        return;
      }
    realloc(len + 1);
    if (negate(words, x.words, len))
      words[len++] = 0;
    ival = len;
  }

  /** Destructively negate this. */
  private void setNegative()
  {
    setNegative(this);
  }

  private static BigInteger abs(BigInteger x)
  {
    return x.isNegative() ? neg(x) : x;
  }

  public BigInteger abs()
  {
    if (USING_NATIVE)
      {
        BigInteger result = new BigInteger();
        mpz.abs(result.mpz);
        return result;
      }

    return abs(this);
  }

  private static BigInteger neg(BigInteger x)
  {
    if (x.words == null && x.ival != Integer.MIN_VALUE)
      return valueOf(- x.ival);
    BigInteger result = new BigInteger(0);
    result.setNegative(x);
    return result.canonicalize();
  }

  public BigInteger negate()
  {
    if (USING_NATIVE)
      {
        BigInteger result = new BigInteger();
        mpz.negate(result.mpz);
        return result;
      }

    return neg(this);
  }

  /** Calculates ceiling(log2(this < 0 ? -this : this+1))
   * See Common Lisp: the Language, 2nd ed, p. 361.
   */
  public int bitLength()
  {
    if (USING_NATIVE)
      return mpz.bitLength();

    if (words == null)
      return MPN.intLength(ival);
      return MPN.intLength(words, ival);
  }

  public byte[] toByteArray()
  {
    if (signum() == 0)
      return new byte[1];

    if (USING_NATIVE)
      {
        // the minimal number of bytes required to represent the MPI is function
        // of (a) its bit-length, and (b) its sign.  only when this MPI is both
        // positive, and its bit-length is a multiple of 8 do we add one zero
        // bit for its sign.  we do this so if we construct a new MPI from the
        // resulting byte array, we wouldn't mistake a positive number, whose
        // bit-length is a multiple of 8, for a similar-length negative one.
        int bits = bitLength();
        if (bits % 8 == 0 || this.signum() == 1)
          bits++;
        byte[] bytes = new byte[(bits + 7) / 8];
        mpz.toByteArray(bytes);
        return bytes;
      }

    // Determine number of bytes needed.  The method bitlength returns
    // the size without the sign bit, so add one bit for that and then
    // add 7 more to emulate the ceil function using integer math.
    byte[] bytes = new byte[(bitLength() + 1 + 7) / 8];
    int nbytes = bytes.length;

    int wptr = 0;
    int word;

    // Deal with words array until one word or less is left to process.
    // If BigInteger is an int, then it is in ival and nbytes will be <= 4.
    while (nbytes > 4)
      {
        word = words[wptr++];
        for (int i = 4; i > 0; --i, word >>= 8)
          bytes[--nbytes] = (byte) word;
      }

    // Deal with the last few bytes.  If BigInteger is an int, use ival.
    word = (words == null) ? ival : words[wptr];
    for ( ; nbytes > 0; word >>= 8)
      bytes[--nbytes] = (byte) word;

    return bytes;
  }

  /** Return the boolean opcode (for bitOp) for swapped operands.
   * I.e. bitOp(swappedOp(op), x, y) == bitOp(op, y, x).
   */
  private static int swappedOp(int op)
  {
    return
    "\000\001\004\005\002\003\006\007\010\011\014\015\012\013\016\017"
    .charAt(op);
  }

  /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
  private static BigInteger bitOp(int op, BigInteger x, BigInteger y)
  {
    switch (op)
      {
        case 0:  return ZERO;
        case 1:  return x.and(y);
        case 3:  return x;
        case 5:  return y;
        case 15: return valueOf(-1);
      }
    BigInteger result = new BigInteger();
    setBitOp(result, op, x, y);
    return result.canonicalize();
  }

  /** Do one the the 16 possible bit-wise operations of two BigIntegers. */
  private static void setBitOp(BigInteger result, int op,
                               BigInteger x, BigInteger y)
  {
    if ((y.words != null) && (x.words == null || x.ival < y.ival))
      {
        BigInteger temp = x;  x = y;  y = temp;
        op = swappedOp(op);
      }
    int xi;
    int yi;
    int xlen, ylen;
    if (y.words == null)
      {
        yi = y.ival;
        ylen = 1;
      }
    else
      {
        yi = y.words[0];
        ylen = y.ival;
      }
    if (x.words == null)
      {
        xi = x.ival;
        xlen = 1;
      }
    else
      {
        xi = x.words[0];
        xlen = x.ival;
      }
    if (xlen > 1)
      result.realloc(xlen);
    int[] w = result.words;
    int i = 0;
    // Code for how to handle the remainder of x.
    // 0:  Truncate to length of y.
    // 1:  Copy rest of x.
    // 2:  Invert rest of x.
    int finish = 0;
    int ni;
    switch (op)
      {
      case 0:  // clr
        ni = 0;
        break;
      case 1: // and
        for (;;)
          {
            ni = xi & yi;
            if (i+1 >= ylen) break;
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
          }
        if (yi < 0) finish = 1;
        break;
      case 2: // andc2
        for (;;)
          {
            ni = xi & ~yi;
            if (i+1 >= ylen) break;
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
          }
        if (yi >= 0) finish = 1;
        break;
      case 3:  // copy x
        ni = xi;
        finish = 1;  // Copy rest
        break;
      case 4: // andc1
        for (;;)
          {
            ni = ~xi & yi;
            if (i+1 >= ylen) break;
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
          }
        if (yi < 0) finish = 2;
        break;
      case 5: // copy y
        for (;;)
          {
            ni = yi;
            if (i+1 >= ylen) break;
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
          }
        break;
      case 6:  // xor
        for (;;)
          {
            ni = xi ^ yi;
            if (i+1 >= ylen) break;
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
          }
        finish = yi < 0 ? 2 : 1;
        break;
      case 7:  // ior
        for (;;)
          {
            ni = xi | yi;
            if (i+1 >= ylen) break;
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
          }
        if (yi >= 0) finish = 1;
        break;
      case 8:  // nor
        for (;;)
          {
            ni = ~(xi | yi);
            if (i+1 >= ylen) break;
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
          }
        if (yi >= 0)  finish = 2;
        break;
      case 9:  // eqv [exclusive nor]
        for (;;)
          {
            ni = ~(xi ^ yi);
            if (i+1 >= ylen) break;
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
          }
        finish = yi >= 0 ? 2 : 1;
        break;
      case 10:  // c2
        for (;;)
          {
            ni = ~yi;
            if (i+1 >= ylen) break;
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
          }
        break;
      case 11:  // orc2
        for (;;)
          {
            ni = xi | ~yi;
            if (i+1 >= ylen) break;
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
          }
        if (yi < 0)  finish = 1;
        break;
      case 12:  // c1
        ni = ~xi;
        finish = 2;
        break;
      case 13:  // orc1
        for (;;)
          {
            ni = ~xi | yi;
            if (i+1 >= ylen) break;
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
          }
        if (yi >= 0) finish = 2;
        break;
      case 14:  // nand
        for (;;)
          {
            ni = ~(xi & yi);
            if (i+1 >= ylen) break;
            w[i++] = ni;  xi = x.words[i];  yi = y.words[i];
          }
        if (yi < 0) finish = 2;
        break;
      default:
      case 15:  // set
        ni = -1;
        break;
      }
    // Here i==ylen-1; w[0]..w[i-1] have the correct result;
    // and ni contains the correct result for w[i+1].
    if (i+1 == xlen)
      finish = 0;
    switch (finish)
      {
      case 0:
        if (i == 0 && w == null)
          {
            result.ival = ni;
            return;
          }
        w[i++] = ni;
        break;
      case 1:  w[i] = ni;  while (++i < xlen)  w[i] = x.words[i];  break;
      case 2:  w[i] = ni;  while (++i < xlen)  w[i] = ~x.words[i];  break;
      }
    result.ival = i;
  }

  /** Return the logical (bit-wise) "and" of a BigInteger and an int. */
  private static BigInteger and(BigInteger x, int y)
  {
    if (x.words == null)
      return valueOf(x.ival & y);
    if (y >= 0)
      return valueOf(x.words[0] & y);
    int len = x.ival;
    int[] words = new int[len];
    words[0] = x.words[0] & y;
    while (--len > 0)
      words[len] = x.words[len];
    return make(words, x.ival);
  }

  /** Return the logical (bit-wise) "and" of two BigIntegers. */
  public BigInteger and(BigInteger y)
  {
    if (USING_NATIVE)
      {
        int dummy = y.signum; // force NPE check
        BigInteger result = new BigInteger();
        mpz.and(y.mpz, result.mpz);
        return result;
      }

    if (y.words == null)
      return and(this, y.ival);
    else if (words == null)
      return and(y, ival);

    BigInteger x = this;
    if (ival < y.ival)
      {
        BigInteger temp = this;  x = y;  y = temp;
      }
    int i;
    int len = y.isNegative() ? x.ival : y.ival;
    int[] words = new int[len];
    for (i = 0;  i < y.ival;  i++)
      words[i] = x.words[i] & y.words[i];
    for ( ; i < len;  i++)
      words[i] = x.words[i];
    return make(words, len);
  }

  /** Return the logical (bit-wise) "(inclusive) or" of two BigIntegers. */
  public BigInteger or(BigInteger y)
  {
    if (USING_NATIVE)
      {
        int dummy = y.signum; // force NPE check
        BigInteger result = new BigInteger();
        mpz.or(y.mpz, result.mpz);
        return result;
      }

    return bitOp(7, this, y);
  }

  /** Return the logical (bit-wise) "exclusive or" of two BigIntegers. */
  public BigInteger xor(BigInteger y)
  {
    if (USING_NATIVE)
      {
        int dummy = y.signum; // force NPE check
        BigInteger result = new BigInteger();
        mpz.xor(y.mpz, result.mpz);
        return result;
      }

    return bitOp(6, this, y);
  }

  /** Return the logical (bit-wise) negation of a BigInteger. */
  public BigInteger not()
  {
    if (USING_NATIVE)
      {
        BigInteger result = new BigInteger();
        mpz.not(result.mpz);
        return result;
      }

    return bitOp(12, this, ZERO);
  }

  public BigInteger andNot(BigInteger val)
  {
    if (USING_NATIVE)
      {
        int dummy = val.signum; // force NPE check
        BigInteger result = new BigInteger();
        mpz.andNot(val.mpz, result.mpz);
        return result;
      }

    return and(val.not());
  }

  public BigInteger clearBit(int n)
  {
    if (n < 0)
      throw new ArithmeticException();

    if (USING_NATIVE)
      {
        BigInteger result = new BigInteger();
        mpz.setBit(n, false, result.mpz);
        return result;
      }

    return and(ONE.shiftLeft(n).not());
  }

  public BigInteger setBit(int n)
  {
    if (n < 0)
      throw new ArithmeticException();

    if (USING_NATIVE)
      {
        BigInteger result = new BigInteger();
        mpz.setBit(n, true, result.mpz);
        return result;
      }

    return or(ONE.shiftLeft(n));
  }

  public boolean testBit(int n)
  {
    if (n < 0)
      throw new ArithmeticException();

    if (USING_NATIVE)
      return mpz.testBit(n) != 0;

    return !and(ONE.shiftLeft(n)).isZero();
  }

  public BigInteger flipBit(int n)
  {
    if (n < 0)
      throw new ArithmeticException();

    if (USING_NATIVE)
      {
        BigInteger result = new BigInteger();
        mpz.flipBit(n, result.mpz);
        return result;
      }

    return xor(ONE.shiftLeft(n));
  }

  public int getLowestSetBit()
  {
    if (USING_NATIVE)
      return mpz.compare(ZERO.mpz) == 0 ? -1 : mpz.lowestSetBit();

    if (isZero())
      return -1;

    if (words == null)
      return MPN.findLowestBit(ival);
    else
      return MPN.findLowestBit(words);
  }

  // bit4count[I] is number of '1' bits in I.
  private static final byte[] bit4_count = { 0, 1, 1, 2,  1, 2, 2, 3,
                                             1, 2, 2, 3,  2, 3, 3, 4};

  private static int bitCount(int i)
  {
    int count = 0;
    while (i != 0)
      {
        count += bit4_count[i & 15];
        i >>>= 4;
      }
    return count;
  }

  private static int bitCount(int[] x, int len)
  {
    int count = 0;
    while (--len >= 0)
      count += bitCount(x[len]);
    return count;
  }

  /** Count one bits in a BigInteger.
   * If argument is negative, count zero bits instead. */
  public int bitCount()
  {
    if (USING_NATIVE)
      return mpz.bitCount();

    int i, x_len;
    int[] x_words = words;
    if (x_words == null)
      {
        x_len = 1;
        i = bitCount(ival);
      }
    else
      {
        x_len = ival;
        i = bitCount(x_words, x_len);
      }
    return isNegative() ? x_len * 32 - i : i;
  }

  private void readObject(ObjectInputStream s)
    throws IOException, ClassNotFoundException
  {
    if (USING_NATIVE)
      {
        mpz = new GMP();
        s.defaultReadObject();
        if (signum != 0)
          mpz.fromByteArray(magnitude);
        // else it's zero and we need to do nothing
      }
    else
      {
        s.defaultReadObject();
        if (magnitude.length == 0 || signum == 0)
          {
            this.ival = 0;
            this.words = null;
          }
        else
          {
            words = byteArrayToIntArray(magnitude, signum < 0 ? -1 : 0);
            BigInteger result = make(words, words.length);
            this.ival = result.ival;
            this.words = result.words;
          }
      }
  }

  private void writeObject(ObjectOutputStream s)
    throws IOException, ClassNotFoundException
  {
    signum = signum();
    magnitude = signum == 0 ? new byte[0] : toByteArray();
    s.defaultWriteObject();
    magnitude = null; // not needed anymore
  }

  // inner class(es) ..........................................................

}