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
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
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk