Re: [boost] [math] Efficient polynomial multiplication

Subject: Re: [boost] [math] Efficient polynomial multiplication
From: Lakshay Garg (lakshayg373_at_[hidden])
Date: 2017-07-17 18:13:27

>
> ​[...] 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​