src/share/classes/java/math/BigInteger.java
Print this page
rev 7721 : 8014319: Faster division of large integers
Summary: Implement Burnickel-Ziegler division algorithm in BigInteger
Reviewed-by: bpb, martin
Contributed-by: Tim Buktu <tbuktu@hotmail.com>
*** 31,41 ****
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.ObjectStreamField;
- import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import sun.misc.DoubleConsts;
import sun.misc.FloatConsts;
--- 31,40 ----
*** 99,108 ****
--- 98,108 ----
*
* @see BigDecimal
* @author Josh Bloch
* @author Michael McCloskey
* @author Alan Eliasen
+ * @author Timothy Buktu
* @since JDK1.1
*/
public class BigInteger extends Number implements Comparable<BigInteger> {
/**
*** 213,222 ****
--- 213,230 ----
* experimentally to work well.
*/
private static final int TOOM_COOK_SQUARE_THRESHOLD = 140;
/**
+ * The threshold value for using Burnikel-Ziegler division. If the number
+ * of ints in the number are larger than this value,
+ * Burnikel-Ziegler division will be used. This value is found
+ * experimentally to work well.
+ */
+ static final int BURNIKEL_ZIEGLER_THRESHOLD = 50;
+
+ /**
* The threshold value for using Schoenhage recursive base conversion. If
* the number of ints in the number are larger than this value,
* the Schoenhage algorithm will be used. In practice, it appears that the
* Schoenhage routine is faster for any threshold down to 2, and is
* relatively flat for thresholds between 2-25, so this choice may be
*** 1934,1948 ****
* @param val value by which this BigInteger is to be divided.
* @return {@code this / val}
* @throws ArithmeticException if {@code val} is zero.
*/
public BigInteger divide(BigInteger val) {
MutableBigInteger q = new MutableBigInteger(),
a = new MutableBigInteger(this.mag),
b = new MutableBigInteger(val.mag);
! a.divide(b, q, false);
return q.toBigInteger(this.signum * val.signum);
}
/**
* Returns an array of two BigIntegers containing {@code (this / val)}
--- 1942,1971 ----
* @param val value by which this BigInteger is to be divided.
* @return {@code this / val}
* @throws ArithmeticException if {@code val} is zero.
*/
public BigInteger divide(BigInteger val) {
+ if (mag.length<BURNIKEL_ZIEGLER_THRESHOLD || val.mag.length<BURNIKEL_ZIEGLER_THRESHOLD)
+ return divideKnuth(val);
+ else
+ return divideBurnikelZiegler(val);
+ }
+
+ /**
+ * Returns a BigInteger whose value is {@code (this / val)} using an O(n^2) algorithm from Knuth.
+ *
+ * @param val value by which this BigInteger is to be divided.
+ * @return {@code this / val}
+ * @throws ArithmeticException if {@code val} is zero.
+ * @see MutableBigInteger#divideKnuth(MutableBigInteger, MutableBigInteger, boolean)
+ */
+ private BigInteger divideKnuth(BigInteger val) {
MutableBigInteger q = new MutableBigInteger(),
a = new MutableBigInteger(this.mag),
b = new MutableBigInteger(val.mag);
! a.divideKnuth(b, q, false);
return q.toBigInteger(this.signum * val.signum);
}
/**
* Returns an array of two BigIntegers containing {@code (this / val)}
*** 1954,1968 ****
* is the initial element, and the remainder {@code (this % val)}
* is the final element.
* @throws ArithmeticException if {@code val} is zero.
*/
public BigInteger[] divideAndRemainder(BigInteger val) {
BigInteger[] result = new BigInteger[2];
MutableBigInteger q = new MutableBigInteger(),
a = new MutableBigInteger(this.mag),
b = new MutableBigInteger(val.mag);
! MutableBigInteger r = a.divide(b, q);
result[0] = q.toBigInteger(this.signum == val.signum ? 1 : -1);
result[1] = r.toBigInteger(this.signum);
return result;
}
--- 1977,1999 ----
* is the initial element, and the remainder {@code (this % val)}
* is the final element.
* @throws ArithmeticException if {@code val} is zero.
*/
public BigInteger[] divideAndRemainder(BigInteger val) {
+ if (mag.length<BURNIKEL_ZIEGLER_THRESHOLD || val.mag.length<BURNIKEL_ZIEGLER_THRESHOLD)
+ return divideAndRemainderKnuth(val);
+ else
+ return divideAndRemainderBurnikelZiegler(val);
+ }
+
+ /** Long division */
+ private BigInteger[] divideAndRemainderKnuth(BigInteger val) {
BigInteger[] result = new BigInteger[2];
MutableBigInteger q = new MutableBigInteger(),
a = new MutableBigInteger(this.mag),
b = new MutableBigInteger(val.mag);
! MutableBigInteger r = a.divideKnuth(b, q);
result[0] = q.toBigInteger(this.signum == val.signum ? 1 : -1);
result[1] = r.toBigInteger(this.signum);
return result;
}
*** 1973,1987 ****
* remainder computed.
* @return {@code this % val}
* @throws ArithmeticException if {@code val} is zero.
*/
public BigInteger remainder(BigInteger val) {
MutableBigInteger q = new MutableBigInteger(),
a = new MutableBigInteger(this.mag),
b = new MutableBigInteger(val.mag);
! return a.divide(b, q).toBigInteger(this.signum);
}
/**
* Returns a BigInteger whose value is <tt>(this<sup>exponent</sup>)</tt>.
* Note that {@code exponent} is an integer rather than a BigInteger.
--- 2004,2058 ----
* remainder computed.
* @return {@code this % val}
* @throws ArithmeticException if {@code val} is zero.
*/
public BigInteger remainder(BigInteger val) {
+ if (mag.length<BURNIKEL_ZIEGLER_THRESHOLD || val.mag.length<BURNIKEL_ZIEGLER_THRESHOLD)
+ return remainderKnuth(val);
+ else
+ return remainderBurnikelZiegler(val);
+ }
+
+ /** Long division */
+ private BigInteger remainderKnuth(BigInteger val) {
MutableBigInteger q = new MutableBigInteger(),
a = new MutableBigInteger(this.mag),
b = new MutableBigInteger(val.mag);
! return a.divideKnuth(b, q).toBigInteger(this.signum);
! }
!
! /**
! * Calculates {@code this / val} using the Burnikel-Ziegler algorithm.
! * @param val the divisor
! * @return {@code this / val}
! */
! private BigInteger divideBurnikelZiegler(BigInteger val) {
! return divideAndRemainderBurnikelZiegler(val)[0];
! }
!
! /**
! * Calculates {@code this % val} using the Burnikel-Ziegler algorithm.
! * @param val the divisor
! * @return {@code this % val}
! */
! private BigInteger remainderBurnikelZiegler(BigInteger val) {
! return divideAndRemainderBurnikelZiegler(val)[1];
! }
!
! /**
! * Computes {@code this / val} and {@code this % val} using the
! * Burnikel-Ziegler algorithm.
! * @param val the divisor
! * @return an array containing the quotient and remainder
! */
! private BigInteger[] divideAndRemainderBurnikelZiegler(BigInteger val) {
! MutableBigInteger q = new MutableBigInteger();
! MutableBigInteger r = new MutableBigInteger(this).divideAndRemainderBurnikelZiegler(new MutableBigInteger(val), q);
! BigInteger qBigInt = q.isZero() ? ZERO : q.toBigInteger(signum*val.signum);
! BigInteger rBigInt = r.isZero() ? ZERO : r.toBigInteger(signum);
! return new BigInteger[] {qBigInt, rBigInt};
}
/**
* Returns a BigInteger whose value is <tt>(this<sup>exponent</sup>)</tt>.
* Note that {@code exponent} is an integer rather than a BigInteger.
*** 3397,3407 ****
return buf.toString();
}
/**
* Converts the specified BigInteger to a string and appends to
! * <code>sb</code>. This implements the recursive Schoenhage algorithm
* for base conversions.
* <p/>
* See Knuth, Donald, _The Art of Computer Programming_, Vol. 2,
* Answers to Exercises (4.4) Question 14.
*
--- 3468,3478 ----
return buf.toString();
}
/**
* Converts the specified BigInteger to a string and appends to
! * {@code sb}. This implements the recursive Schoenhage algorithm
* for base conversions.
* <p/>
* See Knuth, Donald, _The Art of Computer Programming_, Vol. 2,
* Answers to Exercises (4.4) Question 14.
*
*** 3448,3458 ****
/**
* Returns the value radix^(2^exponent) from the cache.
* If this value doesn't already exist in the cache, it is added.
* <p/>
* This could be changed to a more complicated caching method using
! * <code>Future</code>.
*/
private static BigInteger getRadixConversionCache(int radix, int exponent) {
BigInteger[] cacheLine = powerCache[radix]; // volatile read
if (exponent < cacheLine.length) {
return cacheLine[exponent];
--- 3519,3529 ----
/**
* Returns the value radix^(2^exponent) from the cache.
* If this value doesn't already exist in the cache, it is added.
* <p/>
* This could be changed to a more complicated caching method using
! * {@code Future}.
*/
private static BigInteger getRadixConversionCache(int radix, int exponent) {
BigInteger[] cacheLine = powerCache[radix]; // volatile read
if (exponent < cacheLine.length) {
return cacheLine[exponent];