Bottom-Up Karatsuba Algorithm

[Josh Liu]

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

http://sourcepost.sytes.net/sourceview.aspx?source_id=11636

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

http://www.student.gsu.edu/~zliu2

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.