11–20 of 30 posts
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.
Fun article, but it was missing a little bit that took me a minute to get. So if you're already familiar with fourier transforms, this might be the missing piece to this article: Multiplication of polynomials when expressed in the domain of "array of coefficients" is a convolution operation: really you're summing (AB)_k = sum_{i=0}^k A_i B_{k-i} to find the kth coefficient of the result. The indices for B go backward…
This is technically not an O(n lg n) algorithm. Any O(n lg n) polynomial multiplication algorithm can be trivially turned into an O(n lg n) multiplication algorithm (just throw in some carries at the end), but O(n lg n) multiplication is an open problem. In this case the issue is that you need more and more precision for the FFT as the inputs get larger, or else you'll get the wrong answer. I think it ends up being a…
This is technically not an O(n lg n) algorithm. Any O(n lg n) polynomial multiplication algorithm can be trivially turned into an O(n lg n) multiplication algorithm (just throw in some carries at the end), but O(n lg n) multiplication is an open problem. In this case the issue is that you need more and more precision for the FFT as the inputs get larger, or else you'll get the wrong answer. I think it ends up being a…
IIRC if your polynomials have integer coefficients with a bounded number of digits you can use FFT on finite rings and get an actual O(n log n) algorithm.
This blog post is doing precise integer arithmetic without rounding, and dealing with polynomials of tiny degree. But for more general uses... Anyone trying to work with polynomials as continuous functions using floating point arithmetic (or trying to work efficiently with piecewise continuous functions in general) should check out Chebfun, http://www.chebfun.org People should avoid working with polynomials expressed…
This blog post is doing precise integer arithmetic without rounding, and dealing with polynomials of tiny degree. But for more general uses... Anyone trying to work with polynomials as continuous functions using floating point arithmetic (or trying to work efficiently with piecewise continuous functions in general) should check out Chebfun, http://www.chebfun.org People should avoid working with polynomials expressed…
This is technically not an O(n lg n) algorithm. Any O(n lg n) polynomial multiplication algorithm can be trivially turned into an O(n lg n) multiplication algorithm (just throw in some carries at the end), but O(n lg n) multiplication is an open problem. In this case the issue is that you need more and more precision for the FFT as the inputs get larger, or else you'll get the wrong answer. I think it ends up being a…
IIRC if your polynomials have integer coefficients with a bounded number of digits you can use FFT on finite rings and get an actual O(n log n) algorithm.
[deleted]
This is completely wrong. Big-theta does mean it's an upper bound, and also a lower bound. It certainly does not mean it's the exact number of steps; for example, 5x = Θ(3x), but 5x is more than 3x for all positive x.
This is technically not an O(n lg n) algorithm. Any O(n lg n) polynomial multiplication algorithm can be trivially turned into an O(n lg n) multiplication algorithm (just throw in some carries at the end), but O(n lg n) multiplication is an open problem. In this case the issue is that you need more and more precision for the FFT as the inputs get larger, or else you'll get the wrong answer. I think it ends up being a…
As you say, you can always convert to an integer multiplication problem so it stands at O(n lg(n) lg(lg(n))) (not O(n lg^2(n))).
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/C…
But anyway, coin change problem can be solved much faster. http://link.springer.com/article/10.1007%2Fs00453-007-0162-8