I realize that this not related to the topic of the post at all, but... why on earth would you (try to) make a pun and then add "(Haha, get it?)" at the end? At least for me, that takes all the fun out of getting a joke :(
How to multiply polynomials in Θ(n log n) time
21–30 of 30 posts
Re: How to multiply polynomials in Θ(n log n) time
#22I realize that this not related to the topic of the post at all, but... why on earth would you (try to) make a pun and then add "(Haha, get it?)" at the end? At least for me, that takes all the fun out of getting a joke :(
I'm not a native English speaker and I had some trouble understanding that pun.
> So how do we do it? We are going to have to talk a bit about the representation of polynomials in computer memory first. (Haha get it?)
Without that hint I would have totally missed it.
Also, this could be a joke on the joke. Probably the author didn't really think this pun is funny, and made fun of themselves by overstating how funny that pun is. Humor is a large field with lots of varieties. (And no, I will not spoil that this is a maths pun.)
Re: How to multiply polynomials in Θ(n log n) time
#23Fun 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 mentioned in the article in the problem explanation section, but quickly and just passing by. I'll put it right at the beginning where it belongs. Thanks!
I had not understood properly on first read of your comment, but you did not mean what is on the post at all. I'll include this insight somehow :)
Don't you mean signal domain though?
Re: How to multiply polynomials in Θ(n log n) time
#24Earlier quoted context omitted.
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 is not quite correct. A finite ring can only have finitely many primitive roots of unity, so the length of the FFTs you can compute in a ring of fixed size is bounded. To compute arbitrarily long convolutions over a finite ring, you need to extend the ring with more roots of unity (for example, using the Schönhage-Strassen trick), and this increases the complexity.
I think you're right, but it depends on what's your computational model. In word-RAM you usually assume that log n < w where w is the machine word, and you can do arithmetical operations on words in O(1), so if your coefficients fit in w bits the complexity is O(n log n). You could say it's a trick but it's a convenient trick, since on a real-world machines w is much larger than you need (64). I don't know if you can make the same argument about floating point computations.
Re: How to multiply polynomials in Θ(n log n) time
#25> This is the operation called discrete convolution, and it’s the equivalent of multiplying two polynomials in coefficient form.
As a physicist my first thought would be that convolution is simply multiplying in Fourier-space anyway, no need to think about polynomials. I didn't know the application of FFT for polynomials though so thanks for that.
Re: How to multiply polynomials in Θ(n log n) time
#26Can 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…
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
Thanks! That paper is available on the author's website:
http://gi.cebitec.uni-bielefeld.de/people/zsuzsa/papers/Algo...
Re: How to multiply polynomials in Θ(n log n) time
#27I realize that this not related to the topic of the post at all, but... why on earth would you (try to) make a pun and then add "(Haha, get it?)" at the end? At least for me, that takes all the fun out of getting a joke :(
I'm not a native English speaker and I had some trouble understanding that pun. > So how do we do it? We are going to have to talk a bit about the representation of polynomials in computer memory first. (Haha get it?) Without that hint I would have totally missed it. Also, this could be a joke on the joke. Probably the author didn't really think this pun is funny, and made fun of themselves by overstating how funny t…
Can please somebody explain what the pun is supposed to be for us who definitely don't see anything except the normal sentence? That he used "talk a bit" in the sentence that announces consideration of how computer memory works? I'm really disappointed then.
Re: How to multiply polynomials in Θ(n log n) time
#28Fun 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 mentioned in the article in the problem explanation section, but quickly and just passing by. I'll put it right at the beginning where it belongs. Thanks! I had not understood properly on first read of your comment, but you did not mean what is on the post at all. I'll include this insight somehow :) Don't you mean signal domain though?
Yeah I messed that domain up. Thanks.
Re: How to multiply polynomials in Θ(n log n) time
#29Earlier quoted context omitted.
I'm not a native English speaker and I had some trouble understanding that pun. > So how do we do it? We are going to have to talk a bit about the representation of polynomials in computer memory first. (Haha get it?) Without that hint I would have totally missed it. Also, this could be a joke on the joke. Probably the author didn't really think this pun is funny, and made fun of themselves by overstating how funny t…
Can please somebody explain what the pun is supposed to be for us who definitely don't see anything except the normal sentence? That he used "talk a bit" in the sentence that announces consideration of how computer memory works? I'm really disappointed then.
Yes, it's this pun. I did not intend it as a pun, but then I read what I'd written and chuckled. I thought I myself would miss it when reading someone else's article (I'd read with less of a critical eye for form), so I made sure to mark it.
Re: How to multiply polynomials in Θ(n log n) time
#30Earlier quoted context omitted.
Can please somebody explain what the pun is supposed to be for us who definitely don't see anything except the normal sentence? That he used "talk a bit" in the sentence that announces consideration of how computer memory works? I'm really disappointed then.
Yes, it's this pun. I did not intend it as a pun, but then I read what I'd written and chuckled. I thought I myself would miss it when reading someone else's article (I'd read with less of a critical eye for form), so I made sure to mark it.
Thanks! Please do write about the task for which you had to use the presented solution. Is the expected input on which the problem is evaluated really like "100K of golf holes and 100K of possible robot distances"? I don't know anything about these contests and I was not able to find the input on which the program is going to be measured (if I understand the speed is measured?)