On 05/09/2013 03:02 PM, Brian Burkhalter wrote:
>> 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?
You're right that the actual code will use Toom-Cook if 1.) both of
the numbers are greater than the Karatsuba threshold *and* 2.) at least
one of the numbers is greater than the Toom-Cook threshold. That test
could go either way (with "and" or "or".) When the sizes of the numbers
are in between Karatsuba and Toom-Cook sizes, both algorithms perform
approximately equally well. You might choose Karatsuba as it has a
somewhat lower constant factor, but as the efficiency of Toom-Cook
multiplication increased, (say, with my fast exactDivideBy3 routine and
the choice of an optimal Toom-Cook formulation,) it became slightly
advantageous to choose Toom-Cook in this vague situation. But it varies
with the precise bit patterns of the arguments.
The thresholds were tuned to take this into account. I'm not saying
that it always makes an optimal choice, but it's hard to make an optimal
choice without performing potentially expensive tests.
At one point, I had fiddled with "unbalanced" Toom-Cook
multiplication where the numbers are of different sizes, but the added
code complexity wasn't worth the effort.
Note that this logic and the description will change again when
Schoenhage-Strassen (SS) multiplication is added back in. The SS
multiplication routines have a rather complicated stairstep of
thresholds, and describing the thresholds in comments will be difficult.
If you want to change the comment to something like my first sentence
in the first paragraph, that would be fine. Alternately, we could
change the logic to match the comment, but that would probably mean that
we should re-tune the thresholds.
--
Alan Eliasen
elia...@mindspring.com
http://futureboy.us/
