multiplication of unequal sizes
Paul Zimmermann
Paul.Zimmermann@loria.fr
Tue, 14 Jan 2003 13:57:51 +0100
> Just a guess, maybe you could add the two number size in bits and compare
> this with a threshold.
> Ex, let's say you have a 1200 bits number and a 3210 bits number. Then, you
> check the sum of that (4410) with a threshold.
This does not work, since for 4409 bits and 1 bit you'll get the same sum,
but you should always use the naive algorithm.
I think only the smallest size should be compared to the threshold,
at least up to the Toom-Cook range.
In the FFT range it's a bit different since the actual cost will be indeed
a function of the size sum, but you still want the smallest size to be large
enough, otherwise Toom-Cook will be faster.
Paul Zimmermann