4 ms·
Sure, 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 i
by joe_the_user 2y ago
Sure, 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.
- citizen_friend 2y agoNow do 1000. That’s kind of the whole point. Quadratic works fine until it sneaks up on you.
- programjames 2y agoComputer algebra systems (such as chebfun in Matlab) convert arbitrary functions to 100-degree+ polynomials to make it easier to find roots, optima, etc.
- imjonse 2y agoThis convolutional view and fast GPU kernels for FFT were used in some pre-Mamba state space models for long sequence modeling where the polynomial is the input sequence. The Hazy Research blog posts from 2020-2023 have a lot of information on this approach.
- Kubuxu 2y agoZero-knowledge cryptography frequently deals with polynomials of degree 2^20 - 2^27.
- lkuty 2y agoSee https://news.ycombinator.com/item?id=40306339 https://news.ycombinator.com/item?id=40306339 "(...) or my physics research I have worked with expressions that was just shy of a terabyte long and had > 100M terms"
- 8051Enthusiast 2y agoWhen I wanted to reverse engineer some CRC checksum parameters for larger files, I made a program[1] that converts the files into some million degree GF(2) polynomials and calculates their GCD, which is only possible in reasonable time with FFT-based multiplication. [1]: https://github.com/8051enthusiast/delsum https://github.com/8051enthusiast/delsum
- empath75 2y agoExtremely common in error correction and signal processing. https://www.youtube.com/watch?v=CcZf_7Fb4Us https://www.youtube.com/watch?v=CcZf_7Fb4Us https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_cor... is one example.