harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From mloe...@apache.org
Subject svn commit: r416238 - in /incubator/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math: BigDecimal.java BigInteger.java
Date Thu, 22 Jun 2006 04:21:18 GMT
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;



Mime
View raw message