harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From apetre...@apache.org
Subject svn commit: r472137 - in /incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math: BigDecimal.java BigInteger.java Conversion.java Division.java Multiplication.java
Date Tue, 07 Nov 2006 15:20:17 GMT
Author: apetrenko
Date: Tue Nov  7 07:20:17 2006
New Revision: 472137

URL: http://svn.apache.org/viewvc?view=rev&rev=472137
Log:
Patch for HARMONY-1981 "[classlib][java.math] optimization of BigInteger.modPow and BigInteger.pow"

Modified:
    incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigDecimal.java
    incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigInteger.java
    incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Conversion.java
    incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Division.java
    incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Multiplication.java

Modified: incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigDecimal.java
URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigDecimal.java?view=diff&rev=472137&r1=472136&r2=472137
==============================================================================
--- incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigDecimal.java
(original)
+++ incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigDecimal.java
Tue Nov  7 07:20:17 2006
@@ -1937,12 +1937,6 @@
             ClassNotFoundException {
         in.defaultReadObject();
 
-        // see comment to getUnscaledValue()
-//        if (getUnscaledValue() == null) {
-//            // math.0B=null unscaled value
-//            throw new StreamCorruptedException(Messages.getString("math.0B")); //$NON-NLS-1$
-//        }
-
         this.bitLength = intVal.bitLength();
         if (this.bitLength < 64) {
             this.smallValue = intVal.longValue();
@@ -1954,9 +1948,7 @@
         out.defaultWriteObject();
     }
 
-
     private BigInteger getUnscaledValue() {
-        // This method is not supposed to return null. Otherwise uncomment 'if' in readObject

         if(intVal == null) {
             intVal = BigInteger.valueOf(smallValue);
         }

Modified: 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?view=diff&rev=472137&r1=472136&r2=472137
==============================================================================
--- incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigInteger.java
(original)
+++ incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/BigInteger.java
Tue Nov  7 07:20:17 2006
@@ -613,14 +613,17 @@
 
     /** @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)
+        if (exp < 0){
             // math.16=Negative exponent
             throw new ArithmeticException(Messages.getString("math.16")); //$NON-NLS-1$
         }
+        if (exp == 0) {
+            return ONE;
+        } else if(exp == 1 || equals(ONE) || equals(ZERO)) {
+            return this;
+        }
+        return Multiplication.pow(this, exp);
+        
     }
 
     /** @ar.org.fitc.spec_ref */
@@ -760,6 +763,13 @@
             throw new ArithmeticException(Messages.getString("math.18")); //$NON-NLS-1$
         }
         BigInteger base = this;
+        
+        if(m.isOne() | ( exponent.sign>0 & base.sign == 0)){
+            return BigInteger.ZERO;
+        }
+        if(base.sign==0 && exponent.sign == 0){
+            return BigInteger.ONE;
+        }
         if (exponent.sign < 0) {
             base = modInverse(m);
             exponent = exponent.negate();

Modified: 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?view=diff&rev=472137&r1=472136&r2=472137
==============================================================================
--- incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Conversion.java
(original)
+++ incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Conversion.java
Tue Nov  7 07:20:17 2006
@@ -33,7 +33,7 @@
      * 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,
+    private static final int[] digitFitInInt = { -1, -1, 31, 19, 15, 13, 11,
             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 };
 
@@ -44,7 +44,7 @@
      */
 
     private static final int bigRadices[] = { -2147483648, 1162261467,
-            1073741824, 1220703125, -2118184960, 1977326743, 1073741824,
+            1073741824, 1220703125, 362797056, 1977326743, 1073741824,
             387420489, 1000000000, 214358881, 429981696, 815730721, 1475789056,
             170859375, 268435456, 410338673, 612220032, 893871739, 1280000000,
             1801088541, 113379904, 148035889, 191102976, 244140625, 308915776,

Modified: 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?view=diff&rev=472137&r1=472136&r2=472137
==============================================================================
--- incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Division.java
(original)
+++ incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Division.java
Tue Nov  7 07:20:17 2006
@@ -530,16 +530,83 @@
         return s; // a^(-1) mod m
     }
 
+    
+    /*Implements the Montgomery modular exponentiation based in <i>The square and multiply
algorithm and the
+     * Montgomery Reduction</i>.
+     *@ar.org.fitc.ref "C. K. Koc - Analyzing and Comparing Montgomery
+     *                  Multiplication Algorithms"
+     *@see #oddModPow(BigInteger, BigInteger,
+     *                           BigInteger)
+     */
+    static BigInteger squareAndMultiply(BigInteger x2, BigInteger a2, BigInteger exponent,BigInteger
modulus, long n2  ){
+        BigInteger res = x2;
+        for (int i = exponent.bitLength() - 1; i >= 0; i--) {
+            res = monPro(res,res,modulus, n2);
+            if (BitLevel.testBit(exponent, i)) {
+                res = monPro(res, a2, modulus, n2);
+            }
+        }
+        return res;
+    }
+    
+    /*Implements the Montgomery modular exponentiation based in <i>The sliding windows
algorithm and the Mongomery
+     *Reduction</i>.
+     *@ar.org.fitc.ref "A. Menezes,P. van Oorschot, S. Vanstone - Handbook of Applied Cryptography";
+     *@see #oddModPow(BigInteger, BigInteger,
+     *                           BigInteger)
+     */
+    static BigInteger slidingWindow(BigInteger x2, BigInteger a2, BigInteger exponent,BigInteger
modulus, long n2){
+        // fill odd low pows of a2
+        BigInteger pows[] = new BigInteger[8];
+        BigInteger res = x2;
+        int lowexp;
+        BigInteger x3;
+        int acc3;
+        pows[0] = a2;
+        
+        x3 = monSquare(a2,modulus,n2);
+        for (int i = 1; i <= 7; i++){
+            pows[i] = monPro(pows[i-1],x3,modulus,n2) ;
+        }
+        
+        for (int i = exponent.bitLength()-1; i>=0;i--){
+            if( BitLevel.testBit(exponent,i) ) {
+                lowexp = 1;
+                acc3 = i;
+                
+                for(int j = Math.max(i-3,0);j <= i-1 ;j++) {
+                    if (BitLevel.testBit(exponent,j)) {
+                        if (j<acc3) {
+                            acc3 = j;
+                            lowexp = (lowexp << (i-j))^1;
+                        } else {
+                            lowexp = lowexp^(1<<(j-acc3));
+                        }
+                    }
+                }
+                
+                for(int j = acc3; j <= i; j++) {
+                    res = monSquare(res,modulus,n2);
+                }
+                res = monPro(pows[(lowexp-1)>>1], res, modulus,n2);
+                i = acc3 ;
+            }else{
+                res = monSquare(res, modulus, n2) ;
+            }
+        }
+        return res;
+    }
+    
     /**
      * 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>
+     * requires that all parameters be postivive and the mudulus be odd. >
      * 
      * @see BigInteger#modPow(BigInteger, BigInteger)
      * @see #monPro(BigInteger, BigInteger, BigInteger, long)
-     * @ar.org.fitc.ref "C. K. Koc - Analyzing and Comparing Montgomery
-     *                  Multiplication Algorithms"
+     * @see #slidingWindow(BigInteger, BigInteger, BigInteger, BigInteger,
+     *                      long)
+     * @see #squareAndMultiply(BigInteger, BigInteger, BigInteger, BigInteger,
+     *                      long)
      */
     static BigInteger oddModPow(BigInteger base, BigInteger exponent,
             BigInteger modulus) {
@@ -549,11 +616,13 @@
         BigInteger a2 = base.shiftLeft(k).mod(modulus);
         // n-residue of base [1 * r (mod modulus)]
         BigInteger x2 = BigInteger.ZERO.setBit(k).mod(modulus);
+        BigInteger res;
         // 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;
-
+        // compute n2
         do {
             if (((m0 * n2) & powerOfTwo) != 0) {
                 n2 |= powerOfTwo;
@@ -562,13 +631,13 @@
         } 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);
-            }
+        if( modulus.numberLength == 1 ){
+            res = squareAndMultiply(x2,a2, exponent, modulus,n2);
+        } else {
+            res = slidingWindow(x2, a2, exponent, modulus, n2);
         }
-        return monPro(x2, BigInteger.ONE, modulus, n2);
+        
+        return monPro(res, BigInteger.ONE, modulus, n2);
     }
 
     /**
@@ -639,11 +708,80 @@
         return res;
     }
 
+    /** Implements the Montgomery Square of a BigInteger.
+     * @see #monPro(BigInteger, BigInteger, BigInteger,
+     * long)
+     */
+    static BigInteger monSquare(BigInteger aBig, BigInteger modulus,
+            long n2){
+        if(modulus.numberLength == 1){
+            return monPro(aBig, aBig, modulus, n2);
+        }
+        //Squaring
+        int [] a = aBig.digits;
+        int [] n = modulus.digits;
+        int s = modulus.numberLength;
+        
+        //Multiplying...
+        int [] t = new int [(s<<1) + 1];
+        long cs;
+        
+        int limit = Math.min(s,aBig.numberLength );
+        for(int i=0; i<limit; i++){
+            cs = 0;
+            for (int j=i+1; j<limit; j++){
+                cs += (0xFFFFFFFFL & t[i+j]) + (0xFFFFFFFFL & a[i]) * (0xFFFFFFFFL
& a[j]) ;
+                t[i+j] = (int) cs;
+                cs >>>= 32;
+            }
+            
+            t[i+limit] = (int) cs;
+        }
+        BitLevel.shiftLeft( t, t, 0, 1 );
+        
+        cs = 0;
+        long carry = 0;
+        for(int i=0, index = 0; i< s; i++, index++){
+            cs += (0xFFFFFFFFL & a[i]) * (0xFFFFFFFFL & a[i]) + (t[index] & 0xFFFFFFFFL);
+            t[index] = (int) cs;
+            cs >>>= 32;
+            index++;
+            cs += t[index] & 0xFFFFFFFFL ;
+            t[index] = (int)cs;
+            cs >>>= 32;
+        }
+        
+        //Reducing...
+        /* t + m*n */
+        int m = 0;
+        int i, j;
+        cs = carry = 0;
+        for (i=0; i<s; i++){
+            cs = 0;
+            m = (int) ((t[i] & 0xFFFFFFFFL) * (n2 & 0xFFFFFFFFL));
+            for(j=0; j<s; j++){
+                cs = (t[i+j] & 0xFFFFFFFFL) +  (m & 0xFFFFFFFFL)  * (n[j] & 0xFFFFFFFFL)
+ (cs >>> 32);
+                t[i+j] = (int) cs;
+            }
+            //Adding C to the result
+            carry += (t[i+s] & 0xFFFFFFFFL) + ( (cs>>>32) & 0xFFFFFFFFL);
+            t[i+s] = (int) carry;
+            carry >>>=32;
+        }
+        
+        t[s<<1] = (int) carry;
+        
+        /* t / r  */
+        for(j=0; j<s+1; j++){
+            t[j] = t[j+s];
+        }
+        /*step 3*/
+        return finalSubtraction(t, s, s, modulus );
+    }
+    
     /**
-     * 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
+     * Implements the Montgomery Product of two integers represented by
+     * {@code int} arrays. The arrays are suposed in <i>little
      * endian</i> notation.
      * 
      * @param a The first factor of the product.
@@ -667,7 +805,6 @@
         long product;
         long C;
         long aI;
-        boolean lower = false;
 
         for (i = 0; i < s; i++) {
             C = 0;
@@ -698,20 +835,33 @@
             t[s - 1] = (int) product;
             t[s] = t[s + 1] + (int) C;
         }
+        
+        return finalSubtraction(t, t.length-1 ,s, modulus);
+        
+    }
+    /*Performs the final reduction of the Montgomery algorithm.
+     *@see monPro(BigInteger, BigInteger, BigInteger,
+     *long )
+     *@see monSquare(BigInteger, BigInteger ,
+     *long)
+     */
+    static BigInteger finalSubtraction(int t[], int tLength ,int s, BigInteger modulus){
         // skipping leading zeros
-        for (i = t.length - 1; (i > 0) && (t[i] == 0); i--) {
+        int i;
+        int n[] = modulus.digits;
+        boolean lower = false;
+        
+        for (i = tLength; (i > 0) && (t[i] == 0); i--)
             ;
-        }
 
         if (i == s - 1) {
-            for (; (i >= 0) && (t[i] == n[i]); i--) {
+            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);
+        BigInteger res = new BigInteger(1, s+1, t);
         // if (t >= n) compute (t - n)
         if (!lower) {
             Elementary.inplaceSubtract(res, modulus);

Modified: incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Multiplication.java
URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Multiplication.java?view=diff&rev=472137&r1=472136&r2=472137
==============================================================================
--- incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Multiplication.java
(original)
+++ incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Multiplication.java
Tue Nov  7 07:20:17 2006
@@ -244,19 +244,21 @@
         int[] aDigits = a.digits;
         int[] bDigits = b.digits;
         int resDigits[] = new int[resLength];
+        long carry;
+        long bDigit;
+        int i, j, m;
         // Common case
-        for (int j = 0; j < bLen; j++) {
-            long carry = 0;
-            int i;
-            for (i = 0; i < aLen; i++) {
-                int m = i + j;
+        for (j = 0; j < bLen; j++) {
+            carry = 0;
+            bDigit = (bDigits[j] & 0xFFFFFFFFL);
+            for (i = 0, m = j; i < aLen; i++, m++) {
                 carry += (aDigits[i] & 0xFFFFFFFFL)
-                * (bDigits[j] & 0xFFFFFFFFL)
+                * bDigit
                 + (resDigits[m] & 0xFFFFFFFFL);
                 resDigits[m] = (int)carry;
                 carry >>>= 32;
             }
-            resDigits[i + j] = (int) carry;
+            resDigits[m] = (int) carry;
         }
         BigInteger result = new BigInteger(resSign, resLength, resDigits);
         result.cutOffLeadingZeroes();
@@ -326,12 +328,6 @@
         return result;
     }
 
-    /**
-     * Exponentiation algorithm using squaring algorithm.
-     * @param base
-     * @param exponent must be positive
-     * @ar.org.fitc.ref "http://en.wikipedia.org/wiki/Exponentiating_by_squaring"
-     */
     static BigInteger pow(BigInteger base, int exponent) {
         // PRE: exp > 0
         BigInteger res = BigInteger.ONE;
@@ -343,11 +339,53 @@
                 res = res.multiply(acc);
             }
             // acc = base^(2^i)
-            acc = acc.multiply(acc); // squaring            
+            //a limit where karatsuba performs a faster square than the square algorithm
+            if ( acc.numberLength == 1 ){
+                acc = acc.multiply(acc); // square
+            }
+            else{
+                acc = new BigInteger(1, square(acc.digits, acc.numberLength));
+            }
         }
         // exponent == 1, multiply one more time
         res = res.multiply(acc);
         return res;
+    }
+
+    /**
+     *  Performs a<sup>2</sup>
+     *  @param a The number to square.
+     *  @param length The lenght of the number to square.
+     */ 
+    static int[] square(int[] a, int s) {
+        int [] t = new int [s<<1];
+        long cs;
+        long aI;
+        for(int i=0; i<s; i++){
+            cs = 0;
+            aI = (0xFFFFFFFFL & a[i]);
+            for (int j=i+1; j<s; j++){
+                cs += (0xFFFFFFFFL & t[i+j]) + aI * (0xFFFFFFFFL & a[j]) ;
+                t[i+j] = (int) cs;
+                cs >>>= 32;
+            }
+            
+            t[i+s] = (int) cs;
+        }
+        BitLevel.shiftLeft( t, t, 0, 1 );
+        cs = 0;
+        
+        for(int i=0, index = 0; i< s; i++, index++){
+            aI = (0xFFFFFFFFL & a[i]);
+            cs += aI * aI  + (t[index] & 0xFFFFFFFFL);
+            t[index] = (int) cs;
+            cs >>>= 32;
+            index++;
+            cs += t[index] & 0xFFFFFFFFL ;
+            t[index] = (int)cs;
+            cs >>>= 32;
+        }
+        return t;
     }
 
     /**



Mime
View raw message