multiplication of unequal sizes

Jason Moxham
Mon, 13 Jan 2003 02:29:50 +0000

Say we want to multiply two numbers x,y together , if their of equal size=
s ,=20
say both n limbs , then you can just compair n to the various thresholds=20
(basecase,kara,toom,fft) and call the relavant function. However what to =
if they are of different sizes say n and m with n>m.=20

A basecase type method would to divide x into n/m pieces of size m , so w=
e end=20
up doing floor(n/m) multiplications of size m by m , plus a few smaller o=

A kara type method would be to divide x and y into two pieces of size n/2=
"pad out with zeros(don't really do it)" y , so we end up with two muls o=
size n/2 by m   (assuming m<n/2)

I know how gmp does this unequal splitting , and also that it is not opti=
mal ,=20
so what splitting is optimal ? , and are there any referances to papers o=
this ?