# gmp-discuss digest, Vol 1 #63 - 1 msg

**Paul Zimmermann
**
Paul.Zimmermann@loria.fr

*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
this ?
thanks
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.
Paul