You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by ap...@apache.org on 2006/11/07 16:20:17 UTC
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
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;
}
/**