Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!


Forgot your password?

Journal Journal: Bottom-Up Karatsuba-Ofman Multiplication Algorithm

This entry is also a kuro5hin diary entry.

The Karatsuba-Ofman algorithm for polynomial multiplication is a recursive method that reduces the number of point multiplications of polynomials at each step from the four needed by the schoolbook method to only three. In my implementation, I deconstructed the process of the recursive Karatsuba-Ofman algorithm and rearranged the multiplications so that it would be easier to design a bottom-up algorithm around it. A bottom-up algorithm computes results beginning with (logically) the most basic elements and builds up until the final result is obtained. In my method, the basecase multiplications (multiplications that can be done with a simpler algorithm) are computed first along with the factors that are the oprands for these basecase multiplications. The second step is the interpolation step where the basecase products are added and subtracted from each other at different positions to obtain the final answer.

The code, which is very preliminary, can be found here. Again, the code is very slow at the moment and even now, with the code in my repository, it is still a little slower than the recursive Karatsuba-Ofman implementation found in the GMP library. I plan to deconstruct the basecase multiplications and factor calculations in such a way that the operands are friendly to the processor cache. Another optimization is to arrange the interpolation stage in such a way that one of its components becomes O(1) instead of the original O(n).

Some people manage by the book, even though they don't know who wrote the book or even what book.