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 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?
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