biginteger.java

来自「纯java操作系统jnode,安装简单和操作简单的个人使用的Java操作系统」· Java 代码 · 共 2,274 行 · 第 1/4 页

/* java.math.BigInteger -- Arbitary precision integers
   Copyright (C) 1998, 1999, 2000, 2001 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., 59 Temple Place, Suite 330, Boston, MA
02111-1307 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.java.math.MPN;
import java.util.Random;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.IOException;

/**
 * @author Warren Levy <[e-mail]>
 * @date December 20, 1999.
 */

/**
 * 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 <[e-mail]>
 * (found in Kawa 1.6.62).
 *
 * Status:  Believed complete and correct.
 */

public class BigInteger extends Number implements Comparable
{
  /** 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. */
  transient private int ival;
  transient private int[] words;

  // Serialization fields.
  private int bitCount = -1;
  private int bitLength = -1;
  private int firstNonzeroByteNum = -2;
  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. */
  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 = new BigInteger[numFixNum];

  static {
    for (int i = numFixNum;  --i >= 0; )
      smallFixNums[i] = new BigInteger(i + minFixNum);
  }

  // JDK1.2
  public static final BigInteger ZERO = smallFixNums[-minFixNum];

  // JDK1.2
  public static final BigInteger ONE = smallFixNums[1 - minFixNum];

  /* 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 };

  private BigInteger()
  {
  }

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

  public BigInteger(String val, int radix)
  {
    BigInteger result = valueOf(val, 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)
  {
    if (val == null || val.length < 1)
      throw new NumberFormatException();

    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)
  {
    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;
      }

    // 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)
  {
    if (numBits < 0)
      throw new IllegalArgumentException();

    init(numBits, rnd);
  }

  private void init(int numBits, Random rnd)
  {
    int highbits = numBits & 31;
    if (highbits > 0)
      highbits = rnd.nextInt() >>> (32 - highbits);
    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(bitLength, rnd);

    // Keep going until we find a probable prime.
    while (true)
      {
	if (isProbablePrime(certainty))
	  return;

	init(bitLength, rnd);
      }
  }

  /** Return a (possibly-shared) BigInteger with a given long value. */
  private static BigInteger make(long value)
  {
    if (value >= minFixNum && value <= maxFixNum)
      return smallFixNums[(int)value - minFixNum];
    int i = (int) value;
    if ((long)i == value)
      return new BigInteger(i);
    BigInteger result = alloc(2);
    result.ival = 2;
    result.words[0] = i;
    result.words[1] = (int) (value >> 32);
    return result;
  }

  // FIXME: Could simply rename 'make' method above as valueOf while
  // changing all instances of 'make'.  Don't do this until this class
  // is done as the Kawa class this is based on has 'make' methods
  // with other parameters; wait to see if they are used in BigInteger.
  public static BigInteger valueOf(long val)
  {
    return make(val);
  }

  /** 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 make(len);
    len = BigInteger.wordsNeeded(words, len);
    if (len <= 1)
      return len == 0 ? ZERO : make(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) | (((int) bytes[bptr]) & 0xff);
    words[--nwords] = word;

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

  /** Allocate a new non-shared BigInteger.
   * @param nwords number of words to allocate
   */
  private static BigInteger alloc(int nwords)
  {
    if (nwords <= 1)
      return new BigInteger();
    BigInteger result = new BigInteger();
    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 final boolean isNegative()
  {
    return (words == null ? ival : words[ival - 1]) < 0;
  }

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

  private static int compareTo(BigInteger x, BigInteger y)
  {
    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);
  }

  // JDK1.2
  public int compareTo(Object obj)
  {
    if (obj instanceof BigInteger)
      return compareTo(this, (BigInteger) obj);
    throw new ClassCastException();
  }

  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 final boolean isOdd()
  {
    int low = words == null ? ival : words[0];
    return (low & 1) != 0;
  }

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

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

  private final boolean isMinusOne()
  {
    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[(int) ival - minFixNum];
    return this;
  }

  /** Add two ints, yielding a BigInteger. */
  private static final BigInteger add(int x, int y)
  {
    return BigInteger.make((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 final void setAdd(int y)
  {
    setAdd(this, y);
  }

  /** Destructively set the value of this to a long. */
  private final 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 final void set(int[] words, int length)
  {
    this.ival = length;
    this.words = words;
  }

  /** Destructively set the value of this to that of y. */
  private final 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 BigInteger.make((long) k * (long) y.ival + (long) x.ival);
    if (k != 1)
      {
	if (k == -1)
	  y = BigInteger.neg(y);
	else
	  y = BigInteger.times(y, BigInteger.make(k));
      }
    if (x.words == null)
      return BigInteger.add(y, x.ival);
    if (y.words == null)
      return BigInteger.add(x, y.ival);
    // Both are big
    //int len;
    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)
  {
    return add(this, val, 1);
  }

  public BigInteger subtract(BigInteger val)