gmp-discuss digest, Vol 1 #63 - 1 msg
Tue, 14 Jan 2003 12:24:02 +0100
Say we want to multiply two numbers x,y together , if their of equal sizes ,
say both n limbs , then you can just compair n to the various thresholds
(basecase,kara,toom,fft) and call the relavant function. However what to do
if they are of different sizes say n and m with n>m.
A basecase type method would to divide x into n/m pieces of size m , so we end
up doing floor(n/m) multiplications of size m by m , plus a few smaller ones.
A kara type method would be to divide x and y into two pieces of size n/2 by
"pad out with zeros(don't really do it)" y , so we end up with two muls of
size n/2 by m (assuming m<n/2)
I know how gmp does this unequal splitting , and also that it is not optimal ,
so what splitting is optimal ? , and are there any referances to papers on
We started to study this problem with some colleagues (in cc).
It appears that the (theoretically) optimal strategy for Karatsuba
is the following (assuming n >= m):
- cut each part in two with at most one limb difference: floor(n/2) and
ceil(n/2), floor(m/2) and ceil(m/2)
- group together the largest and smallest of each:
ceil(n/2) with floor(m/2), floor(n/2) with ceil(m/2)
(This assumes also that we use Karatsuba as soon as m >= 2.)
For example for n=5, m=3, we would get 5=3+2, 3=2+1, with one product
of 3*1, one of 2*2, and one of 3*2.
However for Toom-Cook we could not find a simple optimal strategy.