Review Request: BigInteger patch for efficient multiplication and division (#4837946) (original) (raw)

Brian Burkhalter brian.burkhalter at oracle.com
Thu May 9 21:02:31 UTC 2013

Hi Max,

On May 9, 2013, at 2:45 AM, Weijun Wang wrote:

Out of curiosity (my major was math back in university), I take a look at BigInteger.java.phase1:

All useful comments are welcome, for whatever reason!

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 TOOMCOOKTHRESHOLD = 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 < KARATSUBATHRESHOLD) || (ylen < KARATSUBATHRESHOLD)) { .... } else if ((xlen < TOOMCOOKTHRESHOLD) && (ylen < TOOMCOOKTHRESHOLD)) 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?

Indeed the javadoc and the code appear to be contradictory. If the comments are accurate then one would expect the logic to be

if ((xlen < TOOM_COOK_THRESHOLD) || (ylen < TOOM_COOK_THRESHOLD))
    return multiplyKaratsuba(this, val);

I can understand in the case of Karatsuba versus the base algorithm why one would require both numbers to be below the threshold, but I don't know enough about the Toom-3 algorithm yet to comment on your question. I imagine Alan or Tim might have something more useful to say on this point.

Thanks,

Brian

More information about the core-libs-dev mailing list