You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@harmony.apache.org by ml...@apache.org on 2006/06/22 06:21:18 UTC
svn commit: r416238 - in
/incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math:
BigDecimal.java BigInteger.java
Author: mloenko
Date: Wed Jun 21 21:21:17 2006
New Revision: 416238
URL: http://svn.apache.org/viewvc?rev=416238&view=rev
Log:
applied performance patch from HARMONY-551
[classlib][java.math] performance improvement for java.math package
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
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?rev=416238&r1=416237&r2=416238&view=diff
==============================================================================
--- 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 Wed Jun 21 21:21:17 2006
@@ -111,6 +111,37 @@
*/
public static final int ROUND_UP = 0;
+ private transient String toStringImage = null;
+
+ private static final BigDecimal[] SMALL_ZERO_SCALED_VALUES = {
+ ZERO,
+ ONE,
+ new BigDecimal(BigInteger.SMALL_VALUES[2], 0),
+ new BigDecimal(BigInteger.SMALL_VALUES[3], 0),
+ new BigDecimal(BigInteger.SMALL_VALUES[4], 0),
+ new BigDecimal(BigInteger.SMALL_VALUES[5], 0),
+ new BigDecimal(BigInteger.SMALL_VALUES[6], 0),
+ new BigDecimal(BigInteger.SMALL_VALUES[7], 0),
+ new BigDecimal(BigInteger.SMALL_VALUES[8], 0),
+ new BigDecimal(BigInteger.SMALL_VALUES[9], 0),
+ TEN
+ };
+
+ private static final BigDecimal[] ZERO_SMALL_SCALED_VALUES = {
+ ZERO,
+ new BigDecimal(BigInteger.ZERO, 1),
+ new BigDecimal(BigInteger.ZERO, 2),
+ new BigDecimal(BigInteger.ZERO, 3),
+ new BigDecimal(BigInteger.ZERO, 4),
+ new BigDecimal(BigInteger.ZERO, 5),
+ new BigDecimal(BigInteger.ZERO, 6),
+ new BigDecimal(BigInteger.ZERO, 7),
+ new BigDecimal(BigInteger.ZERO, 8),
+ new BigDecimal(BigInteger.ZERO, 9),
+ new BigDecimal(BigInteger.ZERO, 10),
+ };
+
+
/**
* Controls overflow in the calculated preferred scale.
* If it overflows a 32-bit integer, return extreme Integer values.
@@ -165,6 +196,12 @@
* the scale value is < 0;
*/
public static BigDecimal valueOf(long unscaledValue, int scale) {
+ if (unscaledValue == 0L && (scale >= 0 && scale <= 10)) {
+ return ZERO_SMALL_SCALED_VALUES[scale];
+ }
+ if (scale == 0 && (unscaledValue >= 0 && unscaledValue <= 10)) {
+ return SMALL_ZERO_SCALED_VALUES[(int) unscaledValue];
+ }
return new BigDecimal(BigInteger.valueOf(unscaledValue), scale);
}
@@ -344,8 +381,28 @@
scale = 0;
} else {
// m * 2 ^ e = m * (10 / 5) ^ e = (m * 5 ^ (-e)) * 10 ^ e
- intVal = intVal.multiply(BigInteger.valueOf(5L).pow(-scale));
scale = -scale;
+ if(scale<fivePows.length) {
+ intVal = intVal.multiply(fivePows[scale]);
+ } else {
+ intVal = intVal.multiply(BigInteger.FIVE.pow(scale));
+ }
+ }
+ }
+
+ private static final BigInteger[] fivePows = new BigInteger[36];
+
+ static {
+ fivePows[0] = BigInteger.ONE;
+ fivePows[1] = BigInteger.FIVE;
+ int i=2;
+ long val = 25L;
+ for(;i<=27;i++) {
+ fivePows[i] = BigInteger.valueOf(val);
+ val*=5L;
+ }
+ for(;i<fivePows.length;i++) {
+ fivePows[i] = fivePows[i-1].multiply(BigInteger.FIVE);
}
}
@@ -507,17 +564,16 @@
* @return BigDecimal The sum of adding two BigDecimal.
*/
public BigDecimal add(BigDecimal value) {
- if (scale == value.scale) {
+ int delta = scale - value.scale;
+ if (delta == 0) {
return new BigDecimal(intVal.add(value.intVal), scale);
}
- boolean thisScaleIsLess = this.scale < value.scale;
- int newScale = thisScaleIsLess ? value.scale : this.scale;
- if (thisScaleIsLess) {
- return new BigDecimal(this.intVal.multiply
- (BigInteger.TEN.pow(value.scale - this.scale)).add(value.intVal), newScale);
+ if (delta < 0) {
+ return new BigDecimal(this.intVal.multiplyByTenPow(-delta)
+ .add(value.intVal), value.scale);
} else {
- return new BigDecimal(value.intVal.multiply
- (BigInteger.TEN.pow(this.scale - value.scale)).add(this.intVal), newScale);
+ return new BigDecimal(value.intVal.multiplyByTenPow(delta)
+ .add(this.intVal), this.scale);
}
}
@@ -574,16 +630,21 @@
* @return int 0 - equal; 1 - this > value; -1 - this < value.
*/
public int compareTo(BigDecimal value) {
- if (this.scale == value.scale) {
- return this.intVal.compareTo(value.intVal);
+ if (this.intVal.sign == value.intVal.sign) {
+ int delta = scale - value.scale;
+ if (delta == 0) {
+ return this.intVal.compareTo(value.intVal);
+ }
+ if (delta < 0) {
+ return this.intVal.multiplyByTenPow(-delta).compareTo(value.intVal);
+ } else {
+ return this.intVal.compareTo(value.intVal.multiplyByTenPow(delta));
+ }
}
- if (this.scale < value.scale) {
- return this.intVal.multiply(BigInteger.TEN.pow(value.scale - this.scale)).
- compareTo(value.intVal);
- } else {
- return this.intVal.compareTo(value.intVal.multiply
- (BigInteger.TEN.pow(this.scale - value.scale)));
+ if (this.intVal.sign == 0) {
+ return -value.intVal.sign;
}
+ return this.intVal.sign;
}
/**
@@ -660,56 +721,182 @@
BigInteger dividend = this.intVal;
BigInteger divisor = value.intVal;
if (exponent < 0) {
- divisor = divisor.multiply(BigInteger.TEN.pow(-exponent));
+ divisor = divisor.multiplyByTenPow(-exponent);
} else if (exponent > 0) {
- dividend = dividend.multiply(BigInteger.TEN.pow(exponent));
+ dividend = dividend.multiplyByTenPow(exponent);
}
- BigInteger res[] = dividend.divideAndRemainder(divisor);
- BigInteger quotient = res[0];
- if (res[1].signum() != 0) {
- if (roundingMode == ROUND_UNNECESSARY) {
- throw new ArithmeticException
- ("rounding mode is ROUND_UNNECESSARY but the result is not exact");
- }
- boolean negativeQuotient = intVal.signum() != divisor.signum();
- boolean negativeRemainder = res[1].signum() == -1;
- boolean negativeDivisor = divisor.signum() == -1;
- if (roundingMode == ROUND_FLOOR) {
- roundingMode = negativeQuotient ? ROUND_UP : ROUND_DOWN;
- } else if (roundingMode == ROUND_CEILING) {
- roundingMode = negativeQuotient ? ROUND_DOWN : ROUND_UP;
- } else {
- if (negativeDivisor) {
- divisor = divisor.abs();
+ return divideByBigInteger(dividend, divisor, roundingMode, quotientScale);
+ }
+
+ private static boolean needIncDec(int quotientLo, boolean negativeQuotient, long divisor, long remainder, int roundingMode) {
+ // Assertion: divisor & remainder are positive
+ if (roundingMode == ROUND_UNNECESSARY) {
+ throw new ArithmeticException("rounding mode is"
+ + " ROUND_UNNECESSARY but the result is not exact");
+ }
+ boolean flag = false;
+ if(roundingMode==ROUND_UP) {
+ flag =true;
+ } else if (roundingMode == ROUND_FLOOR) {
+ flag = negativeQuotient; //negativeQuotient ? ROUND_UP : ROUND_DOWN
+ } else if (roundingMode == ROUND_CEILING) {
+ flag = !negativeQuotient; // negativeQuotient ? ROUND_DOWN : ROUND_UP;
+ } else {
+ // distance == -1 if the quotient is NOT the nearest neighbor
+ // to the exact result;
+ // distance == 0 if the exact result is equidistant from
+ // the neighbors;
+ // distance == +1 if the quotient is the nearest neighbor
+ // to the exact result.
+ long halfDivisor = divisor >>> 1;
+
+ if (roundingMode == ROUND_HALF_DOWN) {
+ flag = halfDivisor < remainder;
+ //roundingMode = (distance >= 0) ? ROUND_DOWN : ROUND_UP;
+ } else if (roundingMode == ROUND_HALF_UP) {
+ flag = halfDivisor <= remainder;
+ //roundingMode = (distance > 0) ? ROUND_DOWN : ROUND_UP;
+ } else if (roundingMode == ROUND_HALF_EVEN) {
+ if (halfDivisor > remainder) {
+ //roundingMode = ROUND_DOWN;
+ } else if (halfDivisor < remainder) {
+ flag = true;
+ //roundingMode = ROUND_UP;
+ } else {
+ flag = (quotientLo & 1) == 1;
+ //roundingMode = ROUND_UP;
}
- if (negativeRemainder) {
- res[1] = res[1].abs();
+ }
+ }
+ return flag;
+ }
+
+ private static BigDecimal divideByInteger(BigInteger dividend, int divisor, int divisorSign, int roundingMode, int quotientScale) {
+ // res[0] is a quotient and res[1] is a remainder:
+ int[] dividendDigits = dividend.digits;
+ int dividendLen = dividend.numberLength;
+ int dividendSign = dividend.sign;
+ if (dividendLen == 1) {
+ long a = ((long) dividendDigits[0] & 0xffffffffL);
+ long b = ((long) divisor & 0xffffffffL);
+ long quo = a / b;
+ long rem = a % b;
+ if (dividendSign != divisorSign) {
+ quo = -quo;
+ if (rem != 0 && needIncDec((int) quo, true, b, rem, roundingMode)) {
+ quo--;
+ }
+ } else {
+ if (rem != 0 && needIncDec((int) quo, false, b, rem, roundingMode)) {
+ quo++;
}
- // distance == -1 if the quotient is NOT the nearest neighbor to the exact result;
- // distance == 0 if the exact result is equidistant from the neighbors;
- // distance == +1 if the quotient is the nearest neighbor to the exact result.
- int distance = divisor.subtract(res[1]).compareTo(res[1]);
- if (roundingMode == ROUND_HALF_DOWN) {
- roundingMode = distance >= 0 ? ROUND_DOWN : ROUND_UP;
- } else if (roundingMode == ROUND_HALF_UP) {
- roundingMode = distance > 0 ? ROUND_DOWN : ROUND_UP;
- } else if (roundingMode == ROUND_HALF_EVEN) {
- if (distance > 0) {
- roundingMode = ROUND_DOWN;
- } else if (distance < 0) {
- roundingMode = ROUND_UP;
- } else if (!quotient.testBit(0)) {
- roundingMode = ROUND_DOWN;
- } else {
- roundingMode = ROUND_UP;
- }
- }
}
- if (roundingMode == ROUND_UP) {
- quotient = quotient.add(BigInteger.valueOf(negativeQuotient ? -1 : 1));
+ return new BigDecimal(BigInteger.valueOf(quo), quotientScale);
+ } else {
+ int quotientLength = dividendLen;
+ int quotientSign = ((dividendSign == divisorSign) ? 1 : -1);
+ int quotientDigits[] = new int[quotientLength];
+ int remainder = BigInteger.divideArrayByInt(quotientDigits,
+ dividendDigits, dividendLen, divisor);
+ if (remainder != 0 && needIncDec(quotientDigits[0], dividendSign != divisorSign, (long) divisor & 0xffffffffL, remainder, roundingMode)) {
+ quotientDigits = BigInteger.incInPlace(quotientDigits);
+ }
+ BigInteger result = new BigInteger(quotientSign, quotientLength,
+ quotientDigits);
+ result.cutOffLeadingZeroes();
+ return new BigDecimal(result, quotientScale);
+ }
+ }
+
+ private static BigDecimal divideByBigInteger(BigInteger dividend, BigInteger divisor, int roundingMode, int quotientScale) {
+ int divisorLen = divisor.numberLength;
+ if (divisorLen == 1) {
+ //res = dividend.divideAndRemainderByInteger(divisorDigits[0], divisorSign);
+ return divideByInteger(dividend, divisor.digits[0], divisor.sign, roundingMode, quotientScale);
+ }
+ BigInteger quotient;
+ BigInteger remainder;
+ int divisorSign = divisor.sign;
+ int[] divisorDigits = divisor.digits;
+ // res[0] is a quotient and res[1] is a remainder:
+ int[] thisDigits = dividend.digits;
+ int thisLen = dividend.numberLength;
+ boolean negativeQuotient = dividend.signum() != divisorSign;
+ int cmp = (thisLen != divisorLen ?
+ ((thisLen > divisorLen) ? 1 : -1) :
+ BigInteger.compareArrays(thisDigits, divisorDigits, thisLen));
+ if (cmp < 0) {
+ if (!dividend.isZero() && needIncDec(0, negativeQuotient, divisor, dividend.abs(), roundingMode)) {
+ return new BigDecimal(negativeQuotient ? BigInteger.NEG_ONE : BigInteger.ONE, quotientScale);
+ }
+ return new BigDecimal(BigInteger.ZERO, quotientScale);
+ } else {
+ int thisSign = dividend.sign;
+ int quotientLength = thisLen - divisorLen + 1;
+ int remainderLength = divisorLen;
+ int quotientSign = ((thisSign == divisorSign) ? 1 : -1);
+ int quotientDigits[] = new int[quotientLength];
+ int remainderDigits[] = BigInteger.divide(quotientDigits, quotientLength,
+ thisDigits, thisLen,
+ divisorDigits, divisorLen);
+ remainder = new BigInteger(1, remainderLength,
+ remainderDigits);
+ remainder.cutOffLeadingZeroes();
+ if (!remainder.isZero() && needIncDec(quotientDigits[0], quotientSign < 0, divisor, remainder, roundingMode)) {
+ quotientDigits = BigInteger.incInPlace(quotientDigits);
+ }
+ quotient = new BigInteger(quotientSign, quotientLength,
+ quotientDigits);
+ quotient.cutOffLeadingZeroes();
+ return new BigDecimal(quotient, quotientScale);
+ }
+ }
+
+ private static boolean needIncDec(int quotientLo, boolean negativeQuotient, BigInteger divisor, BigInteger remainder, int roundingMode) {
+ if (roundingMode == ROUND_UNNECESSARY) {
+ throw new ArithmeticException("rounding mode is"
+ + " ROUND_UNNECESSARY but the result is not exact");
+ }
+ boolean flag = false;
+ int divisorSignum = divisor.signum();
+ if(roundingMode==ROUND_UP) {
+ flag =true;
+ } else if (roundingMode == ROUND_FLOOR) {
+ flag = negativeQuotient; //negativeQuotient ? ROUND_UP : ROUND_DOWN
+ } else if (roundingMode == ROUND_CEILING) {
+ flag = !negativeQuotient; // negativeQuotient ? ROUND_DOWN : ROUND_UP;
+ } else {
+ // distance == -1 if the quotient is NOT the nearest neighbor
+ // to the exact result;
+ // distance == 0 if the exact result is equidistant from
+ // the neighbors;
+ // distance == +1 if the quotient is the nearest neighbor
+ // to the exact result.
+ if (divisorSignum == -1) {
+ divisor = divisor.abs();
+ }
+
+ int distance = divisor.subtract(remainder).compareTo(remainder);
+ if (roundingMode == ROUND_HALF_DOWN) {
+ flag = (distance < 0);
+ //(distance >= 0) ? ROUND_DOWN : ROUND_UP;
+ } else if (roundingMode == ROUND_HALF_UP) {
+ flag = (distance <= 0);
+ //roundingMode = (distance > 0) ? ROUND_DOWN : ROUND_UP;
+ } else if (roundingMode == ROUND_HALF_EVEN) {
+ if (distance > 0) {
+ //roundingMode = ROUND_DOWN;
+ } else if (distance < 0) {
+ flag = true; //roundingMode = ROUND_UP;
+ } else if (!((quotientLo & 1) == 1)) {
+ //roundingMode = ROUND_DOWN;
+ } else {
+ flag = true;
+ //roundingMode = ROUND_UP;
+ }
}
}
- return new BigDecimal(quotient, quotientScale);
+ return flag;
}
/**
@@ -975,11 +1162,16 @@
* @param shift shift distance
*/
private BigDecimal movePoint(int shift) {
- int newScale = getValidInt((long)scale + (long)shift, "scale");
- if (newScale > 0) {
- return new BigDecimal(intVal, newScale);
+ long newScale = (long) scale + (long) shift;
+ if (newScale != (int) newScale) {
+ throw new ArithmeticException("scale outside the range of a 32-bit integer");
+ }
+ int newSc = (int) newScale;
+ if (newSc >= 0) {
+ return new BigDecimal(intVal, newSc);
}
- return new BigDecimal(this.intVal.multiply(BigInteger.TEN.pow(-newScale)), 0);
+ return new BigDecimal(this.intVal
+ .multiplyByTenPow(-newSc), 0);
}
/**
@@ -1192,14 +1384,25 @@
* invalid rounding mode
*/
public BigDecimal setScale(int newScale, int roundingMode) {
+ if (roundingMode > 7 || roundingMode < 0) {
+ throw new IllegalArgumentException("invalid rounding mode");
+ }
int delta = this.scale - newScale;
if (delta == 0) {
return this;
}
if (delta > 0) {
- return divide(new BigDecimal(BigInteger.TEN.pow(delta), delta), newScale, roundingMode);
+ return divideByTenPow(delta, roundingMode, newScale);
} else {
- return new BigDecimal(intVal.multiply(BigInteger.TEN.pow(-delta)), newScale);
+ return new BigDecimal(intVal.multiplyByTenPow(-delta), newScale);
+ }
+ }
+
+ private BigDecimal divideByTenPow(int delta, int roundingMode, int newScale) {
+ if (delta < 10) {
+ return divideByInteger(intVal, BigInteger.tenPows[delta], 1, roundingMode, newScale);
+ } else {
+ return divideByBigInteger(intVal, BigInteger.getTenPow(delta), roundingMode, newScale);
}
}
@@ -1265,17 +1468,17 @@
* @return BigDecimal The result of subtracting the BigDecimal argument.
*/
public BigDecimal subtract(BigDecimal value) {
- if (scale == value.scale) {
+ int delta = scale - value.scale;
+ if (delta == 0) {
return new BigDecimal(intVal.subtract(value.intVal), scale);
}
- boolean thisScaleIsLess = this.scale < value.scale;
- int newScale = thisScaleIsLess ? value.scale : this.scale;
- if (thisScaleIsLess) {
- return new BigDecimal(this.intVal.multiply(BigInteger.TEN.pow(value.scale - this.scale)).
- subtract(value.intVal), newScale);
+ if (delta < 0) {
+ return new BigDecimal(this.intVal.multiplyByTenPow(-delta)
+ .subtract(value.intVal), value.scale);
} else {
- return new BigDecimal(this.intVal.
- subtract(value.intVal.multiply(BigInteger.TEN.pow(this.scale - value.scale))), newScale);
+ return new BigDecimal(this.intVal
+ .subtract(value.intVal.multiplyByTenPow(delta)),
+ this.scale);
}
}
@@ -1299,9 +1502,9 @@
return intVal;
}
if (scale > 0) {
- return intVal.divide(BigInteger.TEN.pow(scale));
+ return intVal.divide(BigInteger.getTenPow(scale));
}
- return intVal.multiply(BigInteger.TEN.pow(-scale));
+ return intVal.multiplyByTenPow(-scale);
}
/**
@@ -1428,40 +1631,10 @@
* @return String a printable representation for the receiver.
*/
public String toString() {
- String intString = intVal.toString();
- if (scale == 0) {
- return intString;
+ if (toStringImage == null) {
+ toStringImage = intVal.toDecimalScaledString(scale);
}
- boolean negNumber = intVal.signum() < 0;
- int startPoint = negNumber ? 2 : 1;
- int endPoint = intString.length();
- int exponent = -scale + intString.length() - (negNumber ? 2 : 1);
- StringBuffer result = new StringBuffer();
- result.append(intString);
- if (scale > 0 && exponent >= -6) {
- if (exponent >= 0) {
- result.insert(exponent + (negNumber ? 2 : 1), '.');
- } else {
- char zeros[] = new char[-exponent + 1];
- zeros[0] = '0';
- zeros[1] = '.';
- for (int i = 2; i < zeros.length; i++) {
- zeros[i] = '0';
- }
- result.insert(negNumber ? 1 : 0, zeros);
- }
- } else {
- if (endPoint - startPoint >= 1) {
- result.insert(startPoint, '.');
- endPoint++;
- }
- result.insert(endPoint, 'E');
- if (exponent > 0) {
- result.insert(++endPoint, '+');
- }
- result.insert(++endPoint, Integer.toString(exponent));
- }
- return result.toString();
+ return toStringImage;
}
/**
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?rev=416238&r1=416237&r2=416238&view=diff
==============================================================================
--- 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 Wed Jun 21 21:21:17 2006
@@ -35,7 +35,7 @@
private static final int EQUALS = 0;
private static final int GREATER = 1;
private static final int LESS = -1;
- private static final BigInteger NEG_ONE = new BigInteger (-1, 1);
+ static final BigInteger NEG_ONE = new BigInteger (-1, 1);
// bigRadices values are precomputed maximal powers of radices
// (integer numbers from 2 to 36) that fit into unsigned int (32 bits).
@@ -49,6 +49,8 @@
887503681, 1073741824, 1291467969, 1544804416, 1838265625, 60466176
};
+ static final int tenPows[] = {1,10,100,1000,10000,100000,1000000,
+ 10000000,100000000,1000000000};
// the first 54 prime numbers were copied from the published sources,
// e.g. http://en.wikipedia.org/wiki/List_of_prime_numbers#The_first_500_prime_numbers
private static final int primes[] = {
@@ -89,20 +91,44 @@
*/
public static final BigInteger ZERO = new BigInteger (0, 0);
+ static final BigInteger FIVE = new BigInteger (1, 5);
+
+ static final BigInteger[] SMALL_VALUES = {ZERO,ONE,new BigInteger(1,2),
+ new BigInteger(1,3), new BigInteger(1,4), FIVE,
+ new BigInteger(1,6), new BigInteger(1,7), new BigInteger(1,8),
+ new BigInteger(1,9), TEN };
+
+ private static final BigInteger[] bigTenPows = new BigInteger [32];
+
+ static {
+
+ bigTenPows[0] = ONE;
+ bigTenPows[1] = TEN;
+ int i=2;
+ long val = 100;
+ for(;i<=18;i++) {
+ bigTenPows[i] = valueOf(val);
+ val*=10L;
+ }
+ for(;i<bigTenPows.length;i++) {
+ bigTenPows[i] = bigTenPows[i-1].multiply(BigInteger.TEN);
+ }
+ }
+
/**
* The magnitude of this in the little-endian representation
*/
- private transient int digits[];
+ transient int digits[];
/**
* The length of this in measured in ints. Can be less than digits.length().
*/
- private transient int numberLength;
+ transient int numberLength;
/**
* The sign of this.
*/
- private transient int sign;
+ transient int sign;
/**
* Adds two arrays element by element taking carry into consideration.
@@ -111,8 +137,10 @@
private static int[] add(int a[], int aSize, int b[], int bSize) {
int i;
int res[] = new int[aSize + 1];
- long k = 0;
- for (i = 0; i < bSize; i++) {
+ long k = ((long)a[0] & 0x0ffffffffL) + ((long)b[0] & 0x0ffffffffL);
+ res[0] = (int)k;
+ k >>= 32;
+ for (i = 1; i < bSize; i++) {
k += ((long)a[i] & 0x0ffffffffL) + ((long)b[i] & 0x0ffffffffL);
res[i] = (int)k;
k >>= 32;
@@ -126,6 +154,27 @@
return res;
}
+ static int[] incInPlace(int a[]) {
+ int size = a.length;
+ long k = ((long)a[0] & 0x0ffffffffL) + 1L;
+ a[0]=(int)k;
+ k >>= 32;
+ int i=1;
+ for (; (i < size)&& k!=0; i++) {
+ k += (long)a[i] & 0x0ffffffffL;
+ a[i] = (int)k;
+ k >>= 32;
+ }
+ if(k!=0 && i==size) {
+ int res[] = new int[size + 1];
+ for(int j=0; j<size; j++) res[j]=a[j];
+ res[i] = (int)k;
+ return res;
+ } else {
+ return a;
+ }
+ }
+
/**
* Adds an integer value to the array of integers remembering carry.
* Returns carry.
@@ -178,29 +227,26 @@
}
/**
- * Compares magnitude of two arrays.
+ * Compares two arrays.
* All elements are treated as unsigned integers.
* The magnitude is the bit chain of elements in big-endian order.
* @param a the first array
- * @param aSize the size of a
* @param b the second array
- * @param bSize the size of b
+ * @param size the size of arrays
* @return 1 if a > b, -1 if a < b, 0 if a == b
*/
- private static int compareMagnitude(final int a[], final int aSize,
- final int b[], final int bSize) {
- if (aSize != bSize) {
- return (aSize > bSize ? 1 : -1);
- }
- for (int i = aSize - 1; i >= 0; i--) {
- if (((long)a[i] & 0x0ffffffffL) > ((long)b[i] & 0x0ffffffffL)) {
- return GREATER;
- }
- if (((long)a[i] & 0x0ffffffffL) < ((long)b[i] & 0x0ffffffffL)) {
+ static int compareArrays(final int[] a, final int[] b, final int size) {
+ for (int i = size - 1; i >= 0; i--) {
+ long aValue = ((long)a[i] & 0x0ffffffffL);
+ long bValue = ((long)b[i] & 0x0ffffffffL);
+ if (aValue < bValue) {
return LESS;
}
+ if (aValue > bValue) {
+ return GREATER;
+ }
}
- return EQUALS;
+ return EQUALS;
}
/**
@@ -230,7 +276,7 @@
* @param bLength the divisor's length
* @return the remainder
*/
- private static int[] divide(int quot[], int quotLength, int a[],
+ 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
@@ -347,15 +393,59 @@
* @param divisor the divisor
* @return remainder
*/
- private static int divideArrayByInt(int dest[], int src[],
+ 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
+ */
+ private 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);
- if (dest != null) {
- dest[i] = (int)res;
- }
result = (int)(res >> 32);
}
return (int)result;
@@ -601,27 +691,36 @@
* @return BigInteger (BigInteger) longValue
*/
public static BigInteger valueOf(long longValue) {
- int valueSign = (longValue > 0 ? 1 : longValue < 0 ? -1 : 0);
if (longValue < 0) {
longValue = -longValue;
+ int valueLo = (int) longValue;
+ int valueHi = (int) (longValue >>> 32);
+ if (valueHi == 0) {
+ return new BigInteger(-1, valueLo);
+ } else {
+ return new BigInteger(-1, 2, new int[]{valueLo, valueHi});
}
- if (((int)longValue & 0xffffffffL) == longValue) {
- return new BigInteger(valueSign, (int)longValue);
+ } else if (longValue <= 10) {
+ return SMALL_VALUES[(int) longValue];
+ } else {
+ int valueLo = (int) longValue;
+ int valueHi = (int) (longValue >> 32);
+ if (valueHi == 0) {
+ return new BigInteger(1, valueLo);
+ } else {
+ return new BigInteger(1, 2, new int[]{valueLo, valueHi});
+ }
}
- int digitsValue[] = new int[2];
- digitsValue[0] = (int)longValue;
- digitsValue[1] = (int)(longValue >> 32);
- return new BigInteger(valueSign, 2, digitsValue);
}
- private BigInteger (int sign, int value) {
+ BigInteger (int sign, int value) {
this.sign = sign;
numberLength = 1;
digits = new int[1];
this.digits[0] = value;
}
- private BigInteger (int sign, int length, int[] value) {
+ BigInteger (int sign, int length, int[] value) {
this.sign = sign;
numberLength = length;
digits = value;
@@ -833,37 +932,70 @@
public BigInteger add(BigInteger that) {
int resDigits[];
int resSign;
- if (this.sign == that.sign) {
- resSign = this.sign;
-
+ int thisSign = this.sign;
+ int thatSign = that.sign;
+ if (thisSign == 0 ) {
+ return that;
+ }
+ if(thatSign == 0){
+ return this;
+ }
+ int thisLen = this.numberLength;
+ int thatLen = that.numberLength;
+ if(thisLen + thatLen == 2) {
+ long a = ((long) this.digits[0] & 0xffffffffL);
+ long b = ((long) that.digits[0] & 0xffffffffL);
+ long res;
+ if (thisSign == thatSign) {
+ res = a+b;
+ int valueLo = (int) res;
+ int valueHi = (int) (res >>> 32);
+ if (valueHi == 0) {
+ return new BigInteger(thisSign, valueLo);
+ } else {
+ return new BigInteger(thisSign, 2, new int[]{valueLo, valueHi});
+ }
+ } else {
+ if (thisSign < 0 ) {
+ res = b-a;
+ } else {
+ res = a-b;
+ }
+ return valueOf( res );
+ }
+ } else if (thisSign == thatSign) {
+ resSign = thisSign;
// an augend should not be shorter than addend
- if (this.numberLength >= that.numberLength) {
- resDigits = add(this.digits, this.numberLength, that.digits,
- that.numberLength);
+ if (thisLen >= thatLen) {
+ resDigits = add(this.digits, thisLen,
+ that.digits, thatLen);
} else {
- resDigits = add(that.digits, that.numberLength, this.digits,
- this.numberLength);
- }
+ resDigits = add(that.digits, thatLen,
+ this.digits, thisLen);
+ }
} else { // signs are different
- int cmp = compareMagnitude(this.digits, this.numberLength,
- that.digits, that.numberLength);
+
+ int cmp = (thisLen != thatLen ?
+ ((thisLen > thatLen) ? 1 : -1) :
+ compareArrays(this.digits,that.digits,thisLen ));
+
if (cmp == EQUALS) {
return ZERO;
}
// a minuend should not be shorter than subtrahend
if (cmp == GREATER) {
- resSign = this.sign;
- resDigits = subtract(this.digits, this.numberLength,
- that.digits, that.numberLength);
+ resSign = thisSign;
+ resDigits = subtract(this.digits, thisLen,
+ that.digits, thatLen);
} else {
- resSign = that.sign;
- resDigits = subtract(that.digits, that.numberLength,
- this.digits, this.numberLength);
+ resSign = thatSign;
+ resDigits = subtract(that.digits, thatLen,
+ this.digits, thisLen);
}
- }
- BigInteger result = new BigInteger(resSign, resDigits.length, resDigits);
- result.cutOffLeadingZeroes();
- return result;
+ }
+ BigInteger res = new BigInteger(resSign, resDigits.length, resDigits);
+ res.cutOffLeadingZeroes();
+ return res;
}
/**
@@ -877,7 +1009,7 @@
if (this.sign == 0 || that.sign == 0) {
return ZERO;
}
- int resSign = this.sign == -1 && that.sign == -1 ? -1 : 1;
+ int resSign = (this.sign == -1 && that.sign == -1) ? -1 : 1;
int resLength;
int resDigits[];
int thisNeg[] = null;
@@ -1140,22 +1272,25 @@
* comparable with the receiver.
*/
public int compareTo(BigInteger that) {
- if (this.sign == that.sign) {
- if(this.sign == 0) {
- return 0;
- }
- int compareResult = compareMagnitude(this.digits,
- this.numberLength, that.digits, that.numberLength);
- if (this.sign == 1) {
+ int thisSign = this.sign;
+ int thatSign = that.sign;
+ if (thisSign == 0) {
+ return -thatSign;
+ }
+ if (thisSign == thatSign) {
+ int thisLen = this.numberLength;
+ int thatLen = that.numberLength;
+ int compareResult = (thisLen != thatLen ?
+ ((thisLen > thatLen) ? 1 : -1) :
+ compareArrays(this.digits,that.digits,thisLen ));
+
+ if (thisSign == 1) {
return compareResult;
} else {
return -compareResult;
}
}
- if (this.sign == 0) {
- return -that.sign;
- }
- return this.sign;
+ return thisSign;
}
/**
@@ -1187,7 +1322,7 @@
/**
* Decreases numberLength if there are zero high elements.
*/
- private void cutOffLeadingZeroes() {
+ final void cutOffLeadingZeroes() {
while(numberLength > 0 && digits[--numberLength] == 0) {
}
if (digits[numberLength++] == 0) {
@@ -1206,38 +1341,53 @@
* if that is zero.
*/
public BigInteger divide(BigInteger that) {
- if (that.equals(ZERO)) {
+ if (that.isZero()) {
throw new ArithmeticException("division by zero");
}
- if (that.isOne()) {
- if (that.sign == 1) {
+ int thatSign = that.sign;
+ if (that.isOne()) {
+ if (thatSign == 1) {
return this;
} else {
return this.negate();
}
}
- int cmp = compareMagnitude(this.digits, this.numberLength, that.digits,
- that.numberLength);
+ int thisSign = this.sign;
+ int thisLen = this.numberLength;
+ int thatLen = that.numberLength;
+ if (thisLen + thatLen == 2) {
+ long val = ((long)this.digits[0] & 0xffffffffL)
+ / ((long)that.digits[0] & 0xffffffffL);
+ if(thisSign != thatSign) {
+ val = -val;
+ }
+ return valueOf( val );
+ } else {
+ int cmp = (thisLen != thatLen ?
+ ((thisLen > thatLen) ? 1 : -1) :
+ compareArrays(this.digits,that.digits,thisLen ));
+
if (cmp == EQUALS) {
- return (this.sign == that.sign ? ONE : NEG_ONE);
+ return ((thisSign == thatSign) ? ONE : NEG_ONE);
}
if (cmp == LESS) {
return ZERO;
}
- int resLength = this.numberLength - that.numberLength + 1;
+ int resLength = thisLen - thatLen + 1;
int resDigits[] = new int[resLength];
- int resSign = (this.sign == that.sign ? 1 : -1);
- if (that.numberLength == 1) {
- divideArrayByInt(resDigits, this.digits, this.numberLength,
+ int resSign = ((thisSign == thatSign) ? 1 : -1);
+ if (thatLen == 1) {
+ divideArrayByInt(resDigits, this.digits, thisLen,
that.digits[0]);
} else {
- divide(resDigits, resLength, this.digits, this.numberLength,
- that.digits, that.numberLength);
+ divide(resDigits, resLength, this.digits, thisLen,
+ that.digits, thatLen);
}
BigInteger result = new BigInteger(resSign, resLength, resDigits);
result.cutOffLeadingZeroes();
return result;
}
+ }
/**
* Answers the quotient and remainder of the receiver divided by a
@@ -1251,39 +1401,74 @@
* if val is zero.
*/
public BigInteger[] divideAndRemainder(BigInteger that) {
- if (that.isZero()) {
+ int thatSign = that.sign;
+ if (thatSign==0) {
throw new ArithmeticException("division by zero");
}
+ int thatLen = that.numberLength;
+ int[] thatDigits = that.digits;
+ if(thatLen == 1) {
+ return divideAndRemainderByInteger(thatDigits[0],thatSign);
+ }
// res[0] is a quotient and res[1] is a remainder:
- BigInteger result[] = new BigInteger[2];
- int quotientLength, remainderLength;
- int quotientSign, remainderSign;
- int quotientDigits[], remainderDigits[];
- if (compareMagnitude(this.digits, this.numberLength, that.digits,
- that.numberLength) == LESS) {
- result[0] = ZERO;
- result[1] = this;
- } else {
- quotientLength = this.numberLength - that.numberLength + 1;
- quotientDigits = new int[quotientLength];
- quotientSign = (this.sign == that.sign ? 1 : -1);
- remainderLength = that.numberLength;
- remainderDigits = new int[quotientLength];
- remainderSign = this.sign;
- if (that.numberLength == 1) {
- remainderDigits[0] = divideArrayByInt(quotientDigits,
- this.digits, this.numberLength, that.digits[0]);
- } else {
- remainderDigits = divide(quotientDigits, quotientLength,
- this.digits, this.numberLength, that.digits,
- that.numberLength);
- }
- result[0] = new BigInteger(quotientSign, quotientLength, quotientDigits);
- result[1] = new BigInteger(remainderSign, remainderLength, remainderDigits);
- result[0].cutOffLeadingZeroes();
- result[1].cutOffLeadingZeroes();
+ int[] thisDigits = this.digits;
+ int thisLen = this.numberLength;
+ int cmp = (thisLen != thatLen ?
+ ((thisLen > thatLen) ? 1 : -1) :
+ compareArrays(thisDigits,thatDigits,thisLen ));
+ if ( cmp < 0 ) {
+ return new BigInteger[]{ZERO, this};
+ } else {
+ int thisSign = this.sign;
+ int quotientLength = thisLen - thatLen + 1;
+ int remainderLength = thatLen;
+ int quotientSign = ((thisSign == thatSign) ? 1 : -1);
+ int quotientDigits[] = new int[quotientLength];
+ int remainderDigits[] = divide(quotientDigits, quotientLength,
+ thisDigits, thisLen,
+ thatDigits, thatLen);
+ BigInteger result0 = new BigInteger(quotientSign, quotientLength,
+ quotientDigits);
+ BigInteger result1 = new BigInteger(thisSign, remainderLength,
+ remainderDigits);
+ result0.cutOffLeadingZeroes();
+ result1.cutOffLeadingZeroes();
+ return new BigInteger[]{result0, result1};
+ }
+ }
+
+ BigInteger[] divideAndRemainderByInteger(int that, int thatSign) {
+ // res[0] is a quotient and res[1] is a remainder:
+ int[] thisDigits = this.digits;
+ int thisLen = this.numberLength;
+ int thisSign = this.sign;
+ if (thisLen == 1) {
+ long a = ((long) thisDigits[0] & 0xffffffffL);
+ long b = ((long) that & 0xffffffffL);
+ long quo = a / b;
+ long rem = a % b;
+ if (thisSign != thatSign) {
+ quo = -quo;
+ }
+ if (thisSign <0 ) {
+ rem = -rem;
+ }
+ return new BigInteger[]{valueOf(quo), valueOf(rem)};
+ } else {
+ int quotientLength = thisLen ;
+ int quotientSign = ((thisSign == thatSign) ? 1 : -1);
+ int quotientDigits[] = new int[quotientLength];
+ int remainderDigits[];
+ remainderDigits = new int[]{divideArrayByInt(quotientDigits,
+ thisDigits, thisLen, that)};
+ BigInteger result0 = new BigInteger(quotientSign, quotientLength,
+ quotientDigits);
+ BigInteger result1 = new BigInteger(thisSign, 1,
+ remainderDigits);
+ result0.cutOffLeadingZeroes();
+ result1.cutOffLeadingZeroes();
+ return new BigInteger[]{result0, result1};
}
- return result;
}
/**
@@ -1368,7 +1553,7 @@
if (! (anotherObj instanceof BigInteger)) {
return false;
}
- return (compareTo((BigInteger)anotherObj) == EQUALS ? true : false);
+ return compareTo((BigInteger)anotherObj) == EQUALS;
}
/**
@@ -1504,7 +1689,7 @@
if (numberLength == 1 && digits[0] == primes[i]) {
return true;
}
- if (divideArrayByInt(null, digits, numberLength, primes[i]) == 0) {
+ if (remainderArrayByInt( digits, numberLength, primes[i]) == 0) {
return false;
}
}
@@ -1575,12 +1760,9 @@
/**
* Checks if this BigInteger equals to ZERO
*/
- private boolean isZero() {
- if (numberLength == 1 && digits[0] == 0) {
- return true;
- }
- return false;
- }
+ final boolean isZero() {
+ return sign==0;
+ }
/**
* Answers the long value which the receiver represents
@@ -1589,6 +1771,7 @@
*/
public long longValue() {
long value = (long)digits[0] & 0xffffffffL;
+ if (numberLength == 0) return 0;
if (numberLength == 1) {
return (sign >= 1 ? value : -value);
} else {
@@ -1753,50 +1936,100 @@
* Implements traditional scholar algorithm described by Knuth.
*/
private BigInteger multiply(BigInteger a, BigInteger b) {
- int resSign = (a.sign == b.sign ? 1 : -1);
- int resLength = a.numberLength + b.numberLength;
- int resDigits[] = new int[resLength];
- // for (i = 0; i < a.numberLength; i++) {
- // r.digits[i] = 0;
- // }
- long carry;
-
- // a special case when both numbers don't exceed int
+ int aLen = a.numberLength;
+ int bLen = b.numberLength;
+ int resLength = aLen + bLen;
+ // a special case when both numbers don't exceed int
if (resLength == 2) {
- carry = ((long)a.digits[0] & 0xffffffffL) *
- ((long)b.digits[0] & 0xffffffffL);
- resDigits[0] = (int)carry;
- resDigits[1] = (int)(carry >>> 32);
- if(resDigits[1] == 0) {
- resLength = 1;
+ long val = ((long)a.digits[0] & 0xffffffffL)
+ * ((long)b.digits[0] & 0xffffffffL);
+ int sign = a.sign != b.sign ? -1 : 1;
+ int valueLo = (int) val;
+ int valueHi = (int) (val >>> 32);
+ if (valueHi == 0) {
+ return new BigInteger(sign, valueLo);
+ } else {
+ return new BigInteger(sign, 2, new int[]{valueLo, valueHi});
}
- return new BigInteger(resSign, resLength, resDigits);
}
-
+ int[] aDigits = a.digits;
+ int[] bDigits = b.digits;
+ int resDigits[] = new int[resLength];
// common case
- for (int j = 0; j < b.numberLength; j++) {
- carry = 0;
+ for (int j = 0; j < bLen; j++) {
+ long carry = 0;
int i;
- for (i = 0; i < a.numberLength; i++) {
+ for (i = 0; i < aLen; i++) {
int m = i + j;
- carry += ((long)a.digits[i] & 0xffffffffL) *
- ((long)b.digits[j] & 0xffffffffL) + ((long)resDigits[m] & 0xffffffffL);
+ carry += ((long)aDigits[i] & 0xffffffffL)
+ * ((long)bDigits[j] & 0xffffffffL)
+ + ((long)resDigits[m] & 0xffffffffL);
resDigits[m] = (int)carry;
carry >>>= 32;
}
resDigits[i + j] = (int)carry;
}
+ BigInteger result = new BigInteger((a.sign == b.sign) ? 1 : -1, resLength, resDigits);
+ result.cutOffLeadingZeroes();
+ return result;
+ }
+
+ private static BigInteger multiplyByPositiveInt(BigInteger a, int b) {
+ int resSign = a.sign;
+ if (resSign == 0) {
+ return ZERO;
+ }
+ int aNumberLength = a.numberLength;
+ int[] aDigits = a.digits;
+ if (aNumberLength == 1) {
+ long res = ((long) aDigits[0] & 0xffffffffL) * ((long) b);
+ int resLo = (int) res;
+ int resHi = (int) (res >>> 32);
+ if (resHi == 0) {
+ return new BigInteger(resSign, resLo);
+ }
+ return new BigInteger(resSign, 2, new int[]{resLo, resHi});
+ }
+ int resLength = aNumberLength + 1;
+ int resDigits[] = new int[resLength];
+ long carry = 0;
+ // common case
+ int i;
+ for (i = 0; i < aNumberLength; i++) {
+ carry += ((long) aDigits[i] & 0xffffffffL)
+ * ((long) b & 0xffffffffL);
+ resDigits[i] = (int) carry;
+ carry >>>= 32;
+ }
+ resDigits[i] = (int) carry;
BigInteger result = new BigInteger(resSign, resLength, resDigits);
result.cutOffLeadingZeroes();
return result;
}
+ BigInteger multiplyByTenPow(int exp) {
+ if(exp < 10) {
+ return multiplyByPositiveInt(this,tenPows[exp]);
+ }
+ return multiply(getTenPow(exp));
+ }
+
+ static BigInteger getTenPow(int exp) {
+ if(exp < bigTenPows.length) {
+ return bigTenPows[exp];
+ }
+ return TEN.pow(exp);
+ }
+
/**
* Answers the negative of the receiver
*
* @return BigInteger (-1) * this
*/
public BigInteger negate() {
+ if(isZero()) {
+ return this;
+ }
return new BigInteger(-sign, numberLength, digits);
}
@@ -1808,7 +2041,7 @@
throw new ArithmeticException("the number must be positive");
}
if (sign == 0) {
- return new BigInteger(1, 2);
+ return SMALL_VALUES[2];
}
int resDigits[] = new int[numberLength];
System.arraycopy(digits, 0, resDigits, 0, numberLength);
@@ -2015,19 +2248,23 @@
if (that.equals(ZERO)) {
throw new ArithmeticException("division by zero");
}
- if (compareMagnitude(this.digits, this.numberLength, that.digits,
- that.numberLength) == LESS) {
+ int thisLen = this.numberLength;
+ int thatLen = that.numberLength;
+ if ((thisLen != thatLen ?
+ ((thisLen > thatLen) ? 1 : -1) :
+ compareArrays(this.digits,that.digits,thisLen ))
+ == LESS) {
return this;
}
- int resLength = that.numberLength;
+ int resLength = thatLen;
int resDigits[] = new int[resLength];
if (resLength == 1) {
- resDigits[0] = divideArrayByInt(null, this.digits,
- this.numberLength, that.digits[0]);
+ resDigits[0] = remainderArrayByInt(this.digits,
+ thisLen, that.digits[0]);
} else {
- int qLen = this.numberLength - that.numberLength + 1;
- resDigits = divide(null, qLen,
- this.digits, this.numberLength, that.digits, that.numberLength);
+ int qLen = thisLen - thatLen + 1;
+ resDigits = divide(null, qLen, this.digits, thisLen,
+ that.digits, thatLen);
}
BigInteger result = new BigInteger(this.sign, resLength, resDigits);
result.cutOffLeadingZeroes();
@@ -2156,32 +2393,57 @@
public BigInteger subtract(BigInteger that) {
int resSign;
int resDigits[];
- int cmp = compareMagnitude(this.digits, this.numberLength, that.digits, that.numberLength);
+ int thisSign = this.sign;
+ int thatSign = that.sign;
+ if(thatSign==0) {
+ return this;
+ }
+ if(thisSign==0){
+ return that.negate();
+ }
+
+ int thisLen = this.numberLength;
+ int thatLen = that.numberLength;
+ if(thisLen+thatLen == 2){
+ long a = ((long) this.digits[0] & 0xffffffffL);
+ long b = ((long) that.digits[0] & 0xffffffffL);
+ if(thisSign<0) {
+ a=-a;
+ }
+ if(thatSign<0){
+ b=-b;
+ }
+ return valueOf( a-b );
+ }
+ int cmp = (thisLen != thatLen ?
+ ((thisLen > thatLen) ? 1 : -1) :
+ compareArrays(this.digits,that.digits,thisLen ));
+
if (cmp == LESS) {
- resSign = -that.sign;
- if (this.sign == that.sign) {
- resDigits = subtract(that.digits, that.numberLength,
- this.digits, this.numberLength);
+ resSign = -thatSign;
+ if (thisSign == thatSign) {
+ resDigits = subtract(that.digits, thatLen,
+ this.digits, thisLen);
} else {
- resDigits = add(that.digits, that.numberLength, this.digits,
- this.numberLength);
+ resDigits = add(that.digits, thatLen, this.digits,
+ thisLen);
}
} else {
- resSign = this.sign;
- if (this.sign == that.sign) {
+ resSign = thisSign;
+ if (thisSign == thatSign) {
if (cmp == EQUALS) {
return ZERO;
}
- resDigits = subtract(this.digits, this.numberLength,
- that.digits, that.numberLength);
+ resDigits = subtract(this.digits, thisLen,
+ that.digits, thatLen);
} else {
- resDigits = add(this.digits, this.numberLength, that.digits,
- that.numberLength);
+ resDigits = add(this.digits, thisLen, that.digits,
+ thatLen);
}
}
- BigInteger result = new BigInteger(resSign, resDigits.length, resDigits);
- result.cutOffLeadingZeroes();
- return result;
+ BigInteger res = new BigInteger(resSign, resDigits.length, resDigits);
+ res.cutOffLeadingZeroes();
+ return res;
}
/**
@@ -2266,6 +2528,26 @@
return bytes;
}
+ private static long divideLongByBillion(long a) {
+ long quot;
+ long rem;
+ if (a >= 0) {
+ long bLong = 1000000000L; //(long)1000000000 & 0xffffffffL;
+ 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);
+ }
+
/**
* Answers a string containing a concise, human-readable description of the
* receiver. In this case, a string of decimal digits.
@@ -2273,7 +2555,150 @@
* @return String a printable representation for the receiver.
*/
public String toString() {
- return toString(10);
+ return toDecimalScaledString(0);
+ }
+
+ String toDecimalScaledString(int scale) {
+ 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();
+ }
}
/**
@@ -2286,17 +2711,22 @@
if (sign == 0) {
return "0";
}
- if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX) {
- radix = 10;
+ if(numberLength == 1) {
+ int highDigit = digits[numberLength-1];
+ long v = (long)highDigit&0xffffffffL;
+ if (sign < 0) {
+ v = -v;
+ }
+ return Long.toString(v,radix);
}
- double bitsForRadixDigit;
- if (radix == 10) {
- bitsForRadixDigit = 3.3219280948873626;
- } else {
- bitsForRadixDigit = Math.log(radix) / Math.log(2);
+ if (radix < Character.MIN_RADIX || radix > Character.MAX_RADIX || radix == 10) {
+ return toString();
}
+ double bitsForRadixDigit;
+ bitsForRadixDigit = Math.log(radix) / Math.log(2);
int resLengthInChars = (int)(abs().bitLength() / bitsForRadixDigit
+ ((sign == -1) ? 1 : 0)) + 1;
+
char result[] = new char[resLengthInChars];
int currentChar = resLengthInChars;
int resDigit;