Iterative Cache Optimized Karatsuba-Ofman multiplication algorithm

Josh Liu zliu2 at
Tue Feb 24 22:12:00 CET 2004

I'm currently working on an iterative cache optimized Karatsuba-Ofman 
multiplication algorithm. The premise behind the algorithm is that one 
performs the basecase multiplies in the first part of the non-recursive 
function and then the interpolation stage operates next. The algorithm 
will not use an explicit stack structure because it will be based 
primarily on loops. The cache optimized part comes from the fact that 
the operands to the basecase multiplies will be ordered in such a way 
that they are lined up in spatially with regards to the execution 
order. The basecase multiplies will be deconstructed so that the 
products will be computed simultaneously because the lines of the a 
group products will be formed together. I have the indices of the 
basecase multiplies currently and I will work on the interpolation 
stage later. I hope to be finished in two to three weeks.

More information about the gmp-devel mailing list