# multiplication of unequal sizes

**Jason Moxham
**
J.L.Moxham@maths.soton.ac.uk

*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 =
do=20
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=
nes.
A kara type method would be to divide x and y into two pieces of size n/2=
by=20
"pad out with zeros(don't really do it)" y , so we end up with two muls o=
f=20
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=
n=20
this ?
thanks