Re: [boost] [math] Efficient polynomial multiplication

Subject: Re: [boost] [math] Efficient polynomial multiplication
From: John Maddock (jz.maddock_at_[hidden])
Date: 2017-07-13 12:35:41

On 13/07/2017 06:00, Lakshay Garg via Boost wrote:
> Hello all
>
> This is my first post to the mailing list.
>
> While looking at the source code for polynomial multiplication
> (boost/math/tools/polynomial.hpp) I discovered that the library used
> O(N^2) algorithm for multiplication. I would like to work on
> implementing a more efficient algorithm (complexity: O(N log(N))).
>
> I am writing this mail to get views and feedback from the community
> and have a healthy discussion before starting the work.

There has been some work towards this here: 
https://github.com/boostorg/math/pull/32, but it's a long way from ready 
to go.

The Karatsuba algorithm is probably/possibly of more interest than FFT 
based ones too: as FFT's only really kick in when the digit count is 
exceptionally large.

So I would say if you're looking for something to do, 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.

Best, John Maddock.

---
This email has been checked for viruses by AVG.
http://www.avg.com