How to multiply polynomials in Θ(n log n) time

Re:How to multiply polynomials in Θ(n log n) time by nonsequitur on Monday September 07, 2015 @08:27PM (#10183641)

Can anybody guess in which way he used convolution for solving what is generally known as the change-making problem? Wikipedia [1] mentions a "probabilistic convolution tree", but that seems much more involved.

Edit: Solved. I've missed that the problem only deals with change amounts that can be reached with one or two coins. So a single convolution is sufficient in this specific case.

https://en.wikipedia.org/wiki/Change-making_problem

[ Parent | on HN ]

Re:How to multiply polynomials in Θ(n log n) time by chaoxu on Tuesday September 08, 2015 @02:12AM (#10184296)

probabilistic convolution tree is not much more involved. In some sense it's just multiple polynomial multiplication.

But anyway, coin change problem can be solved much faster. http://link.springer.com/article/10.1007%2Fs00453-007-0162-8

[ Parent | on HN ]

Re:How to multiply polynomials in Θ(n log n) time by nonsequitur on Tuesday September 08, 2015 @04:46AM (#10184632)

Thanks! That paper is available on the author's website: http://gi.cebitec.uni-bielefeld.de/people/zsuzsa/papers/Algo...

[ Parent | on HN ]