Earlier quoted context omitted.
Thanks, not often we see Knuth erratas. :)
You never see "erratas", since "errata" is already the plural (of "erratum").
The ensemble of errata of multiple books are erratas… probably.
Convolutions, Fast Fourier Transform and polynomials (2022)
51–60 of 61 posts
Re: Convolutions, Fast Fourier Transform and polynomials (2022)
#52Earlier quoted context omitted.
In libgmp I think the numbers have to be around 100,000 bits or 30,000 digits for FFT to be faster. https://gmplib.org/manual/Multiplication-Algorithms GMP has lots of other methods in between schoolbook multiplication and FFT multiplication. A nice one is Karatsuba multiplication which is very easy to understand and delivers O(n^1.58) rather than O(n^2) performance. Python uses this method for multiplying large numb…
There is a nice picture of the "best" for different ranges of sizes of numbers to be multiplied at http://gmplib.org/devel/log.i7.1024.png More context and explanation can be found at: http://gmplib.org/devel/ BTW, I like Bernstein's survey of different multiplication algorithms at https://cr.yp.to/papers/m3.pdf (there is a unifying theme about using ring isomorphisms to explain many of the "standard" routines.)
PS: if you're interested in multiplying "ludicrously large numbers", Harvey and van der Hoeven had a nice breakthrough and got multiplication down to "FFT speed" (n*log(n)), see
https://hal.science/hal-02070778v2/document
A pop-sci description can be found at
https://theconversation.com/weve-found-a-quicker-way-to-mult...
Re: Convolutions, Fast Fourier Transform and polynomials (2022)
#53Note that the FFT has this property of “convolution is pointwise multiplication” for any cyclic multiplicative group, see https://www.sciencedirect.com/science/article/pii/S002200007... for a more algebraic derivation.
Some call this a “harmonic” fft, and there are also non-harmonic FFTs:
- the “additive NTT” of [LCH14] on GF(2^n)
- the circle fft on the unit circle X^2+Y^2=1 of a finite field [HLP24]
- the ecfft on a sequence of elliptic curve isogenies [BCKL21]
[LCH14]: https://arxiv.org/abs/1404.3458
[HLP24]: https://eprint.iacr.org/2024/278
[BCKL21]: https://arxiv.org/pdf/2107.08473
Re: Convolutions, Fast Fourier Transform and polynomials (2022)
#54The key ”trick” of the operation seems to be this revelation: > In other words, performing the convolution of two signals in time domain is equivalent to multiplying them in the frequency domain. Great article, as it breaks down a complex idea into much smaller steps that even my math challenged mind can somehow grasp, but did I miss a step? Or is it left as an exercise to the reader to look up? I was already stretch…
Thanks! In case it helps: * Multiplying two polynomials as taught in school is in reality a convolution. * "performing the convolution of two signals in the time domain is equivalent to multiplying them in the frequency domain" * FFT allows us to convert from time domain to frequency domain * We use FFT to convert our polynomial to frequency domain. * If we are now in the frequency domain, we just need to multiply. F…
Yep, it definitely helps! What I'm struggling to understand is why "performing the convolution of two signals in the time domain is equivalent to multiplying them in the frequency domain" (I'm going to google/gpt it, this is more of an exercise left for me to dive into, your post is perfect as it is)
Re: Convolutions, Fast Fourier Transform and polynomials (2022)
#55I'd like the article even more if it used numpy.convolve in the benchmark.
comparing pure python and numpy fft feels not right to me.
the result will be similar, sure, but the effect might then only show for much larger inputs.
Re: Convolutions, Fast Fourier Transform and polynomials (2022)
#56Sure, the naive method of multiplying polynomials is slow in the degree of the polynomial. But when does one have to deal with two degree 100 polynomials? My impression is that this sort of method isn't used by computer algebra system for this reason.
Extremely common in error correction and signal processing.
https://www.youtube.com/watch?v=CcZf_7Fb4Us
https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_cor... is one example.
Re: Convolutions, Fast Fourier Transform and polynomials (2022)
#57[dead]
Re: Convolutions, Fast Fourier Transform and polynomials (2022)
#58[dead]
Re: Convolutions, Fast Fourier Transform and polynomials (2022)
#59Interesting. I've just implemented an algorithm (matrix profile) that makes use of FFT to compute a big set of dot products of time series subsequences where the length n of the time series can be in 100s of millions. The fast convolution computation using FFT reduces the computation time from O(n) to O(log n) with awesome speed gains at this scale. Throw in a GPU and the speed goes up even faster, like processing 10 million data point in 0.1 second on a laptop.
Re: Convolutions, Fast Fourier Transform and polynomials (2022)
#60I'd like the article even more if it used numpy.convolve in the benchmark. comparing pure python and numpy fft feels not right to me. the result will be similar, sure, but the effect might then only show for much larger inputs.
Great feedback. I have updated the post using convolve instead. There is a huge difference convolve/naive. On the other hand, convolved is slower than the FFT as expected, but for greater than 3000 degree polynomials or so.
See diff: https://github.com/alrevuelta/myblog/commit/9fcc3dc84b1d9b66...