harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From mloe...@apache.org
Subject svn commit: r431881 [2/3] - in /incubator/harmony/enhanced/classlib/trunk/modules: luni/src/main/java/java/lang/ math/src/main/java/java/math/ math/src/main/resources/ math/src/test/java/org/apache/harmony/tests/java/math/ math2/
Date Wed, 16 Aug 2006 11:56:04 GMT
Added: incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigInteger.java
URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigInteger.java?rev=431881&view=auto
==============================================================================
--- incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigInteger.java (added)
+++ incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigInteger.java Wed Aug 16 04:55:59 2006
@@ -0,0 +1,839 @@
+/*
+ *  Copyright 2005, 2006 The Apache Software Foundation or its licensors, as applicable.
+ *
+ *  Licensed under the Apache License, Version 2.0 (the "License");
+ *  you may not use this file except in compliance with the License.
+ *  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+package java.math;
+
+import java.io.IOException;
+import java.io.ObjectInputStream;
+import java.io.ObjectOutputStream;
+import java.util.Random;
+import java.io.Serializable;
+
+/**
+ * @author Daniel Fridlender
+ * @author Matthias Gallé
+ * @author Mariano Heredia
+ * @author Miguel Vasquez
+ * 
+ * @ar.org.fitc.spec_ref 
+ */
+public class BigInteger extends Number implements Comparable<BigInteger>,
+        Serializable {
+
+    /** @ar.org.fitc.spec_ref */
+    private static final long serialVersionUID = -8287574255936472291L;
+
+    /* Fields used for the internal representation. */
+
+    /** The magnitude of this in the little-endian representation. */
+    transient int digits[];
+
+    /** The length of this in measured in ints. Can be less than digits.length(). */
+    transient int numberLength;
+
+    /** The sign of this. */
+    transient int sign;
+
+    /* Static Fields */
+
+    /** @ar.org.fitc.spec_ref */
+    public static final BigInteger ONE = new BigInteger(1, 1);
+
+    /** @ar.org.fitc.spec_ref */
+    public static final BigInteger TEN = new BigInteger(1, 10);
+
+    /** @ar.org.fitc.spec_ref */
+    public static final BigInteger ZERO = new BigInteger(0, 0);
+
+    /** The {@code BigInteger} constant -1. */
+    static final BigInteger MINUS_ONE = new BigInteger(-1, 1);
+
+    /** The {@code BigInteger} constant 0 used for comparison. */
+    static final int EQUALS = 0;
+
+    /** The {@code BigInteger} constant 1 used for comparison. */
+    static final int GREATER = 1;
+
+    /** The {@code BigInteger} constant -1 used for comparison. */
+    static final int LESS = -1;
+
+    /** All the {@ BigInteger} numbers in the range [0,10] are cached. */
+    static final BigInteger[] SMALL_VALUES = { ZERO, ONE, new BigInteger(1, 2),
+            new BigInteger(1, 3), new BigInteger(1, 4), new BigInteger(1, 5),
+            new BigInteger(1, 6), new BigInteger(1, 7), new BigInteger(1, 8),
+            new BigInteger(1, 9), TEN };
+
+    /* Serialized Fields */
+
+    /** @ar.org.fitc.spec_ref */
+    private int bitCount = -1;
+
+    /** @ar.org.fitc.spec_ref */
+    private int bitLength = -1;
+
+    /** @ar.org.fitc.spec_ref */
+    private int lowestSetBit = -2;
+
+    /** @ar.org.fitc.spec_ref */
+    private int firstNonzeroByteNum = -2;
+
+    /** @ar.org.fitc.spec_ref */
+    private int signum;
+
+    /** @ar.org.fitc.spec_ref */
+    private byte[] magnitude;
+
+    /* Public Constructors */
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger(int numBits, Random rnd) {
+        if (numBits < 0) {
+            throw new IllegalArgumentException("numBits must be non-negative");
+        }
+        if (rnd == null) {
+            throw new NullPointerException();
+        }
+        if (numBits == 0) {
+            sign = 0;
+            numberLength = 1;
+            digits = new int[] { 0 };
+        } else {
+            sign = 1;
+            numberLength = (numBits + 31) >> 5;
+            digits = new int[numberLength];
+            for (int i = 0; i < numberLength; i++) {
+                digits[i] = rnd.nextInt();
+            }
+            // Using only the necessary bits
+            digits[numberLength - 1] >>>= (-numBits) & 31;
+            cutOffLeadingZeroes();
+        }
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger(int bitLength, int certainty, Random rnd) {
+        if (bitLength < 2) {
+            throw new ArithmeticException("bitLength < 2");
+        }
+        BigInteger me = Primality.consBigInteger(bitLength, certainty, rnd);
+        sign = me.sign;
+        numberLength = me.numberLength;
+        digits = me.digits;
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger(String val) {
+        this(val, 10);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger(String val, int radix) {
+        if (val == null) {
+            throw new NullPointerException();
+        }
+        if ((radix < Character.MIN_RADIX) || (radix > Character.MAX_RADIX)) {
+            throw new NumberFormatException("Radix out of range");
+        }
+        if (val.length() == 0) {
+            throw new NumberFormatException("Zero length BigInteger");
+        }
+        BigInteger me = Conversion.string2BigInteger(val, radix);
+        sign = me.sign;
+        numberLength = me.numberLength;
+        digits = me.digits;
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger(int signum, byte[] magnitude) {
+        if (magnitude == null) {
+            throw new NullPointerException();
+        }
+        if ((signum < -1) || (signum > 1)) {
+            throw new NumberFormatException("Invalid signum value");
+        }
+        if (signum == 0) {
+            for (int i = 0; i < magnitude.length; i++) {
+                if (magnitude[i] != 0) {
+                    throw new NumberFormatException("signum-magnitude mismatch");
+                }
+            }
+        }
+        if (magnitude.length == 0) {
+            sign = 0;
+            numberLength = 1;
+            digits = new int[] { 0 };
+        } else {
+            sign = signum;
+            putBytesToIntegers(magnitude, false);
+            cutOffLeadingZeroes();
+        }
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger(byte[] val) {
+        if (val.length == 0) {
+            throw new NumberFormatException("Zero length BigInteger");
+        }
+        if (val[0] < 0) {
+            sign = -1;
+            putBytesToIntegers(val, true);
+            BitLevel.setTrueCoded(digits, numberLength);
+        } else {
+            sign = 1;
+            putBytesToIntegers(val, false);
+        }
+        cutOffLeadingZeroes();
+    }
+
+    /* Package Constructors */
+
+    /** 
+     * Constructs a number which array is of size 1.
+     * @param sign the sign of the number
+     * @param value the only one digit of array 
+     */
+    BigInteger(int sign, int value) {
+        this.sign = sign;
+        numberLength = 1;
+        digits = new int[] { value };
+    }
+
+    /** 
+     * Constructs a number without to create new space.
+     * This constrcut should be used only if the three fields 
+     * of representation are known. 
+     * @param sign the sign of the number
+     * @param numberLength the length of the internal array
+     * @param digits a reference of some array created before 
+     */
+    BigInteger(int sign, int numberLength, int[] digits) {
+        this.sign = sign;
+        this.numberLength = numberLength;
+        this.digits = digits;
+    }
+
+    /**
+     * Creates a new {@code BigInteger} whose value is equal to the
+     * specified {@code long}.
+     * @param sign the sign of the number
+     * @param val the value of the new {@code BigInteger}.
+     */
+    BigInteger(int sign, long val) {
+        //PRE: (val >= 0) && (sign >= -1) && (sign <= 1)
+        this.sign = sign;
+        if ((val & 0xFFFFFFFF00000000L) == 0) {
+            // It fits in one 'int'
+            numberLength = 1;
+            digits = new int[] { (int) val };
+        } else {
+            numberLength = 2;
+            digits = new int[] { (int) val, (int) (val >> 32) };
+        }
+    }
+
+    /**
+     * Creates a new {@code BigInteger} with the given sign and magnitude. 
+     * This constructor does not create a copy, so any changes to the 
+     * reference will affect the new number.
+     * @param signum The sign of the number represented by {@code digits}
+     * @param digits The magnitude of the number
+     */
+    BigInteger(int signum, int digits[]) {
+        if (digits.length == 0) {
+            sign = 0;
+            numberLength = 1;
+            digits = new int[] { 0 };
+        } else {
+            sign = signum;
+            numberLength = digits.length;
+            this.digits = digits;
+            cutOffLeadingZeroes();
+        }
+    }
+
+    /* Public Methods */
+
+    /** @ar.org.fitc.spec_ref */
+    public static BigInteger valueOf(long val) {
+        if (val < 0) {
+            return new BigInteger(-1, -val);
+        } else if (val <= 10) {
+            return SMALL_VALUES[(int) val];
+        } else {// (val > 10)
+            return new BigInteger(1, val);
+        }
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public byte[] toByteArray() {
+        BigInteger temp = this;
+        int bitLen = bitLength();
+        int bytesLen = (bitLen == 0) ? 1 : ((bitLen + 1) >> 3)
+                + (((bitLen + 1) & 7) == 0 ? 0 : 1);
+        if (sign < 0) {
+            temp = clone();
+            // Convert from the true coded form to the two's complement one
+            BitLevel.setTrueCoded(temp.digits, numberLength);
+        }
+        /* Puts the little-endian int array representing the magnitude
+         * of this BigInteger into the big-endian byte array. */
+        byte[] bytes = new byte[bytesLen];
+        int firstByteNumber = 0;
+        int highBytes;
+        int digitIndex = 0;
+        int bytesInInteger = 4;
+        int digit;
+        int hB;
+
+        if (bytesLen - (numberLength << 2) == 1) {
+            bytes[0] = (byte) ((sign < 0) ? -1 : 0);
+            highBytes = 4;
+            firstByteNumber++;
+        } else {
+            hB = bytesLen & 3;
+            highBytes = (hB == 0) ? 4 : hB;
+        }
+        while (bytesLen > firstByteNumber) {
+            digit = temp.digits[digitIndex];
+            digitIndex++;
+            if (digitIndex == numberLength) {
+                bytesInInteger = highBytes;
+            }
+            for (int i = 0; i < bytesInInteger; i++, digit >>= 8) {
+                bytes[--bytesLen] = (byte) digit;
+            }
+        }
+        return bytes;
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger abs() {
+        return ((sign < 0) ? new BigInteger(1, numberLength, digits) : this);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger negate() {
+        return ((sign == 0) ? this
+                : new BigInteger(-sign, numberLength, digits));
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger add(BigInteger val) {
+        return Elementary.add(this, val);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger subtract(BigInteger val) {
+        return Elementary.subtract(this, val);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public int signum() {
+        return sign;
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger shiftRight(int n) {
+        if ((n == 0) || (sign == 0)) {
+            return this;
+        }
+        return ((n > 0) ? BitLevel.shiftRight(this, n) : BitLevel.shiftLeft(
+                this, -n));
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger shiftLeft(int n) {
+        if ((n == 0) || (sign == 0)) {
+            return this;
+        }
+        return ((n > 0) ? BitLevel.shiftLeft(this, n) : BitLevel.shiftRight(
+                this, -n));
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public int bitLength() {
+        return BitLevel.bitLength(this);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public boolean testBit(int n) {
+        if (n == 0) {
+            return ((digits[0] & 1) != 0);
+        }
+        if (n < 0) {
+            throw new ArithmeticException("Negative bit address");
+        }
+        int intCount = n >> 5;
+        if (intCount >= numberLength) {
+            return (sign < 0);
+        }
+        int digit = digits[intCount];
+        int i;
+        n = (1 << (n & 31)); // int with 1 set to the needed position
+        if (sign < 0) {
+            for (i = 0; (i < intCount) && (digits[i] == 0); i++)
+                ;
+            digit = ((i == intCount) ? -digit : ~digit);
+        }
+        return ((digit & n) != 0);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger setBit(int n) {
+        if (n < 0) {
+            throw new ArithmeticException("Negative bit address");
+        }
+        int intCount = n >> 5; // count of integers: count / 32
+        return (((sign < 0) && (intCount >= numberLength)) ? this : BitLevel
+                .changeBit(this, intCount, n & 31, 2));
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger clearBit(int n) {
+        if (n < 0) {
+            throw new ArithmeticException("Negative bit address");
+        }
+        int intCount = n >> 5;
+        return (((sign == 0) || ((sign > 0) && (intCount >= numberLength))) ? this
+                : BitLevel.changeBit(this, intCount, n & 31, 3));
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger flipBit(int n) {
+        if (n < 0) {
+            throw new ArithmeticException("Negative bit address");
+        }
+        return BitLevel.changeBit(this, n >> 5, n & 31, 1);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public int getLowestSetBit() {
+        if (sign == 0) {
+            return -1;
+        }
+        int i;
+        // (sign != 0)  implies that exists some non zero digit 
+        for (i = 0; digits[i] == 0; i++)
+            ;
+        return ((i << 5) + Integer.numberOfTrailingZeros(digits[i]));
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public int bitCount() {
+        return BitLevel.bitCount(this);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger not() {
+        return Logical.not(this);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger and(BigInteger val) {
+        return Logical.and(this, val);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger or(BigInteger val) {
+        return Logical.or(this, val);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger xor(BigInteger val) {
+        return Logical.xor(this, val);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger andNot(BigInteger val) {
+        return Logical.and(this, Logical.not(val));
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public int intValue() {
+        return (sign * digits[0]);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public long longValue() {
+        long value = (numberLength > 1) ? (((long) digits[1]) << 32)
+                | (digits[0] & 0xFFFFFFFFL) : (digits[0] & 0xFFFFFFFFL);
+        return (sign * value);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public float floatValue() {
+        return (float) doubleValue();
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public double doubleValue() {
+        return Conversion.bigInteger2Double(this);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public int compareTo(BigInteger val) {
+        if (sign > val.sign) {
+            return GREATER;
+        }
+        if (sign < val.sign) {
+            return LESS;
+        }
+        if (numberLength > val.numberLength) {
+            return sign;
+        }
+        if (numberLength < val.numberLength) {
+            return -val.sign;
+        }
+        // Equal sign and equal numberLength 
+        return (sign * Elementary.compareArrays(digits, val.digits,
+                numberLength));
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger min(BigInteger val) {
+        return ((this.compareTo(val) == LESS) ? this : val);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger max(BigInteger val) {
+        return ((this.compareTo(val) == GREATER) ? this : val);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public int hashCode() {
+        return intValue();
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public boolean equals(Object x) {
+        return ((x instanceof BigInteger) && (compareTo((BigInteger) x) == EQUALS));
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public String toString() {
+        return Conversion.toDecimalScaledString(this, 0);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public String toString(int radix) {
+        return Conversion.bigInteger2String(this, radix);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger gcd(BigInteger val) {
+        BigInteger val1 = this.abs();
+        BigInteger val2 = val.abs();
+        // To avoid a possible division by zero
+        if (sign == 0) {
+            return val2;
+        }
+        if (val.sign == 0) {
+            return val1;
+        }
+        /* Implements one step of the Euclidean algorithm
+         * To reduce some operand if it's much smaller than the other one */
+        if (val1.numberLength > val2.numberLength) {
+            val1 = val1.remainder(val2);
+            if (val1.sign == 0) {
+                return val2;
+            }
+        } else if (val2.numberLength > val1.numberLength) {
+            val2 = val2.remainder(val1);
+            if (val2.sign == 0) {
+                return val1;
+            }
+        }
+        /* Optimization for small operands
+         * (val1.bitLength() < 64)   and   (val2.bitLength() < 64) */
+        if (((val1.numberLength == 1) || ((val1.numberLength == 2) && (val1.digits[1] > 0)))
+                && ((val2.numberLength == 1) || ((val2.numberLength == 2) && (val2.digits[1] > 0)))) {
+            return BigInteger.valueOf(Division.gcdBinary(val1.longValue(), val2
+                    .longValue()));
+        } else {// Now 'val1' and 'val2' will be muttable
+            return Division.gcdBinary(val1.clone(), val2.clone());
+        }
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger multiply(BigInteger val) {
+        // This let us to throw NullPointerException when val == null
+        if (val.sign == 0) {
+            return ZERO;
+        }
+        if (sign == 0) {
+            return ZERO;
+        }
+        return Multiplication.multiply(this, val);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger pow(int exp) {
+        if (exp > 0) {
+            return Multiplication.pow(this, exp);
+        } else if (exp == 0) {
+            return ONE;
+        } else {// (exp < 0)
+            throw new ArithmeticException("Negative exponent");
+        }
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger[] divideAndRemainder(BigInteger divisor) {
+        int divisorSign = divisor.sign;
+        if (divisorSign == 0) {
+            throw new ArithmeticException("BigInteger divide by zero");
+        }
+        int divisorLen = divisor.numberLength;
+        int[] divisorDigits = divisor.digits;
+        if (divisorLen == 1) {
+            return Division.divideAndRemainderByInteger(this, divisorDigits[0],
+                    divisorSign);
+        }
+        // res[0] is a quotient and res[1] is a remainder:
+        int[] thisDigits = digits;
+        int thisLen = numberLength;
+        int cmp = (thisLen != divisorLen) ? ((thisLen > divisorLen) ? 1 : -1)
+                : Elementary.compareArrays(thisDigits, divisorDigits, thisLen);
+        if (cmp < 0) {
+            return new BigInteger[] { ZERO, this };
+        } else {
+            int thisSign = sign;
+            int quotientLength = thisLen - divisorLen + 1;
+            int remainderLength = divisorLen;
+            int quotientSign = ((thisSign == divisorSign) ? 1 : -1);
+            int quotientDigits[] = new int[quotientLength];
+            int remainderDigits[] = Division.divide(quotientDigits,
+                    quotientLength, thisDigits, thisLen, divisorDigits,
+                    divisorLen);
+            BigInteger result0 = new BigInteger(quotientSign, quotientLength,
+                    quotientDigits);
+            BigInteger result1 = new BigInteger(thisSign, remainderLength,
+                    remainderDigits);
+            result0.cutOffLeadingZeroes();
+            result1.cutOffLeadingZeroes();
+            return new BigInteger[] { result0, result1 };
+        }
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger divide(BigInteger divisor) {
+        if (divisor.sign == 0) {
+            throw new ArithmeticException("BigInteger divide by zero");
+        }
+        int divisorSign = divisor.sign;
+        if (divisor.isOne()) {
+            return ((divisor.sign > 0) ? this : this.negate());
+        }
+        int thisSign = sign;
+        int thisLen = numberLength;
+        int divisorLen = divisor.numberLength;
+        if (thisLen + divisorLen == 2) {
+            long val = ((long) digits[0] & 0xFFFFFFFFL)
+                    / ((long) divisor.digits[0] & 0xFFFFFFFFL);
+            if (thisSign != divisorSign) {
+                val = -val;
+            }
+            return valueOf(val);
+        } else {
+            int cmp = ((thisLen != divisorLen) ? ((thisLen > divisorLen) ? 1
+                    : -1) : Elementary.compareArrays(digits, divisor.digits,
+                    thisLen));
+            if (cmp == EQUALS) {
+                return ((thisSign == divisorSign) ? ONE : MINUS_ONE);
+            }
+            if (cmp == LESS) {
+                return ZERO;
+            }
+            int resLength = thisLen - divisorLen + 1;
+            int resDigits[] = new int[resLength];
+            int resSign = ((thisSign == divisorSign) ? 1 : -1);
+            if (divisorLen == 1) {
+                Division.divideArrayByInt(resDigits, digits, thisLen,
+                        divisor.digits[0]);
+            } else {
+                Division.divide(resDigits, resLength, digits, thisLen,
+                        divisor.digits, divisorLen);
+            }
+            BigInteger result = new BigInteger(resSign, resLength, resDigits);
+            result.cutOffLeadingZeroes();
+            return result;
+        }
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger remainder(BigInteger divisor) {
+        if (divisor.sign == 0) {
+            throw new ArithmeticException("BigInteger divide by zero");
+        }
+        int thisLen = numberLength;
+        int divisorLen = divisor.numberLength;
+        if (((thisLen != divisorLen) ? ((thisLen > divisorLen) ? 1 : -1)
+                : Elementary.compareArrays(digits, divisor.digits, thisLen)) == LESS) {
+            return this;
+        }
+        int resLength = divisorLen;
+        int resDigits[] = new int[resLength];
+        if (resLength == 1) {
+            resDigits[0] = Division.remainderArrayByInt(digits, thisLen,
+                    divisor.digits[0]);
+        } else {
+            int qLen = thisLen - divisorLen + 1;
+            resDigits = Division.divide(null, qLen, digits, thisLen,
+                    divisor.digits, divisorLen);
+        }
+        BigInteger result = new BigInteger(sign, resLength, resDigits);
+        result.cutOffLeadingZeroes();
+        return result;
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger modInverse(BigInteger m) {
+        if (m.sign <= 0) {
+            throw new ArithmeticException("BigInteger: modulus not positive");
+        }
+        // If both are even, no inverse exists
+        if (!(testBit(0) || m.testBit(0))) {
+            throw new ArithmeticException("BigInteger not invertible.");
+        }
+        if (m.isOne()) {
+            return ZERO;
+        }
+        // From now on: (m > 1)
+        BigInteger res = Division.modInverse(abs(), m);
+        if (res.sign == 0) {
+            throw new ArithmeticException("BigInteger not invertible.");
+        }
+        return ((sign < 0) ? m.subtract(res) : res);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger modPow(BigInteger exponent, BigInteger m) {
+        if (m.sign <= 0) {
+            throw new ArithmeticException("BigInteger: modulus not positive");
+        }
+        BigInteger base = this;
+        if (exponent.sign < 0) {
+            base = modInverse(m);
+            exponent = exponent.negate();
+        }
+        // From now on: (m > 0) and (exponent >= 0)
+        BigInteger res = (m.testBit(0)) ? Division.oddModPow(base.abs(),
+                exponent, m) : Division.evenModPow(base.abs(), exponent, m);
+        if ((base.sign < 0) && exponent.testBit(0)) {
+            // -b^e mod m == ((-1 mod m) * (b^e mod m)) mod m
+            res = m.subtract(BigInteger.ONE).multiply(res).mod(m);
+        }
+        // else exponent is even, so base^exp is positive
+        return res;
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger mod(BigInteger m) {
+        if (m.sign <= 0) {
+            throw new ArithmeticException("BigInteger: modulus not positive");
+        }
+        BigInteger rem = remainder(m);
+        return ((rem.sign < 0) ? rem.add(m) : rem);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public boolean isProbablePrime(int certainty) {
+        return Primality.isProbablePrime(abs(), certainty);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public BigInteger nextProbablePrime() {
+        if (sign < 0) {
+            throw new ArithmeticException("start < 0: " + this);
+        }
+        return Primality.nextProbablePrime(this);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    public static BigInteger probablePrime(int bitLength, Random rnd) {
+        return new BigInteger(bitLength, 100, rnd);
+    }
+
+    /* Private Methods */
+
+    /** Decreases {@code numberLength} if there are zero high elements. */
+    final void cutOffLeadingZeroes() {
+        while ((numberLength > 0) && (digits[--numberLength] == 0))
+            ;
+        if (digits[numberLength++] == 0) {
+            sign = 0;
+        }
+    }
+
+    /** Tests if {@code this.abs()} is equals to {@code ONE} */
+    boolean isOne() {
+        return ((numberLength == 1) && (digits[0] == 1));
+    }
+
+    /**
+     * Puts a big-endian byte array into a little-endian int array 
+     * representing non-negative "digits" of a big integer number.
+     */
+    private void putBytesToIntegers(byte[] byteValues, boolean isNegative) {
+        int bytesLen = byteValues.length;
+        int highBytes = bytesLen & 3;
+        numberLength = (bytesLen >> 2) + ((highBytes == 0) ? 0 : 1);
+        digits = new int[numberLength];
+        int i = 0;
+        // Set the highest element of an int array negative if needed
+        if (isNegative) {
+            digits[numberLength - 1] = -1;
+        }
+        // Put bytes to the int array starting from the end of the byte array
+        while (bytesLen > highBytes) {
+            digits[i++] = (byteValues[--bytesLen] & 0xFF)
+                    | (byteValues[--bytesLen] & 0xFF) << 8
+                    | (byteValues[--bytesLen] & 0xFF) << 16
+                    | (byteValues[--bytesLen] & 0xFF) << 24;
+        }
+        // Put the first bytes in the highest element of the int array
+        for (int j = 0; j < bytesLen; j++) {
+            digits[i] = (digits[i] << 8) | (byteValues[j] & 0xFF);
+        }
+    }
+
+    /**
+     * Returns a clone of {@code this}.
+     * @return a copy of {@code this}, so that {@code equals(clone()) == true}.
+     */
+    @Override
+    protected BigInteger clone() {
+        int[] clonedDigits = new int[numberLength];
+        System.arraycopy(digits, 0, clonedDigits, 0, numberLength);
+        return new BigInteger(sign, numberLength, clonedDigits);
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    private void readObject(ObjectInputStream in) throws IOException,
+            ClassNotFoundException {
+        in.defaultReadObject();
+        sign = signum;
+        putBytesToIntegers(magnitude, false);
+        cutOffLeadingZeroes();
+    }
+
+    /** @ar.org.fitc.spec_ref */
+    private void writeObject(ObjectOutputStream out) throws IOException {
+        signum = signum();
+        magnitude = abs().toByteArray();
+        out.defaultWriteObject();
+    }
+
+}

Propchange: incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigInteger.java
------------------------------------------------------------------------------
    svn:executable = *

Added: incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BitLevel.java
URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BitLevel.java?rev=431881&view=auto
==============================================================================
--- incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BitLevel.java (added)
+++ incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BitLevel.java Wed Aug 16 04:55:59 2006
@@ -0,0 +1,297 @@
+ /*
+  *  Copyright 2005 The Apache Software Foundation or its licensors, as applicable.
+  *
+  *  Licensed under the Apache License, Version 2.0 (the "License");
+  *  you may not use this file except in compliance with the License.
+  *  You may obtain a copy of the License at
+  *
+  *     http://www.apache.org/licenses/LICENSE-2.0
+  *
+  *  Unless required by applicable law or agreed to in writing, software
+  *  distributed under the License is distributed on an "AS IS" BASIS,
+  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+  *  See the License for the specific language governing permissions and
+  *  limitations under the License.
+  */
+package java.math;
+
+/**
+ * Static library that provides all the <b>bit level</b> operations for
+ * {@link BigInteger}. The operations are:
+ * <ul type="circle">
+ * <li>Left Shifting</li>
+ * <li>Right Shifting</li>
+ * <li>Bit clearingting</li>
+ * <li>Bit setting</li>
+ * <li>Bit counting</li>
+ * <li>Bit testing</li>
+ * <li>Getting of the lowest bit setted</li>
+ * </ul>
+ * All operations are provided in immutable way, and some in both mutable and
+ * immutable.
+ * 
+ * @author Daniel Fridlender
+ * @author Matthias Gallé
+ * @author Mariano Heredia
+ * @author Miguel Vasquez
+ */
+class BitLevel {
+
+    /** Just to denote that this class can't be instantied. */
+    private BitLevel() {}
+
+    /**
+     * Converts bits represented by an int array from two's complementary code
+     * to true one and vice versa. Performs ~value + 1.
+     */
+    static int setTrueCoded(int arr[], final int length) {
+        int i;
+        // Until the first set bit, the bits are equal (i.e. 0)
+        for (i = 0; (i < length) && (arr[i] == 0); i++)
+            ;
+        if (i == length) {
+            return 1;
+        }
+        // The digit that cointains the first set bit is (arithmetic) negated
+        arr[i] = -arr[i];
+        // From this position, the bits are (boolean) negated
+        for (i++; i < length; i++) {
+            arr[i] = ~arr[i];
+        }
+        return 0;
+    }
+
+    /** @see BigInteger#bitLength() */
+    static int bitLength(BigInteger val) {
+        if (val.sign == 0) {
+            return 0;
+        }
+        int bLength = (val.numberLength << 5);
+        int highDigit = val.digits[val.numberLength - 1];
+        int i;
+
+        if (val.sign < 0) {
+            for (i = 0; val.digits[i] == 0; i++)
+                ;
+            // We reduce the problem to the positive case.
+            if (i == val.numberLength - 1) {
+                highDigit--;
+            }
+        }
+        // Subtracting all sign bits
+        bLength -= Integer.numberOfLeadingZeros(highDigit);
+        return bLength;
+    }
+
+    /** @see BigInteger#bitCount() */
+    static int bitCount(BigInteger val) {
+        int bCount = 0;
+        int i;
+
+        if (val.sign >= 0) {
+            for (i = 0; i < val.numberLength; i++) {
+                bCount += Integer.bitCount(val.digits[i]);
+            }
+        } else {// (sign < 0)
+            for (i = 0; val.digits[i] == 0; i++)
+                ;
+            // this digit absorbs the carry
+            bCount += Integer.bitCount(-val.digits[i]);
+            for (i++; i < val.numberLength; i++) {
+                bCount += Integer.bitCount(~val.digits[i]);
+            }
+            // We take the complement sum:
+            bCount = (val.numberLength << 5) - bCount;
+        }
+        return bCount;
+    }
+
+    /**
+     * Performs a fast bit testing for positive numbers. The bit to to be tested
+     * must be in the range {@code [0, val.bitLength()-1]}
+     */
+    static boolean testBit(BigInteger val, int n) {
+        // PRE: 0 <= n < val.bitLength()
+        return ((val.digits[n >> 5] & (1 << (n & 31))) != 0);
+    }
+
+    /**
+     * Changes a bit in the BigInteger depending on the operation.
+     * 
+     * @param intCount the number of an element in the array to change bit in
+     * @param bitNumber the bit's number in the intCount element
+     * @param operation's code: 1 for flipBit(), 2 for setBit(), 3 for
+     *        clearBit()
+     */
+    static BigInteger changeBit(BigInteger n, final int intCount,
+            int bitNumber, final int operation) {
+        int resSign = (n.sign == 0) ? 1 : n.sign;
+        int resLength;
+        resLength = Math.max(intCount, n.numberLength);
+        // increase length for a possible carry in the second
+        // BitLevel.setTrueCoded();
+        resLength++;
+        int resDigits[] = new int[resLength];
+        for (int i = n.numberLength; i < resLength; i++) {
+            resDigits[i] = 0;
+        }
+        System.arraycopy(n.digits, 0, resDigits, 0, n.numberLength);
+        if (n.sign < 0) {
+            BitLevel.setTrueCoded(resDigits, resLength);
+        }
+        bitNumber = 1 << bitNumber;
+        switch (operation) {
+            case 1: // flip bit
+                resDigits[intCount] ^= bitNumber;
+                break;
+            case 2: // set bit
+                resDigits[intCount] |= bitNumber;
+                break;
+            case 3: // clear bit
+                resDigits[intCount] &= ~bitNumber;
+                break;
+        }
+        if (n.sign < 0) {
+            BitLevel.setTrueCoded(resDigits, resLength);
+        }
+        BigInteger result = new BigInteger(resSign, resLength, resDigits);
+        result.cutOffLeadingZeroes();
+        return result;
+    }
+
+    /**
+     * Check if there are 1s in the lowest bits of this BigInteger
+     * 
+     * @param numberOfBits the number of the lowest bits to check
+     * @return false if all bits are 0s, true otherwise
+     */
+    static boolean nonZeroDroppedBits(int numberOfBits, int digits[]) {
+        int intCount = numberOfBits >> 5;
+        int bitCount = numberOfBits & 31;
+        int i;
+
+        for (i = 0; (i < intCount) && (digits[i] == 0); i++)
+            ;
+        return ((i != intCount) || (digits[i] << (32 - bitCount) != 0));
+    }
+
+    /** @see BigInteger#shiftLeft(int) */
+    static BigInteger shiftLeft(BigInteger source, int count) {
+        int intCount = count >> 5;
+        count &= 31;
+        int resLength = source.numberLength + intCount + ((count == 0) ? 0 : 1);
+        int resDigits[] = new int[resLength];
+
+        shiftLeft(resDigits, source.digits, intCount, count);
+        BigInteger result = new BigInteger(source.sign, resLength, resDigits);
+        result.cutOffLeadingZeroes();
+        return result;
+    }
+
+    /**
+     * Performs {@code val <<= count}.
+     */
+    static void inplaceShiftLeft(BigInteger val, int count) {
+        int intCount = count >> 5; // count of integers
+        val.numberLength -= intCount;
+        shiftLeft(val.digits, val.digits, intCount, count & 31);
+        val.cutOffLeadingZeroes();
+    }
+
+    /**
+     * Shifts left an array of integers. Total shift distance in bits is
+     * intCount * 32 + count
+     * 
+     * @param result the destination array
+     * @param source the source array
+     * @param intCount the shift distance in integers
+     * @param count an additional shift distance in bits
+     */
+    static void shiftLeft(int result[], int source[], int intCount, int count) {
+        if (count == 0) {
+            System.arraycopy(source, 0, result, intCount, result.length
+                    - intCount);
+        } else {
+            int rightShiftCount = 32 - count;
+
+            result[result.length - 1] = 0;
+            for (int i = result.length - 1; i > intCount; i--) {
+                result[i] |= source[i - intCount - 1] >>> rightShiftCount;
+                result[i - 1] = source[i - intCount - 1] << count;
+            }
+        }
+    }
+
+    /** @see BigInteger#shiftRight(int) */
+    static BigInteger shiftRight(BigInteger source, int count) {
+        int intCount = count >> 5; // count of integers
+        count &= 31; // count of remaining bits
+        if (intCount >= source.numberLength) {
+            return ((source.sign < 0) ? BigInteger.MINUS_ONE : BigInteger.ZERO);
+        }
+        int i;
+        int resLength = source.numberLength - intCount;
+        int resDigits[] = new int[resLength + 1];
+
+        shiftRight(resDigits, resLength, source.digits, intCount, count);
+        if (source.sign < 0) {
+            // Checking if the dropped bits are zeros (the remainder equals to
+            // 0)
+            for (i = 0; (i < intCount) && (source.digits[i] == 0); i++)
+                ;
+            // If the remainder is not zero, add 1 to the result
+            if ((i < intCount)
+                    || ((count > 0) && ((source.digits[i] << (32 - count)) != 0))) {
+                for (i = 0; (i < resLength) && (resDigits[i] == -1); i++) {
+                    resDigits[i] = 0;
+                }
+                if (i == resLength) {
+                    resLength++;
+                }
+                resDigits[i]++;
+            }
+        }
+        BigInteger result = new BigInteger(source.sign, resLength, resDigits);
+        result.cutOffLeadingZeroes();
+        return result;
+    }
+
+    /**
+     * Performs {@code val >>= count} where {@code val} is a positive number.
+     */
+    static void inplaceShiftRight(BigInteger val, int count) {
+        // PRE: val > 0
+        int intCount = count >> 5; // count of integers
+        val.numberLength -= intCount;
+        shiftRight(val.digits, val.numberLength, val.digits, intCount,
+                count & 31);
+        val.cutOffLeadingZeroes();
+    }
+
+    /**
+     * Shifts right an array of integers. Total shift distance in bits is
+     * intCount * 32 + count.
+     * 
+     * @param result the destination array
+     * @param resultLen the destination array's length
+     * @param source the source array
+     * @param intCount the number of elements to be shifted
+     * @param count the number of bits to be shifted
+     */
+    static void shiftRight(int result[], int resultLen, int source[],
+            int intCount, int count) {
+        if (count == 0) {
+            System.arraycopy(source, intCount, result, 0, resultLen);
+        } else {
+            int i;
+            int leftShiftCount = 32 - count;
+
+            for (i = 0; i < resultLen - 1; i++) {
+                result[i] = (source[i + intCount] >>> count)
+                        | (source[i + intCount + 1] << leftShiftCount);
+            }
+            result[i] = (source[i + intCount] >>> count);
+        }
+    }
+
+}

Propchange: incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BitLevel.java
------------------------------------------------------------------------------
    svn:executable = *

Added: incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Conversion.java
URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Conversion.java?rev=431881&view=auto
==============================================================================
--- incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Conversion.java (added)
+++ incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Conversion.java Wed Aug 16 04:55:59 2006
@@ -0,0 +1,421 @@
+/*
+ *  Copyright 2005 The Apache Software Foundation or its licensors, as applicable.
+ *
+ *  Licensed under the Apache License, Version 2.0 (the "License");
+ *  you may not use this file except in compliance with the License.
+ *  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+package java.math;
+
+/**
+ * Static library that provides {@link BigInteger} base conversion from/to any
+ * integer represented in an {@link java.lang.String} Object.
+ * 
+ * @author Daniel Fridlender
+ * @author Matthias Gallé
+ * @author Mariano Heredia
+ * @author Miguel Vasquez
+ */
+class Conversion {
+
+    /** Just to denote that this class can't be instantied */
+    private Conversion() {}
+
+    /**
+     * Holds the maximal exponent for each radix, so that radix<sup>digitFitInInt[radix]</sup>
+     * fit in an {@code int} (32 bits).
+     */
+    private static final int[] digitFitInInt = { -1, -1, 31, 19, 15, 13, 12,
+            11, 10, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7, 7, 7, 7, 6, 6, 6, 6, 6, 6, 6,
+            6, 6, 6, 6, 6, 6, 6, 5 };
+
+    /**
+     * bigRadices values are precomputed maximal powers of radices (integer
+     * numbers from 2 to 36) that fit into unsigned int (32 bits). bigRadices[0] =
+     * 2 ^ 31, bigRadices[8] = 10 ^ 9, etc.
+     */
+
+    private static final int bigRadices[] = { -2147483648, 1162261467,
+            1073741824, 1220703125, -2118184960, 1977326743, 1073741824,
+            387420489, 1000000000, 214358881, 429981696, 815730721, 1475789056,
+            170859375, 268435456, 410338673, 612220032, 893871739, 1280000000,
+            1801088541, 113379904, 148035889, 191102976, 244140625, 308915776,
+            387420489, 481890304, 594823321, 729000000, 887503681, 1073741824,
+            1291467969, 1544804416, 1838265625, 60466176 };
+
+    /** @see BigInteger#BigInteger(String, int) */
+    static BigInteger string2BigInteger(String val, int radix) {
+        int sign;
+        int[] digits;
+        int numberLength;
+        int stringLength = val.length();
+        int startChar;
+        int endChar = stringLength;
+
+        if (val.charAt(0) == '-') {
+            sign = -1;
+            startChar = 1;
+            stringLength--;
+        } else {
+            sign = 1;
+            startChar = 0;
+        }
+        /*
+         * We use the following algorithm: split a string into portions of n
+         * characters and convert each portion to an integer according to the
+         * radix. Then convert an exp(radix, n) based number to binary using the
+         * multiplication method. See D. Knuth, The Art of Computer Programming,
+         * vol. 2.
+         */
+
+        int charsPerInt = digitFitInInt[radix];
+        int bigRadixDigitsLength = stringLength / charsPerInt;
+        int topChars = stringLength % charsPerInt;
+
+        if (topChars != 0) {
+            bigRadixDigitsLength++;
+        }
+        digits = new int[bigRadixDigitsLength];
+        // Get the maximal power of radix that fits in int
+        int bigRadix = bigRadices[radix - 2];
+        // Parse an input string and accumulate the BigInteger's magnitude
+        int digitIndex = 0; // index of digits array
+        int substrEnd = startChar + ((topChars == 0) ? charsPerInt : topChars);
+        int newDigit;
+        BigInteger result;
+
+        for (int substrStart = startChar; substrStart < endChar; substrStart = substrEnd, substrEnd = substrStart
+                + charsPerInt) {
+            int bigRadixDigit = Integer.parseInt(val.substring(substrStart,
+                    substrEnd), radix);
+            newDigit = Multiplication.multiplyByInt(digits, digitIndex,
+                    bigRadix);
+            newDigit += Elementary
+                    .inplaceAdd(digits, digitIndex, bigRadixDigit);
+            digits[digitIndex++] = newDigit;
+        }
+        numberLength = digitIndex;
+        result = new BigInteger(sign, numberLength, digits);
+        result.cutOffLeadingZeroes();
+        return result;
+    }
+
+    /** @see BigInteger#toString(int) */
+    static String bigInteger2String(BigInteger val, int radix) {
+        int sign = val.sign;
+        int numberLength = val.numberLength;
+        int digits[] = val.digits;
+
+        if (sign == 0) {
+            return "0";
+        }
+        if (numberLength == 1) {
+            int highDigit = digits[numberLength - 1];
+            long v = (long) highDigit & 0xFFFFFFFFL;
+            if (sign < 0) {
+                v = -v;
+            }
+            return Long.toString(v, radix);
+        }
+        if ((radix == 10) || (radix < Character.MIN_RADIX)
+                || (radix > Character.MAX_RADIX)) {
+            return val.toString();
+        }
+        double bitsForRadixDigit;
+        bitsForRadixDigit = Math.log(radix) / Math.log(2);
+        int resLengthInChars = (int) (val.abs().bitLength() / bitsForRadixDigit + ((sign < 0) ? 1
+                : 0)) + 1;
+
+        char result[] = new char[resLengthInChars];
+        int currentChar = resLengthInChars;
+        int resDigit;
+        if (radix != 16) {
+            int temp[] = new int[numberLength];
+            System.arraycopy(digits, 0, temp, 0, numberLength);
+            int tempLen = numberLength;
+            int charsPerInt = digitFitInInt[radix];
+            int i;
+            // get the maximal power of radix that fits in int
+            int bigRadix = bigRadices[radix - 2];
+            while (true) {
+                // divide the array of digits by bigRadix and convert remainders
+                // to characters collecting them in the char array
+                resDigit = Division.divideArrayByInt(temp, temp, tempLen,
+                        bigRadix);
+                int previous = currentChar;
+                do {
+                    result[--currentChar] = Character.forDigit(
+                            resDigit % radix, radix);
+                } while (((resDigit /= radix) != 0) && (currentChar != 0));
+                int delta = charsPerInt - previous + currentChar;
+                for (i = 0; i < delta && currentChar > 0; i++) {
+                    result[--currentChar] = '0';
+                }
+                for (i = tempLen - 1; (i > 0) && (temp[i] == 0); i--)
+                    ;
+                tempLen = i + 1;
+                if ((tempLen == 1) && (temp[0] == 0)) { // the quotient is 0
+                    break;
+                }
+            }
+        } else {
+            // radix == 16
+            for (int i = 0; i < numberLength; i++) {
+                for (int j = 0; (j < 8) && (currentChar > 0); j++) {
+                    resDigit = digits[i] >> (j << 2) & 0xf;
+                    result[--currentChar] = Character.forDigit(resDigit, 16);
+                }
+            }
+        }
+        while (result[currentChar] == '0') {
+            currentChar++;
+        }
+        if (sign == -1) {
+            result[--currentChar] = '-';
+        }
+        return new String(result, currentChar, resLengthInChars - currentChar);
+    }
+
+    /**
+     * Builds the correspondent {@code String} representation of {@code val}
+     * being scaled by {@code scale}.
+     * 
+     * @see BigInteger#toString()
+     * @see BigDecimal#toString()
+     */
+    static String toDecimalScaledString(BigInteger val, int scale) {
+        int sign = val.sign;
+        int numberLength = val.numberLength;
+        int digits[] = val.digits;
+        int resLengthInChars;
+        int currentChar;
+        char result[];
+
+        if (sign == 0) {
+            switch (scale) {
+                case 0:
+                    return "0";
+                case 1:
+                    return "0.0";
+                case 2:
+                    return "0.00";
+                case 3:
+                    return "0.000";
+                case 4:
+                    return "0.0000";
+                case 5:
+                    return "0.00000";
+                case 6:
+                    return "0.000000";
+                default:
+                    StringBuffer result1 = new StringBuffer();
+                    if (scale < 0) {
+                        result1.append("0E+");
+                    } else {
+                        result1.append("0E");
+                    }
+                    result1.append(-scale);
+                    return result1.toString();
+            }
+        } else {
+            // one 32-bit unsigned value may contains 10 decimal digits
+            resLengthInChars = numberLength * 10 + 1 + 7;
+            // Explanation why +1+7:
+            // +1 - one char for sign if needed.
+            // +7 - For "special case 2" (see below) we have 7 free chars for
+            // inserting necessary scaled digits.
+            result = new char[resLengthInChars + 1];
+            // alocated [resLengthInChars+1] charactes.
+            // a free latest character may be used for "special case 1" (see
+            // below)
+            currentChar = resLengthInChars;
+            if (numberLength == 1) {
+                int highDigit = digits[0];
+                if (highDigit < 0) {
+                    long v = (long) highDigit & 0xFFFFFFFFL;
+                    do {
+                        long prev = v;
+                        v /= 10;
+                        result[--currentChar] = (char) (0x0030 + ((int) (prev - v * 10)));
+                    } while (v != 0);
+                } else {
+                    int v = highDigit;
+                    do {
+                        int prev = v;
+                        v /= 10;
+                        result[--currentChar] = (char) (0x0030 + (prev - v * 10));
+                    } while (v != 0);
+                }
+            } else {
+                int temp[] = new int[numberLength];
+                int tempLen = numberLength;
+                System.arraycopy(digits, 0, temp, 0, tempLen);
+                BIG_LOOP: while (true) {
+                    // divide the array of digits by bigRadix and convert
+                    // remainders
+                    // to characters collecting them in the char array
+                    long result11 = 0;
+                    for (int i1 = tempLen - 1; i1 >= 0; i1--) {
+                        long temp1 = (result11 << 32)
+                                + ((long) temp[i1] & 0xFFFFFFFFL);
+                        long res = divideLongByBillion(temp1);
+                        temp[i1] = (int) res;
+                        result11 = (int) (res >> 32);
+                    }
+                    int resDigit = (int) result11;
+                    int previous = currentChar;
+                    do {
+                        result[--currentChar] = (char) (0x0030 + (resDigit % 10));
+                    } while (((resDigit /= 10) != 0) && (currentChar != 0));
+                    int delta = 9 - previous + currentChar;
+                    for (int i = 0; (i < delta) && (currentChar > 0); i++) {
+                        result[--currentChar] = '0';
+                    }
+                    int j = tempLen - 1;
+                    for (; temp[j] == 0; j--) {
+                        if (j == 0) { // means temp[0] == 0
+                            break BIG_LOOP;
+                        }
+                    }
+                    tempLen = j + 1;
+                }
+                while (result[currentChar] == '0') {
+                    currentChar++;
+                }
+            }
+        }
+        boolean negNumber = (sign < 0);
+        int exponent = resLengthInChars - currentChar - scale - 1;
+        if (scale == 0) {
+            if (negNumber) {
+                result[--currentChar] = '-';
+            }
+            return new String(result, currentChar, resLengthInChars
+                    - currentChar);
+        }
+        if ((scale > 0) && (exponent >= -6)) {
+            if (exponent >= 0) {
+                // special case 1
+                int insertPoint = currentChar + exponent;
+                for (int j = resLengthInChars - 1; j >= insertPoint; j--) {
+                    result[j + 1] = result[j];
+                }
+                result[++insertPoint] = '.';
+                if (negNumber) {
+                    result[--currentChar] = '-';
+                }
+                return new String(result, currentChar, resLengthInChars
+                        - currentChar + 1);
+            } else {
+                // special case 2
+                for (int j = 2; j < -exponent + 1; j++) {
+                    result[--currentChar] = '0';
+                }
+                result[--currentChar] = '.';
+                result[--currentChar] = '0';
+                if (negNumber) {
+                    result[--currentChar] = '-';
+                }
+                return new String(result, currentChar, resLengthInChars
+                        - currentChar);
+            }
+        } else {
+            int startPoint = currentChar + 1;
+            int endPoint = resLengthInChars;
+            StringBuffer result1 = new StringBuffer(16 + endPoint - startPoint);
+            if (negNumber) {
+                result1.append('-');
+            }
+            if (endPoint - startPoint >= 1) {
+                result1.append(result[currentChar]);
+                result1.append('.');
+                result1.append(result, currentChar + 1, resLengthInChars
+                        - currentChar - 1);
+            } else {
+                result1.append(result, currentChar, resLengthInChars
+                        - currentChar);
+            }
+            result1.append('E');
+            if (exponent > 0) {
+                result1.append('+');
+            }
+            result1.append(Integer.toString(exponent));
+            return result1.toString();
+        }
+    }
+
+    static long divideLongByBillion(long a) {
+        long quot;
+        long rem;
+
+        if (a >= 0) {
+            long bLong = 1000000000L;
+            quot = (a / bLong);
+            rem = (a % bLong);
+        } else {
+            /*
+             * Make the dividend positive shifting it right by 1 bit then get
+             * the quotient an remainder and correct them properly
+             */
+            long aPos = a >>> 1;
+            long bPos = 1000000000L >>> 1;
+            quot = aPos / bPos;
+            rem = aPos % bPos;
+            // double the remainder and add 1 if 'a' is odd
+            rem = (rem << 1) + (a & 1);
+        }
+        return ((rem << 32) | (quot & 0xFFFFFFFFL));
+    }
+
+    /** @see BigInteger#doubleValue() */
+    static double bigInteger2Double(BigInteger val) {
+        // val.bitLength() < 64
+        if ((val.numberLength < 2)
+                || ((val.numberLength == 2) && (val.digits[1] > 0))) {
+            return val.longValue();
+        }
+        // val.bitLength() >= 33 * 32 > 1024
+        if (val.numberLength > 32) {
+            return ((val.sign > 0) ? Double.POSITIVE_INFINITY
+                    : Double.NEGATIVE_INFINITY);
+        }
+        int bitLen = val.abs().bitLength();
+        long exponent = bitLen - 1;
+        int delta = bitLen - 54;
+        // We need 54 top bits from this, the 53th bit is always 1 in lVal.
+        long lVal = val.abs().shiftRight(delta).longValue();
+        /*
+         * Take 53 bits from lVal to mantissa. The least significant bit is
+         * needed for rounding.
+         */
+        long mantissa = lVal & 0x1FFFFFFFFFFFFFL;
+        if (exponent == 1023) {
+            if (mantissa == 0X1FFFFFFFFFFFFFL) {
+                return ((val.sign > 0) ? Double.POSITIVE_INFINITY
+                        : Double.NEGATIVE_INFINITY);
+            }
+            if (mantissa == 0x1FFFFFFFFFFFFEL) {
+                return ((val.sign > 0) ? Double.MAX_VALUE : -Double.MAX_VALUE);
+            }
+        }
+        // Round the mantissa
+        if (((mantissa & 1) == 1)
+                && (((mantissa & 2) == 2) || BitLevel.nonZeroDroppedBits(delta,
+                        val.digits))) {
+            mantissa += 2;
+        }
+        mantissa >>= 1; // drop the rounding bit
+        long resSign = (val.sign < 0) ? 0x8000000000000000L : 0;
+        exponent = ((long) (1023 + exponent) << 52) & 0x7FF0000000000000L;
+        long result = resSign | exponent | mantissa;
+        return Double.longBitsToDouble(result);
+    }
+}

Propchange: incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Conversion.java
------------------------------------------------------------------------------
    svn:executable = *

Added: incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Division.java
URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Division.java?rev=431881&view=auto
==============================================================================
--- incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Division.java (added)
+++ incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Division.java Wed Aug 16 04:55:59 2006
@@ -0,0 +1,765 @@
+/*
+ *  Copyright 2005 The Apache Software Foundation or its licensors, as applicable.
+ *
+ *  Licensed under the Apache License, Version 2.0 (the "License");
+ *  you may not use this file except in compliance with the License.
+ *  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+
+package java.math;
+
+/**
+ * Static library that provides all operations related with division and modular
+ * arithmetic to {@link BigInteger}. Some methos are provided in both mutable
+ * and immutable way. There are several variants provided listed below:
+ * 
+ * <ul type="circle">
+ * <li> <b>Division</b>
+ * <ul type="circle">
+ * <li>{@link BigInteger} division and remainder by {@link BigInteger}.</li>
+ * <li>{@link BigInteger} division and remainder by {@code int}.</li>
+ * <li><i>gcd</i> between {@link BigInteger} numbers.</li>
+ * </ul>
+ * </li>
+ * <li> <b>Modular arithmetic </b>
+ * <ul type="circle">
+ * <li>Modular exponentiation between {@link BigInteger} numbers.</li>
+ * <li>Modular inverse of a {@link BigInteger} numbers.</li>
+ * </ul>
+ * </li>
+ * </ul>
+ * 
+ * @author Daniel Fridlender
+ * @author Matthias Gallé
+ * @author Mariano Heredia
+ * @author Miguel Vasquez
+ */
+class Division {
+
+    /**
+     * Divides the array 'a' by the array 'b' and gets the quotient and the
+     * remainder. Implements the Knuth's division algorithm. See D. Knuth, The
+     * Art of Computer Programming, vol. 2. Steps D1-D8 correspond the steps in
+     * the algorithm description.
+     * 
+     * @param quot the quotient
+     * @param quotLength the quotient's length
+     * @param a the dividend
+     * @param aLength the dividend's length
+     * @param b the divisor
+     * @param bLength the divisor's length
+     * @return the remainder
+     */
+    static int[] divide(int quot[], int quotLength, int a[], int aLength,
+            int b[], int bLength) {
+
+        int normA[] = new int[aLength + 1]; // the normalized dividend
+        // an extra byte is needed for correct shift
+        int normB[] = new int[bLength + 1]; // the normalized divisor;
+        int normBLength = bLength;
+        /*
+         * Step D1: normalize a and b and put the results to a1 and b1 the
+         * normalized divisor's first digit must be >= 2^31
+         */
+        int divisorShift = Integer.numberOfLeadingZeros(b[bLength - 1]);
+        if (divisorShift != 0) {
+            BitLevel.shiftLeft(normB, b, 0, divisorShift);
+            BitLevel.shiftLeft(normA, a, 0, divisorShift);
+        } else {
+            System.arraycopy(a, 0, normA, 0, aLength);
+            System.arraycopy(b, 0, normB, 0, bLength);
+        }
+        int firstDivisorDigit = normB[normBLength - 1];
+        // Step D2: set the quotient index
+        int i = quotLength - 1;
+        int j = aLength;
+
+        while (i >= 0) {
+            // Step D3: calculate a guess digit guessDigit
+            int guessDigit = 0;
+            if (normA[j] == firstDivisorDigit) {
+                // set guessDigit to the largest unsigned int value
+                guessDigit = -1;
+            } else {
+                long product = ((((long) normA[j] & 0xffffffffL) << 32) + ((long) normA[j - 1] & 0xffffffffL));
+                long res = Division.divideLongByInt(product, firstDivisorDigit);
+                guessDigit = (int) res; // the quotient of divideLongByInt
+                int rem = (int) (res >> 32); // the remainder of
+                                                // divideLongByInt
+                // decrease guessDigit by 1 while leftHand > rightHand
+                if (guessDigit != 0) {
+                    long leftHand = 0;
+                    long rightHand = 0;
+                    boolean rOverflowed = false;
+                    guessDigit++; // to have the proper value in the loop
+                                    // below
+                    do {
+                        guessDigit--;
+                        if (rOverflowed) {
+                            break;
+                        }
+                        // leftHand always fits in an unsigned long
+                        leftHand = ((long) guessDigit & 0xffffffffL)
+                                * ((long) normB[normBLength - 2] & 0xffffffffL);
+                        /*
+                         * rightHand can overflow; in this case the loop
+                         * condition will be true in the next step of the loop
+                         */
+                        rightHand = ((long) rem << 32)
+                                + ((long) normA[j - 2] & 0xffffffffL);
+                        long longR = ((long) rem & 0xffffffffL)
+                                + ((long) firstDivisorDigit & 0xffffffffL);
+                        /*
+                         * checks that longR does not fit in an unsigned int;
+                         * this ensures that rightHand will overflow unsigned
+                         * long in the next step
+                         */
+                        if (Integer.numberOfLeadingZeros((int) (longR >>> 32)) < 32) {
+                            rOverflowed = true;
+                        } else {
+                            rem = (int) longR;
+                        }
+                    } while (((leftHand ^ 0x8000000000000000L) > (rightHand ^ 0x8000000000000000L)));
+                }
+            }
+            // Step D4: multiply normB by guessDigit and subtract the production
+            // from normA.
+            if (guessDigit != 0) {
+                int borrow = Division.multiplyAndSubtract(normA, j
+                        - normBLength, normB, normBLength,
+                        (long) guessDigit & 0xffffffffL);
+                // Step D5: check the borrow
+                if (borrow != 0) {
+                    // Step D6: compensating addition
+                    guessDigit--;
+                    long carry = 0;
+                    for (int k = 0; k < normBLength; k++) {
+                        carry += ((long) normA[j - normBLength + k] & 0xffffffffL)
+                                + ((long) normB[k] & 0xffffffffL);
+                        normA[j - normBLength + k] = (int) carry;
+                        carry >>>= 32;
+                    }
+                }
+            }
+            if (quot != null) {
+                quot[i] = (int) guessDigit;
+            }
+            // Step D7
+            j--;
+            i--;
+        }
+        /*
+         * Step D8: we got the remainder in normA. Denormalize it id needed
+         */
+        if (divisorShift != 0) {
+            // reuse normB
+            BitLevel.shiftRight(normB, normBLength, normA, 0, divisorShift);
+            return normB;
+        } else {
+            System.arraycopy(normA, 0, normB, 0, bLength);
+            return normA;
+        }
+    }
+
+    /**
+     * Divides an array by an integer value. Implements the Knuth's division
+     * algorithm. See D. Knuth, The Art of Computer Programming, vol. 2.
+     * 
+     * @param dest the quotient
+     * @param src the dividend
+     * @param srcLength the length of the dividend
+     * @param divisor the divisor
+     * @return remainder
+     */
+    static int divideArrayByInt(int dest[], int src[], final int srcLength,
+            final int divisor) {
+
+        long rem = 0;
+        long bLong = (long) divisor & 0xffffffffL;
+
+        for (int i = srcLength - 1; i >= 0; i--) {
+            long temp = (rem << 32) | ((long) src[i] & 0xffffffffL);
+            long quot;
+            if (temp >= 0) {
+                quot = (temp / bLong);
+                rem = (temp % bLong);
+            } else {
+                /*
+                 * make the dividend positive shifting it right by 1 bit then
+                 * get the quotient an remainder and correct them properly
+                 */
+                long aPos = temp >>> 1;
+                long bPos = divisor >>> 1;
+                quot = aPos / bPos;
+                rem = aPos % bPos;
+                // double the remainder and add 1 if a is odd
+                rem = (rem << 1) + (temp & 1);
+                if ((divisor & 1) != 0) {
+                    // the divisor is odd
+                    if (quot <= rem) {
+                        rem -= quot;
+                    } else {
+                        if (quot - rem <= bLong) {
+                            rem += bLong - quot;
+                            quot -= 1;
+                        } else {
+                            rem += (bLong << 1) - quot;
+                            quot -= 2;
+                        }
+                    }
+                }
+            }
+            dest[i] = (int) (quot & 0xffffffffL);
+        }
+        return (int) rem;
+    }
+
+    /**
+     * Divides an array by an integer value. Implements the Knuth's division
+     * algorithm. See D. Knuth, The Art of Computer Programming, vol. 2.
+     * 
+     * @param src the dividend
+     * @param srcLength the length of the dividend
+     * @param divisor the divisor
+     * @return remainder
+     */
+    static int remainderArrayByInt(int src[], final int srcLength,
+            final int divisor) {
+
+        long result = 0;
+
+        for (int i = srcLength - 1; i >= 0; i--) {
+            long temp = (result << 32) + ((long) src[i] & 0xffffffffL);
+            long res = divideLongByInt(temp, divisor);
+            result = (int) (res >> 32);
+        }
+        return (int) result;
+    }
+
+    /**
+     * Divides a <code>BigInteger</code> by a signed <code>int</code> and
+     * returns the remainder.
+     * 
+     * @param dividend the BigInteger to be divided. Must be non-negative.
+     * @param divisor a signed int
+     * @return divide % divisor
+     */
+    static int remainder(BigInteger dividend, int divisor) {
+        return remainderArrayByInt(dividend.digits, dividend.numberLength,
+                divisor);
+    }
+
+    /**
+     * Divides an unsigned long a by an unsigned int b. It is supposed that the
+     * most significant bit of b is set to 1, i.e. b < 0
+     * 
+     * @param a the dividend
+     * @param b the divisor
+     * @return the long value containing the unsigned integer remainder in the
+     *         left half and the unsigned integer quotient in the right half
+     */
+    static long divideLongByInt(long a, int b) {
+        long quot;
+        long rem;
+        long bLong = (long) b & 0xffffffffL;
+
+        if (a >= 0) {
+            quot = (a / bLong);
+            rem = (a % bLong);
+        } else {
+            /*
+             * Make the dividend positive shifting it right by 1 bit then get
+             * the quotient an remainder and correct them properly
+             */
+            long aPos = a >>> 1;
+            long bPos = b >>> 1;
+            quot = aPos / bPos;
+            rem = aPos % bPos;
+            // double the remainder and add 1 if a is odd
+            rem = (rem << 1) + (a & 1);
+            if ((b & 1) != 0) { // the divisor is odd
+                if (quot <= rem) {
+                    rem -= quot;
+                } else {
+                    if (quot - rem <= bLong) {
+                        rem += bLong - quot;
+                        quot -= 1;
+                    } else {
+                        rem += (bLong << 1) - quot;
+                        quot -= 2;
+                    }
+                }
+            }
+        }
+        return (rem << 32) | (quot & 0xffffffffL);
+    }
+
+    /**
+     * Computes the quotient and the remainder after a divison by an {@code int}
+     * number.
+     * 
+     * @return an array of the form {@code [quotient, remainder]}.
+     */
+    static BigInteger[] divideAndRemainderByInteger(BigInteger val,
+            int divisor, int divisorSign) {
+        // res[0] is a quotient and res[1] is a remainder:
+        int[] valDigits = val.digits;
+        int valLen = val.numberLength;
+        int valSign = val.sign;
+        if (valLen == 1) {
+            long a = ((long) valDigits[0] & 0xffffffffL);
+            long b = ((long) divisor & 0xffffffffL);
+            long quo = a / b;
+            long rem = a % b;
+            if (valSign != divisorSign) {
+                quo = -quo;
+            }
+            if (valSign < 0) {
+                rem = -rem;
+            }
+            return new BigInteger[] { BigInteger.valueOf(quo),
+                    BigInteger.valueOf(rem) };
+        } else {
+            int quotientLength = valLen;
+            int quotientSign = ((valSign == divisorSign) ? 1 : -1);
+            int quotientDigits[] = new int[quotientLength];
+            int remainderDigits[];
+            remainderDigits = new int[] { Division.divideArrayByInt(
+                    quotientDigits, valDigits, valLen, divisor) };
+            BigInteger result0 = new BigInteger(quotientSign, quotientLength,
+                    quotientDigits);
+            BigInteger result1 = new BigInteger(valSign, 1, remainderDigits);
+            result0.cutOffLeadingZeroes();
+            result1.cutOffLeadingZeroes();
+            return new BigInteger[] { result0, result1 };
+        }
+    }
+
+    /**
+     * Multipies an array by int and subtracts it from a subarray of another
+     * array.
+     * 
+     * @param a the array to subtract from
+     * @param start the start element of the subarray of a
+     * @param b the array to be multiplied and subtracted
+     * @param bLen the length of b
+     * @param c the multiplier of b
+     * @return the carry element of subtraction
+     */
+    static int multiplyAndSubtract(int a[], int start, int b[], int bLen, long c) {
+        int i;
+        int carry = 0;
+        long product;
+        int productInt;
+
+        for (i = 0; i < bLen; i++) {
+            product = c * ((long) b[i] & 0xffffffffL);
+            productInt = (int) product;
+            productInt += carry;
+            carry = (int) (product >> 32)
+                    + ((productInt ^ 0x80000000) < (carry ^ 0x80000000) ? 1 : 0);
+            productInt = a[start + i] - productInt;
+            if ((productInt ^ 0x80000000) > (a[start + i] ^ 0x80000000)) {
+                carry++;
+            }
+            a[start + i] = productInt;
+        }
+        product = ((long) a[start + i] & 0xffffffffL)
+                - ((long) carry & 0xffffffffL);
+        a[start + i] = (int) product;
+        carry = (int) (product >> 32); // -1 or 0
+        return carry;
+    }
+
+    /**
+     * Return the greatest common divisor of op1 and op2, based in The Binary
+     * GCD Algorithm of D. Knuth.
+     * 
+     * @param op1 must be greater than zero
+     * @param op2 must be greater than zero
+     * @see BigInteger#gcd(BigInteger)
+     * @ar.org.fitc.ref "The Art of Computer Programming Vo.2, Section 4.5.2,
+     *                  Algorithm B by D. Knuth."
+     * @return {@code GCD(op1, op2)}
+     */
+    static BigInteger gcdBinary(BigInteger op1, BigInteger op2) {
+        // PRE: (op1 > 0) and (op2 > 0)
+        /*
+         * Divide both number the maximal possible times by 2 without rounding
+         * gcd(2*a, 2*b) = 2 * gcd(a,n)
+         */
+        int lsb1 = op1.getLowestSetBit();
+        int lsb2 = op2.getLowestSetBit();
+        int pow2Count = Math.min(lsb1, lsb2);
+
+        if (lsb1 != 0) {
+            BitLevel.inplaceShiftRight(op1, lsb1);
+        }
+        if (lsb2 != 0) {
+            BitLevel.inplaceShiftRight(op2, lsb2);
+        }
+        do {// gcd(2*k+1,2*n) = gcd(2*k+1, n)
+            lsb1 = op1.getLowestSetBit();
+            if (lsb1 != 0) {
+                BitLevel.inplaceShiftRight(op1, lsb1);
+            }
+            // gcd(2*n,2*k+1) = gcd(n,2*k+1)
+            lsb2 = op2.getLowestSetBit();
+            if (lsb2 != 0) {
+                BitLevel.inplaceShiftRight(op2, lsb2);
+            }
+            if (op1.compareTo(op2) >= BigInteger.EQUALS) {
+                Elementary.inplaceSubtract(op1, op2);
+            } else {
+                Elementary.inplaceSubtract(op2, op1);
+            }
+        } while (op1.sign != 0);
+        return op2.shiftLeft(pow2Count);
+    }
+
+    /**
+     * Performs the same as {@link #gcdBinary(BigInteger, BigInteger)}, but
+     * with numbers of 63 bits, represented in positives values of {@code long}
+     * type.
+     * 
+     * @param op1 a postive number
+     * @param op2 a postive number
+     * @see #gcdBinary(BigInteger, BigInteger)
+     * @return <code>GCD(op1, op2)</code>
+     */
+    static long gcdBinary(long op1, long op2) {
+        // PRE: (op1 > 0) and (op2 > 0)
+        int lsb1 = Long.numberOfTrailingZeros(op1);
+        int lsb2 = Long.numberOfTrailingZeros(op2);
+        int pow2Count = Math.min(lsb1, lsb2);
+
+        if (lsb1 != 0) {
+            op1 >>>= lsb1;
+        }
+        if (lsb2 != 0) {
+            op2 >>>= lsb2;
+        }
+        do {
+            lsb1 = Long.numberOfTrailingZeros(op1);
+            if (lsb1 != 0) {
+                op1 >>>= lsb1;
+            }
+            lsb2 = Long.numberOfTrailingZeros(op2);
+            if (lsb2 != 0) {
+                op2 >>>= lsb2;
+            }
+            if (op1 >= op2) {
+                op1 -= op2;
+            } else {
+                op2 -= op1;
+            }
+        } while (op1 != 0);
+        return (op2 << pow2Count);
+    }
+
+    /**
+     * Implements the "Shifting Euclidean modular inverse algorithm".
+     * 
+     * @see BigInteger#modInverse(BigInteger)
+     * @param a a positive number
+     * @param m a positive modulus
+     * @ar.org.fitc.ref "Laszlo Hars - Modular Inverse Algorithms Without
+     *                  Multiplications for Cryptographic Applications"
+     */
+    static BigInteger modInverse(BigInteger a, BigInteger m) {
+        // PRE: (a > 0) and (m > 0)
+        BigInteger u, v, r, s, temp;
+        // u = MAX(a,m), v = MIN(a,m)
+        if (a.compareTo(m) == BigInteger.LESS) {
+            u = m;
+            v = a;
+            r = BigInteger.ZERO;
+            s = BigInteger.ONE;
+        } else {
+            v = m;
+            u = a;
+            s = BigInteger.ZERO;
+            r = BigInteger.ONE;
+        }
+        int uLen = u.bitLength();
+        int vLen = v.bitLength();
+        int f = uLen - vLen;
+
+        while (vLen > 1) {
+            if (u.sign == v.sign) {
+                u = u.subtract(v.shiftLeft(f));
+                r = r.subtract(s.shiftLeft(f));
+            } else {
+                u = u.add(v.shiftLeft(f));
+                r = r.add(s.shiftLeft(f));
+            }
+            uLen = u.abs().bitLength();
+            vLen = v.abs().bitLength();
+            f = uLen - vLen;
+            if (f < 0) {
+                // SWAP(u,v)
+                temp = u;
+                u = v;
+                v = temp;
+                // SWAP(r,s)
+                temp = r;
+                r = s;
+                s = temp;
+
+                f = -f;
+                vLen = uLen;
+            }
+        }
+        if (v.sign == 0) {
+            return BigInteger.ZERO;
+        }
+        if (v.sign < 0) {
+            s = s.negate();
+        }
+        if (s.compareTo(m) == BigInteger.GREATER) {
+            return s.subtract(m);
+        }
+        if (s.sign < 0) {
+            return s.add(m);
+        }
+        return s; // a^(-1) mod m
+    }
+
+    /**
+     * Performs modular exponentiation using the Montgomery Reduction. It
+     * requires that all parameters be postivive and the mudulus be odd. Based
+     * in <i>The square and multiply algorithm and the Montgomery Reduction (C.
+     * K. Koc - Analyzing and Comparing Montgomery Multiplication Algorithms)</i>
+     * 
+     * @see BigInteger#modPow(BigInteger, BigInteger)
+     * @see #monPro(BigInteger, BigInteger, BigInteger, long)
+     * @ar.org.fitc.ref "C. K. Koc - Analyzing and Comparing Montgomery
+     *                  Multiplication Algorithms"
+     */
+    static BigInteger oddModPow(BigInteger base, BigInteger exponent,
+            BigInteger modulus) {
+        // PRE: (base > 0), (exponent > 0), (modulus > 0) and (odd modulus)
+        int k = (modulus.numberLength << 5); // r = 2^k
+        // n-residue of base [base * r (mod modulus)]
+        BigInteger a2 = base.shiftLeft(k).mod(modulus);
+        // n-residue of base [1 * r (mod modulus)]
+        BigInteger x2 = BigInteger.ZERO.setBit(k).mod(modulus);
+        // Compute (modulus[0]^(-1)) (mod 2^32) for odd modulus
+        long m0 = modulus.digits[0] & 0xFFFFFFFFL;
+        long n2 = 1L; // this is n'[0]
+        long powerOfTwo = 2L;
+
+        do {
+            if (((m0 * n2) & powerOfTwo) != 0) {
+                n2 |= powerOfTwo;
+            }
+            powerOfTwo <<= 1;
+        } while (powerOfTwo < 0x100000000L);
+        n2 = -n2;
+
+        for (int i = exponent.bitLength() - 1; i >= 0; i--) {
+            x2 = monPro(x2, x2, modulus, n2);
+            if (BitLevel.testBit(exponent, i)) {
+                x2 = monPro(x2, a2, modulus, n2);
+            }
+        }
+        return monPro(x2, BigInteger.ONE, modulus, n2);
+    }
+
+    /**
+     * Performs modular exponentiation using the Montgomery Reduction. It
+     * requires that all parameters be postivive and the mudulus be even. Based
+     * <i>The square and multiply algorithm and the Montgomery Reduction C. K.
+     * Koc - Montgomery Reduction with Even Modulus</i>. The square and
+     * multiply algorithm and the Montgomery Reduction.
+     * 
+     * @ar.org.fitc.ref "C. K. Koc - Montgomery Reduction with Even Modulus"
+     * @see BigInteger#modPow(BigInteger, BigInteger)
+     */
+    static BigInteger evenModPow(BigInteger base, BigInteger exponent,
+            BigInteger modulus) {
+        // PRE: (base > 0), (exponent > 0), (modulus > 0) and (modulus even)
+        // STEP 1: Obtain the factorization 'modulus'= q * 2^j.
+        int j = modulus.getLowestSetBit();
+        BigInteger q = modulus.shiftRight(j);
+
+        // STEP 2: Compute x1 := base^exponent (mod q).
+        BigInteger x1 = oddModPow(base, exponent, q);
+
+        // STEP 3: Compute x2 := base^exponent (mod 2^j).
+        BigInteger x2 = pow2ModPow(base, exponent, j);
+
+        // STEP 4: Compute q^(-1) (mod 2^j) and y := (x2-x1) * q^(-1) (mod 2^j)
+        BigInteger qInv = modPow2Inverse(q, j);
+        BigInteger y = (x2.subtract(x1)).multiply(qInv);
+        inplaceModPow2(y, j);
+        if (y.sign < 0) {
+            y = y.add(BigInteger.ZERO.setBit(j));
+        }
+        // STEP 5: Compute and return: x1 + q * y
+        return x1.add(q.multiply(y));
+    }
+
+    /**
+     * It requires that all parameters be postivive.
+     * 
+     * @return {@code base<sup>exponent</sup> mod (2<sup>j</sup>)}.
+     * @see BigInteger#modPow(BigInteger, BigInteger)
+     */
+    static BigInteger pow2ModPow(BigInteger base, BigInteger exponent, int j) {
+        // PRE: (base > 0), (exponent > 0) and (j > 0)
+        BigInteger res = BigInteger.ONE;
+        BigInteger e = exponent.clone();
+        BigInteger baseMod2toN = base.clone();
+        BigInteger res2;
+        /*
+         * If 'base' is odd then it's coprime with 2^j and phi(2^j) = 2^(j-1);
+         * so we can reduce reduce the exponent (mod 2^(j-1)).
+         */
+        if (base.testBit(0)) {
+            inplaceModPow2(e, j - 1);
+        }
+        inplaceModPow2(baseMod2toN, j);
+
+        for (int i = e.bitLength() - 1; i >= 0; i--) {
+            res2 = res.clone();
+            inplaceModPow2(res2, j);
+            res = res.multiply(res2);
+            if (BitLevel.testBit(e, i)) {
+                res = res.multiply(baseMod2toN);
+                inplaceModPow2(res, j);
+            }
+        }
+        inplaceModPow2(res, j);
+        return res;
+    }
+
+    /**
+     * Implements the Montgomery Product of two integres represented by
+     * {@code int} arrays. Based in <i>The square and multiply algorithm and the
+     * Montgomery Reduction (C. K. Koc - Analyzing and Comparing Montgomery
+     * Multiplication Algorithms)</i> The arrays are suposed in <i>little
+     * endian</i> notation.
+     * 
+     * @param a The first factor of the product.
+     * @param b The second factor of the product.
+     * @param modulus The modululus of the oprations. Z<sub>modulus</sub>.
+     * @param n2 The digit modulus'[0].
+     * @ar.org.fitc.ref "C. K. Koc - Analyzing and Comparing Montgomery
+     *                  Multiplication Algorithms"
+     * @see #modPowOdd(BigInteger, BigInteger, BigInteger)
+     */
+    static BigInteger monPro(BigInteger a, BigInteger b, BigInteger modulus,
+            long n2) {
+        int aFirst = a.numberLength - 1;
+        int bFirst = b.numberLength - 1;
+        int s = modulus.numberLength;
+        int n[] = modulus.digits;
+
+        int m;
+        int i, j;
+        int t[] = new int[(s << 1) + 1];
+        long product;
+        long C;
+        long aI;
+        boolean lower = false;
+
+        for (i = 0; i < s; i++) {
+            C = 0;
+            aI = (i > aFirst) ? 0 : (a.digits[i] & 0xFFFFFFFFL);
+            for (j = 0; j < s; j++) {
+                product = (t[j] & 0xFFFFFFFFL) + C
+                        + ((j > bFirst) ? 0 : (b.digits[j] & 0xFFFFFFFFL) * aI);
+                C = product >>> 32;
+                t[j] = (int) product;
+            }
+            product = (t[s] & 0xFFFFFFFFL) + C;
+            C = product >>> 32;
+            t[s] = (int) product;
+            t[s + 1] = (int) C;
+
+            m = (int) ((t[0] & 0xFFFFFFFFL) * n2);
+            product = (t[0] & 0xFFFFFFFFL) + (m & 0xFFFFFFFFL)
+                    * (n[0] & 0xFFFFFFFFL);
+            C = (int) (product >>> 32);
+            for (j = 1; j < s; j++) {
+                product = (t[j] & 0xFFFFFFFFL) + (C & 0xFFFFFFFFL)
+                        + (m & 0xFFFFFFFFL) * (n[j] & 0xFFFFFFFFL);
+                C = product >>> 32;
+                t[j - 1] = (int) product;
+            }
+            product = (t[s] & 0xFFFFFFFFL) + (C & 0xFFFFFFFFL);
+            C = product >>> 32;
+            t[s - 1] = (int) product;
+            t[s] = t[s + 1] + (int) C;
+        }
+        // skipping leading zeros
+        for (i = t.length - 1; (i > 0) && (t[i] == 0); i--)
+            ;
+
+        if (i == s - 1) {
+            for (; (i >= 0) && (t[i] == n[i]); i--)
+                ;
+            lower = (i >= 0) && (t[i] & 0xFFFFFFFFL) < (n[i] & 0xFFFFFFFFL);
+        } else {
+            lower = (i < s - 1);
+        }
+        BigInteger res = new BigInteger(1, t.length, t);
+        // if (t >= n) compute (t - n)
+        if (!lower) {
+            Elementary.inplaceSubtract(res, modulus);
+        }
+        res.cutOffLeadingZeroes();
+        return res;
+    }
+
+    /**
+     * @param x an odd positive number.
+     * @param n the exponent by which 2 is raised.
+     * @return {@code x<sup>-1</sup> (mod 2<sup>n</sup>)}.
+     */
+    static BigInteger modPow2Inverse(BigInteger x, int n) {
+        // PRE: (x > 0), (x is odd), and (n > 0)
+        BigInteger y = new BigInteger(1, new int[1 << n]);
+        y.numberLength = 1;
+        y.digits[0] = 1;
+        y.sign = 1;
+
+        for (int i = 1; i < n; i++) {
+            if (BitLevel.testBit(x.multiply(y), i)) {
+                // Adding 2^i to y (setting the i-th bit)
+                y.digits[i >> 5] |= (1 << (i & 31));
+            }
+        }
+        return y;
+    }
+
+    /**
+     * Performs {@code x = x mod (2<sup>n</sup>)}.
+     * 
+     * @param x a positive number, it will store the result.
+     * @param n a positive exponent of {@code 2}.
+     */
+    static void inplaceModPow2(BigInteger x, int n) {
+        // PRE: (x > 0) and (n >= 0)
+        int fd = n >> 5;
+        int leadingZeros;
+
+        if ((x.numberLength < fd) || (x.bitLength() <= n)) {
+            return;
+        }
+        leadingZeros = 32 - (n & 31);
+        x.numberLength = fd + 1;
+        x.digits[fd] &= (leadingZeros < 32) ? (-1 >>> leadingZeros) : 0;
+        x.cutOffLeadingZeroes();
+    }
+
+}

Propchange: incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Division.java
------------------------------------------------------------------------------
    svn:executable = *



Mime
View raw message