Out of curiosity (my major was math back in university), I take a look
at BigInteger.java.phase1:
First you have:
/**
* The threshold value for using 3-way Toom-Cook multiplication.
* If the number of ints in both mag arrays are greater than this
number,
* then Toom-Cook multiplication will be used. This value is found
* experimentally to work well.
*/
private static final int TOOM_COOK_THRESHOLD = 75;
but then:
public BigInteger multiply(BigInteger val) {
if (val.signum == 0 || signum == 0)
return ZERO;
int xlen = mag.length;
int ylen = val.mag.length;
if ((xlen < KARATSUBA_THRESHOLD) || (ylen < KARATSUBA_THRESHOLD))
{
....
}
else
if ((xlen < TOOM_COOK_THRESHOLD) && (ylen <
TOOM_COOK_THRESHOLD))
return multiplyKaratsuba(this, val);
else
return multiplyToomCook3(this, val);
}
So, is it *both* numbers or *any* of them great than the constant that
the Toom-Cook algotithm will be used?
Thanks
Max
On 5/9/13 3:11 PM, Alan Eliasen wrote:
On 05/07/2013 12:53 PM, Brian Burkhalter wrote:
To recapitulate in one place, I think we agree on the following sequence:
Phase 1: Faster multiplication and exponentiation of large integers
* Karatsuba and Toom-Cook multiplication and squaring; revised pow() function.
* http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4837946 (update
synopsis/description)
* http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4646474
Phase 2: Faster string conversion of large integers
* Recursive Schoenhage toString() routines.
* http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4641897
Phase 3: Faster division of large integers
* Burnickel-Ziegler division routines.
* Issue to be filed.
Phase 4: Faster multiplication and division of very large integers
* Barrett division and Schoenhage-Strassen multiplication.
* Issue to be filed.
Okay, I've created a set of patches that implement these 4 phases.
(They're not actually patches, but the entire source file for each
phase, as Brian requested.)
These are available at:
http://futureboy.us/temp/BigIntegerPatch.zip
In this zipfile, the file(s) to use for each phase are marked with
the ".phaseX" suffix. If there is no change in a file for a given
phase, there is no file included for that phase, but you should make
sure that you are still using the BigDecimal and MutableBigInteger
file(s) applied in the previous phases.
So, to be very clear, the files that make up each phase are:
Phase 1:
BigInteger.java.phase1
BigDecimal.java.phase1 (since BigInteger.pow is accelerated, the
workaround in BigDecimal is removed.)
Phase 2:
BigInteger.java.phase2
Phase 3:
BigInteger.java.phase3
MutableBigInteger.java.phase3 (to use Burnikel-Ziegler divide)
Phase 4:
BigInteger.java.phase4
For your reference, the final versions of each file are contained
with the ".final" suffix. These will be identical to previous phases
applied, and you don't have to apply them, but if someone wants to
quickly drop in the best improvements to their own JDK, just use the 3
files with the ".final" suffix.
Let me know if you have any issues with these.
Tim and Brian, you might decide amongst yourselves who wants to file
the issues for phases 3 and 4. I don't know if Brian has any magical
powers to make the issues skip the QA process.
