Boost logo

Boost :

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:, 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.

Boost list run by bdawes at, gregod at, cpdaniel at, john at