Invariant multiplier in Karatsuba/Toom

[Josh Liu]

I mentioned non-recursive variants of the Karatsuba-Ofman algorithm in 
two posts to this list. The code I put up, here at:

http://www.student.gsu.edu/~zliu2/centrinia.tar.bz2

directory 
centrinia/base/design/N/large/multiplication/Karatsuba__Ofman/iterative

is slower than its recursive counterpart. This is because it is only a 
direct translation of the recursive version into an iterative algorithm 
with naive use of stacks.
I am currently working on an iterative Karatsuba algorithm that will 
involve the deconstruction of the basecase multiplications so that I 
can order them in such a way that they can be done in serial, with 
regards to spatial order. It involves the multiplication of factors 
that require no subtractions first, then factors that are differences 
with one subtraction next, then three subtractions, then seven 
subtractions, and so on. Some repeated subtractions will be eliminated. 
The important part is that this method can be implemented to take 
advantage of the dependencies of each level of the subtraction chain. 
The indices of the interpolation has a structure very  similar to that 
of the indices of the basecase multiplies and subtractions and can be 
done just as easily.

P.S. Please email me if you want any information regarding the 
iterative cache optimized Karatsuba-Ofman algorithm.