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

[Brian Burkhalter]

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