[...] then a PR for the Karatsuba algorithm would be the best choice: most of the work would be in up-rating the tests and doing performance testing to see what order of polynomial needs the more complex algorithm.
I have been doing some experiments with the Karatsuba multiplication algorithm. Karatsuba multiplication is outperforming the regular multiplication method for high degree polynomials (> 500). I believe it can still be improved since I haven't spent much time trying to optimize it. But before that I would like to share some bench-marking result and have a discussion. Here are some benchmark results (using google-benchmark): | Polynomial | TIME | | Size | Boost Polynomial | Naive array impl | Karatsuba array impl | |------------+------------------+------------------+----------------------| | 1 | 167 ns | 47 ns | 60 ns | | 2 | 163 ns | 59 ns | 93 ns | | 4 | 200 ns | 87 ns | 208 ns | | 8 | 231 ns | 134 ns | 264 ns | | 16 | 324 ns | 243 ns | 495 ns | | 32 | 601 ns | 534 ns | 1005 ns | | 64 | 1479 ns | 1873 ns | 2626 ns | | 128 | 5192 ns | 5280 ns | 7031 ns | | 256 | 18512 ns | 18215 ns | 18221 ns | | 512 | 79322 ns | 66010 ns | 54160 ns | | 1024 | 267440 ns | 247470 ns | 152651 ns | | 2048 | 1158600 ns | 968172 ns | 433985 ns | |------------|------------------|------------------|----------------------| | Complexity | 0.34 N^2 | 0.23 N^2 | 2.47 N^1.585 | | BigO RMS | 15 % | 2 % | 5 % | Boost Polynomial -> Polynomial class in the boost.math library Naive array impl -> O(N^2) polynomial multiplication on plain C arrays Karatsuba array -> Karatsuba polynomial multiplication using plain C arrays Looking at the data, I'm wondering why is boost's implementation so slow for polynomials of lower degree? I could not see any obvious reason by looking at the source. -- Lakshay