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

41–50 of 61 posts

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

#41

Post by nickcw »

clearprop wrote: post #36
nickcw wrote: post #34

You can use this method to multiply long numbers together. The key insight you need is that polynomial multiplication is the same as normal long number multiplication without doing carrying. So suppose you have a 1000 digit number. You then take each digit and use it as the coefficient of a 1000 element polynomial. You can then multiply these polynomials together using the fft method as described in the article. To c…

Thanks for the comment. That makes sense, since as you are saying, a base10 number can be expressed as a polynomial where x=10. Eg: 983 = 9x^2 + 8x + 3 aka [9, 8, 3]. Wondering how big the number has to be to make sense, and where this is used in practice.

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 numbers together

https://en.wikipedia.org/wiki/Karatsuba_algorithm

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

#42

Post by lkuty »

joe_the_user wrote: post #21

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.

See 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"

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

#43

Post by guyomes »

cperciva wrote: post #20
dataflow wrote: post #12

Earlier quoted context omitted.

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

For FFT with floating-point numbers, another paper from Arnold Schönhage in 1982 [1] already gives the bound in Psi(n l) operations, where n is the number of coefficients, and l is the desired precision (typically 53 for double precision). Psi(m) is the time to multiply two integers with m digits, which is known since 2021 to be O(m log m) [2]. So the current bound is O(nl log(nl)).

[1]: https://doi.org/10.1007/3-540-11607-9_1

[2]: https://www.texmacs.org/joris/nlogn/nlogn-abs.html

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

#44

Post by pfdietz »

nickcw wrote: post #41
clearprop wrote: post #36

Earlier quoted context omitted.

Thanks for the comment. That makes sense, since as you are saying, a base10 number can be expressed as a polynomial where x=10. Eg: 983 = 9x^2 + 8x + 3 aka [9, 8, 3]. Wondering how big the number has to be to make sense, and where this is used in practice.

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…

The Karatsuba algorithm idea can also be used for multiplication of polynomials.

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

#47

Post by 8051Enthusiast »

joe_the_user wrote: post #21

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.

When 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

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

#48

Post by keepamovin »

So integer factoring is a discrete deconvolution? I wonder if juxtaposing the FFT representation (inverse pointwise multiplication) and the tableax (regular long multiplication / carry add) could break the symmetry and get enough information for a fast algorithm?

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

#50

Post by kurlberg »

nickcw wrote: post #41
clearprop wrote: post #36

Earlier quoted context omitted.

Thanks for the comment. That makes sense, since as you are saying, a base10 number can be expressed as a polynomial where x=10. Eg: 983 = 9x^2 + 8x + 3 aka [9, 8, 3]. Wondering how big the number has to be to make sense, and where this is used in practice.

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.)

Post reply on HN