Bottom-Up Karatsuba Algorithm
zliu2 at student.gsu.edu
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
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 gsu.edu
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