Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Convolutions, Fast Fourier Transform and polynomials (2022)

alvarorevuelta.com

Post reply on HN
Print view View original

11–20 of 61 posts

Re: Convolutions, Fast Fourier Transform and polynomials (2022)

#11

Post by cperciva »

programjames wrote: post #3

Something that always bothers me about these explanations is they usually forget about numerical errors. You can't just abstract away multiplying coefficients as "constant time". You may as well abstract away the entire multiplication to begin with! If you take into account numerical precision, it's closer to O(n (log n)^3) [1]. [1]: http://numbers.computation.free.fr/Constants/Algorithms/fft....

The error bound cited in that article is wildly pessimistic. The latest edition of Knuth has the correct bound (because I gave it to him).

Re: Convolutions, Fast Fourier Transform and polynomials (2022)

#12

Post by dataflow »

cperciva wrote: post #11
programjames wrote: post #3

Something that always bothers me about these explanations is they usually forget about numerical errors. You can't just abstract away multiplying coefficients as "constant time". You may as well abstract away the entire multiplication to begin with! If you take into account numerical precision, it's closer to O(n (log n)^3) [1]. [1]: http://numbers.computation.free.fr/Constants/Algorithms/fft....

The error bound cited in that article is wildly pessimistic. The latest edition of Knuth has the correct bound (because I gave it to him).

Would you mind just sharing it here...?

Re: Convolutions, Fast Fourier Transform and polynomials (2022)

#13

Post by dataflow »

xphos wrote: post #8
e-khadem wrote: post #5

Earlier quoted context omitted.

But if the coefficients are integers, you can use NTT with a big enough modulus and get exact results and a boost (esp. in hardware) in multiplication time.

Had no clue what NTT was but found this as a reference https://codeforces.com/blog/entry/48798#:~:text=NTT%20(Numbe... .

See chapter 26 of the "FXT book". I just shared it here: https://news.ycombinator.com/item?id=40841355

Re: Convolutions, Fast Fourier Transform and polynomials (2022)

#14

Post by uoaei »

programjames wrote: post #3

Something that always bothers me about these explanations is they usually forget about numerical errors. You can't just abstract away multiplying coefficients as "constant time". You may as well abstract away the entire multiplication to begin with! If you take into account numerical precision, it's closer to O(n (log n)^3) [1]. [1]: http://numbers.computation.free.fr/Constants/Algorithms/fft....

Hence the distinction between computer science and software engineering. :)

Re: Convolutions, Fast Fourier Transform and polynomials (2022)

#15

Post by sigil »

Who was the first person to propose FFTs for faster polynomial multiplication?

Got curious about this recently. I’m not great at citation tracing, but did make it back to this 1995 paper by David Eppstein [0] where he uses it to efficiently solve Subset Sum after an incremental update. Surely Knuth’s TAOCP had it even earlier?

The fact that FFT polynomial multiplication also lets you solve Exact Subset Sum with Repetition in sub-exponential time came as a real shock to me. [1] Crucially, this algo is O(N log N) where N = the maximum element, not N = the set size, so it isn’t a P ≠ NP counterexample or anything.

[0] https://escholarship.org/content/qt6sd695gn/qt6sd695gn.pdf

[1] https://x.com/festivitymn/status/1788362552998580473?s=46&t=...

Re: Convolutions, Fast Fourier Transform and polynomials (2022)

#16

Post by cornstalks »

sigil wrote: post #15

Who was the first person to propose FFTs for faster polynomial multiplication? Got curious about this recently. I’m not great at citation tracing, but did make it back to this 1995 paper by David Eppstein [0] where he uses it to efficiently solve Subset Sum after an incremental update. Surely Knuth’s TAOCP had it even earlier? The fact that FFT polynomial multiplication also lets you solve Exact Subset Sum with Repet…

The Schönhage–Strassen algorithm from 1971 is basically a polynomial multiplication using FFTs: https://en.m.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Stras...

Re: Convolutions, Fast Fourier Transform and polynomials (2022)

#17

Post by npalli »

sigil wrote: post #15

Who was the first person to propose FFTs for faster polynomial multiplication? Got curious about this recently. I’m not great at citation tracing, but did make it back to this 1995 paper by David Eppstein [0] where he uses it to efficiently solve Subset Sum after an incremental update. Surely Knuth’s TAOCP had it even earlier? The fact that FFT polynomial multiplication also lets you solve Exact Subset Sum with Repet…

Earliest maybe Gentleman and Sande from 1966 and a kickass title (for '66) - "Fast Fourier Transforms: for fun and profit"

https://www.cis.rit.edu/class/simg716/FFT_Fun_Profit.pdf

Re: Convolutions, Fast Fourier Transform and polynomials (2022)

#18

Post by pbsd »

sigil wrote: post #15

Who was the first person to propose FFTs for faster polynomial multiplication? Got curious about this recently. I’m not great at citation tracing, but did make it back to this 1995 paper by David Eppstein [0] where he uses it to efficiently solve Subset Sum after an incremental update. Surely Knuth’s TAOCP had it even earlier? The fact that FFT polynomial multiplication also lets you solve Exact Subset Sum with Repet…

Pollard [1], Nicholson [2], and Schonhage-Strassen [3] seem to have come up with it independently around the same time, using different approaches. Strassen is said to have discovered the Pollard approach in 1968 but there is no (written) record of it.

It should also be noted that, while it was not exactly the birth of the FFT, Cooley-Tukey's 1965 paper [4] on it was what kickstarted research on FFT and its applications. This was just a few years after that.

[1] https://doi.org/10.1090/S0025-5718-1971-0301966-0

[2] https://doi.org/10.1016/S0022-0000(71)80014-4

[3] https://doi.org/10.1007/BF02242355

[4] https://doi.org/10.1090/S0025-5718-1965-0178586-1

Re: Convolutions, Fast Fourier Transform and polynomials (2022)

#19

Post by adgjlsfhk1 »

programjames wrote: post #9
e-khadem wrote: post #5

Earlier quoted context omitted.

But if the coefficients are integers, you can use NTT with a big enough modulus and get exact results and a boost (esp. in hardware) in multiplication time.

Is there a way to find groups with easy generators/primitive roots? I imagine you'd want a small root of unity, but also be able to choose a bigger modulus for extra big multiplications. Also, afaik it's discrete-logarithm level of difficulty to even find a generator if you choose a random modulus, though I don't know if it's easier to find a modulus after you choose the generator.

since the groups you're looking at are is size log(n), you can do a lot of work without issue. as long as you do experimental it less work, it doesn't affect the runtime.

Re: Convolutions, Fast Fourier Transform and polynomials (2022)

#20

Post by cperciva »

dataflow wrote: post #12
cperciva wrote: post #11

Earlier quoted context omitted.

The error bound cited in that article is wildly pessimistic. The latest edition of Knuth has the correct bound (because I gave it to him).

Would you mind just sharing it here...?

Short answer is that FFTs are about as well behaved as anything can possibly be, because they're rotations in C^n.

Explicit bound is in https://www.daemonology.net/papers/fft.pdf

Post reply on HN