
Boost : 
Subject: Re: [boost] [math] Efficient polynomial multiplication
From: Lakshay Garg (lakshayg373_at_[hidden])
Date: 20170717 18:13:27
>
> â€‹[...] then a PR for the Karatsuba algorithm would be the best choice:
> most of the work would be in uprating 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 benchmarking result and have a
discussion.
Here are some benchmark results (using googlebenchmark):
 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â€‹
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk