biginteger.java

来自「《移动Agent技术》一书的所有章节源代码。」· Java 代码 · 共 1,801 行 · 第 1/3 页

        int     xyCmp = compareTo(0, x, 0, y);
        int[]   count;

        if (xyCmp > 0)
        {
            int[]   c;

            int     shift = bitLength(0, x) - bitLength(0, y);

            if (shift > 1)
            {
                c = shiftLeft(y, shift - 1);
                count = shiftLeft(ONE.magnitude, shift - 1);
            }
            else
            {
                c = new int[x.length];
                count = new int[1];

                System.arraycopy(y, 0, c, c.length - y.length, y.length);
                count[0] = 1;
            }

            int[]   iCount = new int[count.length];

            subtract(0, x, 0, c);
            System.arraycopy(count, 0, iCount, 0, count.length);

            int xStart = 0;
            int cStart = 0;
            int iCountStart = 0;

            for (;;)
            {
                int cmp = compareTo(xStart, x, cStart, c);

                while (cmp >= 0)
                {
                    subtract(xStart, x, cStart, c);
                    add(count, iCount);
                    cmp = compareTo(xStart, x, cStart, c);
                }

                xyCmp = compareTo(xStart, x, 0, y);

                if (xyCmp > 0)
                {
                    if (x[xStart] == 0)
                    {
                        xStart++;
                    }

                    shift = bitLength(cStart, c) - bitLength(xStart, x);

                    if (shift == 0)
                    {
                        c = shiftRightOne(cStart, c);
                        iCount = shiftRightOne(iCountStart, iCount);
                    }
                    else
                    {
                        c = shiftRight(cStart, c, shift);
                        iCount = shiftRight(iCountStart, iCount, shift);
                    }

                    if (c[cStart] == 0)
                    {
                        cStart++;
                    }

                    if (iCount[iCountStart] == 0)
                    {
                        iCountStart++;
                    }
                }
                else if (xyCmp == 0)
                {
                    add(count, ONE.magnitude);
                    for (int i = xStart; i != x.length; i++)
                    {
                        x[i] = 0;
                    }
                    break;
                }
                else
                {
                    break;
                }
            }
        }
        else if (xyCmp == 0)
        {
            count = new int[1];

            count[0] = 1;
        }
        else
        {
            count = new int[1];

            count[0] = 0;
        }
   
        return count;
    }

	public BigInteger divide(
		BigInteger val)
		throws ArithmeticException
	{
		if (val.sign == 0)
        {
			throw new ArithmeticException("Divide by zero");
        }

		if (sign == 0)
        {
            return BigInteger.ZERO;
        }

		if (val.compareTo(BigInteger.ONE) == 0)
        {
            return this;
        }

        int[]   mag = new int[this.magnitude.length];
        System.arraycopy(this.magnitude, 0, mag, 0, mag.length);

        return new BigInteger(this.sign * val.sign, divide(mag, val.magnitude));
	}

	public BigInteger[] divideAndRemainder(
		BigInteger val)
		throws ArithmeticException
	{
		if (val.sign == 0)
        {
			throw new ArithmeticException("Divide by zero");
        }

		BigInteger biggies[] = new BigInteger[2];

		if (sign == 0)
        {
			biggies[0] = biggies[1] = BigInteger.ZERO;

			return biggies;
        }

		if (val.compareTo(BigInteger.ONE) == 0)
        {
			biggies[0] = this;
			biggies[1] = BigInteger.ZERO;

			return biggies;
        }

        int[]   remainder = new int[this.magnitude.length];
        System.arraycopy(this.magnitude, 0, remainder, 0, remainder.length);

        int[]   quotient = divide(remainder, val.magnitude);

        biggies[0] = new BigInteger(this.sign * val.sign, quotient);
        biggies[1] = new BigInteger(this.sign, remainder);

        return biggies;
	}

	public boolean equals(
		Object val)
	{
		if (val == this) return true;

		if (!(val instanceof BigInteger)) return false;
		BigInteger biggie = (BigInteger)val;

		if (biggie.sign != sign || biggie.magnitude.length != magnitude.length)
			return false;

		for (int i = 0; i < magnitude.length; i++) {
			if (biggie.magnitude[i] != magnitude[i]) return false;
			}

		return true;
	}

	public BigInteger gcd(
		BigInteger val)
	{
		if (val.sign == 0) return this.abs();
		else if (sign == 0) return val.abs();

		BigInteger r;
		BigInteger u = this;
		BigInteger v = val;

		while (v.sign != 0) {
			r = u.mod(v);
			u = v;
			v = r;
		}

		return u;
	}


	public int hashCode()
	{
		return 0;
	}


	public int intValue()
	{
        if (magnitude.length == 0)
        {
            return 0;
        }

        if (sign < 0)
        {
            return -magnitude[magnitude.length - 1];
        }
        else
        {
            return magnitude[magnitude.length - 1];
        }
	}


    /**
     * return whether or not a BigInteger is probably prime with a 
     * probability of 1 - (1/2)**certainty.
     * <p>
     * From Knuth Vol 2, pg 395.
     */
	public boolean isProbablePrime(
		int certainty)
	{
        if (certainty == 0)
        {
            return true;
        }
        
        BigInteger n = this.abs();

        if (n.equals(TWO))
        {
            return true;
        }

        if (n.equals(ONE) || !n.testBit(0))
        {
            return false;
        }

	if ((certainty & 0x1) == 1)
	{
		certainty = certainty / 2 + 1;
	}
	else
	{
		certainty /= 2;
	}

        //
        // let n = 1 + 2^kq
        //
        BigInteger  q = n.subtract(ONE);
        int         k = q.getLowestSetBit();

        q = q.shiftRight(k);

        Random  rnd = new Random();
        for (int i = 0; i <= certainty; i++)
        {
            BigInteger x;

            do
            {
                x = new BigInteger(n.bitLength(), rnd);
            }
            while (x.compareTo(ONE) <= 0 || x.compareTo(n) >= 0);

            int         j = 0;
            BigInteger  y = x.modPow(q, n);

            while (!((j == 0 && y.equals(ONE)) || y.equals(n.subtract(ONE))))
            {
                if (j > 0 && y.equals(ONE))
                {
                    return false;
                }
                if (++j == k)
                {
                    return false;
                }
                y = y.modPow(TWO, n);
            }
        }
        
		return true;
	}


	public long longValue()
	{
        long    val = 0;

        if (magnitude.length == 0)
        {
            return 0;
        }

        if (magnitude.length > 1)
        {
            val = magnitude[magnitude.length - 2] << 32 
                        | (magnitude[magnitude.length - 1] & IMASK);
        }
        else
        {
            val = (magnitude[magnitude.length - 1] & IMASK);
        }

        if (sign < 0)
        {
            return -val;
        }
        else
        {
            return val;
        }
	}


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


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


	public BigInteger mod(
		BigInteger m)
		throws ArithmeticException
	{
		if (m.sign <= 0)
        {
             throw new ArithmeticException("BigInteger: modulus is not positive");
        }

		BigInteger biggie = this.remainder(m);

		return (biggie.sign >= 0 ? biggie : biggie.add(m));
	}


	public BigInteger modInverse(
		BigInteger m)
		throws ArithmeticException
	{
		if (m.sign != 1)
        {
			throw new ArithmeticException("Modulus must be positive");
        }

        BigInteger x = new BigInteger();
        BigInteger y = new BigInteger();

        BigInteger gcd = BigInteger.extEuclid(this, m, x, y);

        if (!gcd.equals(BigInteger.ONE))
        {
                throw new ArithmeticException("Numbers not relatively prime.");
        }

        if (x.compareTo(BigInteger.ZERO) < 0)
        {
            x = x.add(m);
        }

        return x;
	}

	/**
	 * Calculate the numbers u1, u2, and u3 such that:
	 *
	 * u1 * a + u2 * b = u3
	 *
	 * where u3 is the greatest common divider of a and b.
	 * a and b using the extended Euclid algorithm (refer p. 323
	 * of The Art of Computer Programming vol 2, 2nd ed).
	 * This also seems to have the side effect of calculating
	 * some form of multiplicative inverse.
	 *
	 * @param a    First number to calculate gcd for
	 * @param b    Second number to calculate gcd for
	 * @param u1Out      the return object for the u1 value
	 * @param u2Out      the return object for the u2 value
	 * @return     The greatest common divisor of a and b
	 */
	private static BigInteger extEuclid(
		BigInteger a,
		BigInteger b,
		BigInteger u1Out,
		BigInteger u2Out)
	{
		BigInteger  res;

		BigInteger u1 = BigInteger.ONE;
		BigInteger u3 = a;
		BigInteger v1 = BigInteger.ZERO;
		BigInteger v3 = b;

		while (v3.compareTo(BigInteger.ZERO) > 0)
        {
            BigInteger q, tn, tv;

            q = u3.divide(v3);

            tn = u1.subtract(v1.multiply(q));
            u1 = v1;
            v1 = tn;

            tn = u3.subtract(v3.multiply(q));
            u3 = v3;
            v3 = tn;
        }

		u1Out.sign = u1.sign;
		u1Out.magnitude = u1.magnitude;

		res = u3.subtract(u1.multiply(a)).divide(b);
		u2Out.sign = res.sign;
		u2Out.magnitude = res.magnitude;

		return u3;
	}

    /**
     * zero out the array x
     */
    private void zero(
        int[]   x)
    {
        for (int i = 0; i != x.length; i++)
        {
            x[i] = 0;
        }
    }

	public BigInteger modPow(
		BigInteger exponent,
		BigInteger m)
		throws ArithmeticException
	{
        int[]       zAccum, zVal;
        int[]       yAccum, yVal;

        if (magnitude.length <= m.magnitude.length)
        {
            zAccum = new int[m.magnitude.length * 2];
            zVal = new int[m.magnitude.length];

            System.arraycopy(magnitude, 0, zVal,
                zVal.length - magnitude.length, magnitude.length);
        }
        else
        {
            //
            // in normal practice we'll never see this...
            //
            BigInteger  tmp = this.remainder(m);

            zAccum = new int[m.magnitude.length * 2];
            zVal = new int[m.magnitude.length];

            System.arraycopy(tmp.magnitude, 0, zVal,
                zVal.length - tmp.magnitude.length, tmp.magnitude.length);
        }

        yAccum = new int[m.magnitude.length * 2];
        yVal = new int[m.magnitude.length];

        //
		// from LSW to MSW
        //
		for (int i = 0; i < exponent.magnitude.length; i++)
        {
			int v = exponent.magnitude[i];
			int bits = 0;

            if (i == 0)
            {
                while (v > 0)
                {
				    v <<= 1;
                    bits++;
                }

                //
                // first time in initialise y
                //
                System.arraycopy(zVal, 0, yVal, 0, zVal.length);

                v <<= 1;
                bits++;
            }

			while (v != 0)
            {
                square(yAccum, yVal);
                remainder(yAccum, m.magnitude);
                System.arraycopy(yAccum, yAccum.length - yVal.length,
                                                  yVal, 0, yVal.length);
                zero(yAccum);
                bits++;

				if (v < 0)
                {
                    multiply(yAccum, yVal, zVal);
                    remainder(yAccum, m.magnitude);
                    System.arraycopy(yAccum, yAccum.length - yVal.length,
                                                      yVal, 0, yVal.length);
                    zero(yAccum);
                }

				v <<= 1;
            }

            while (bits < 32)
            {
                square(yAccum, yVal);
                remainder(yAccum, m.magnitude);
                System.arraycopy(yAccum, yAccum.length - yVal.length,
                                                   yVal, 0, yVal.length);
                zero(yAccum);
                bits++;
            }
        }

        return new BigInteger(1, yVal);
	}

    /**
     * return w with w = x * x - w is assumed to have enough space.
     */
	private int[] square(
        int[]   w,
        int[]   x)
	{
        long    u1, u2, c;

        if (w.length != 2 * x.length)
        {
            throw new IllegalArgumentException("no I don't think so...");
        }

        for (int i = x.length - 1; i != 0; i--)
        {
            long    v = (x[i] & IMASK);

            u1 = v * v;
            u2 = u1 >>> 32;
            u1 = u1 & IMASK;

            u1 += (w[2 * i + 1] & IMASK);

            w[2 * i + 1] = (int)u1;
            c = u2 + (u1 >> 32);

            for (int j = i - 1; j >= 0; j--)
            {
                u1 = (x[j] & IMASK) * v;
                u2 = u1 >>> 31;                     // multiply by 2!
                u1 = (u1 & 0x7fffffff) << 1;        // multiply by 2!
                u1 += (w[i + j + 1] & IMASK) + c;

                w[i + j + 1] = (int)u1;
                c = u2 + (u1 >>> 32);
            }
            c += w[i] & IMASK;
            w[i] = (int)c;
            w[i - 1] = (int)(c >> 32);
        }

        u1 = (x[0] & IMASK);
        u1 = u1 * u1;
        u2 = u1 >>> 32;
        u1 = u1 & IMASK;

        u1 += (w[1] & IMASK);

        w[1] = (int)u1;