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