multiplication of unequal sizes

[delta trinity]

Just a guess, maybe you could add the two number size in bits and compare 
this with a threshold.

Ex, let's say you have a 1200 bits number and a 3210 bits number.  Then, you 
check the sum of that (4410) with a threshold.

By the way, multiplying two numbers of a specific amout of digits will 
always give a result that it's maximum number of digits will be the sum of 
the number of digits of both source numbers (by mathematical proof...).  Ex, 
in the case above, with any numbers of 1200 digits multiplied with any 
numbers of 3210 digits (what ever the base is), the result will always be 
4410 digits or a bit less (actually, no less than 1 digit less of the sum of 
digits, provided that you don't have leeding zeros).

>From: Jason Moxham <J.L.Moxham@maths.soton.ac.uk>
>Reply-To: J.L.Moxham@maths.soton.ac.uk
>To: gmp-discuss@swox.com
>Subject: multiplication of unequal sizes
>Date: Mon, 13 Jan 2003 02:29:50 +0000
>
>
>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


_________________________________________________________________
MSN 8 helps eliminate e-mail viruses. Get 2 months FREE* 
http://join.msn.com/?page=features/virus