multiplication of unequal sizes
Mon, 13 Jan 2003 12:45:04 -0500
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>
>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
>up doing floor(n/m) multiplications of size m by m , plus a few smaller
>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 of
>size n/2 by m (assuming m<n/2)
>I know how gmp does this unequal splitting , and also that it is not
>so what splitting is optimal ? , and are there any referances to papers on
MSN 8 helps eliminate e-mail viruses. Get 2 months FREE*