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