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

[Paul Zimmermann]

   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