Bottom-Up Karatsuba Algorithm

Josh Liu zliu2 at
Sat Mar 6 21:19:57 CET 2004

I have a bottom-up Karatsuba multiplication algorithm. It is based on 
first doing the base multiplies in one loop and then the interpolation 
in a second loop (actually there are more loops in the code since I 
need to allocate memory and unroll certain parts of the basecase loop).

A preview is here at sourcepost

I will post a compilable version either tomorrow (3/7/04) or Monday 
(3/8/04) at

The code is currently a little slower than the GMP version but then 
again there are some very obnoxious speed bumps that I haven't yet 
removed. This bottom-up code can be tailored to become cache optimized 
with some major changes to the loop structure. The thresholds for this 
algorithm is around 16 limbs on a Pentium 4. I will update the 
link periodically with newer versions of my bottom-up code.

I hope that this can be of use to GMP.

More information about the gmp-devel mailing list