Iterative Cache Optimized Karatsuba-Ofman multiplication algorithm

[Torbjorn Granlund]

Josh Liu <zliu2 at student.gsu.edu> writes:

  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.
  
This is interesting work.  Please make provisions for using the
assembly-based mpn_mul_basecase for your basecase code, if at all
possible.

-- 
Torbjörn