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
