5 ms·

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,

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.

Kubuxu 2y ago
FFT is used extensively in curve based zero-knowledge cryptography, not for the purpose of splitting a single large number into smaller ones, but to interpolate and evaluate very large polynomials (for example of the degree 2^27). All of this happens in a field of an elliptic curve so the complexity reduction is greatly appreciated.
nickcw 2y ago
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 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 https://en.wikipedia.org/wiki/Karatsuba_algorithm
- pfdietz 2y ago
  The Karatsuba algorithm idea can also be used for multiplication of polynomials.
- kurlberg 2y ago
  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 http://gmplib.org/devel/log.i7.1024.png More context and explanation can be found at: http://gmplib.org/devel/ http://gmplib.org/devel/ BTW, I like Bernstein's survey of different multiplication algorithms at https://cr.yp.to/papers/m3.pdf https://cr.yp.to/papers/m3.pdf (there is a unifying theme about using ring isomorphisms to explain many of the "standard" routines.)
  - kurlberg 2y ago
    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 https://hal.science/hal-02070778v2/document A pop-sci description can be found at https://theconversation.com/weve-found-a-quicker-way-to-multiply-really-big-numbers-114923 https://theconversation.com/weve-found-a-quicker-way-to-mult...

Kubuxu 2y ago

FFT is used extensively in curve based zero-knowledge cryptography, not for the purpose of splitting a single large number into smaller ones, but to interpolate and evaluate very large polynomials (for example of the degree 2^27). All of this happens in a field of an elliptic curve so the complexity reduction is greatly appreciated.

nickcw 2y ago

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 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 https://en.wikipedia.org/wiki/Karatsuba_algorithm

pfdietz 2y ago
The Karatsuba algorithm idea can also be used for multiplication of polynomials.
kurlberg 2y ago
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 http://gmplib.org/devel/log.i7.1024.png More context and explanation can be found at: http://gmplib.org/devel/ http://gmplib.org/devel/ BTW, I like Bernstein's survey of different multiplication algorithms at https://cr.yp.to/papers/m3.pdf https://cr.yp.to/papers/m3.pdf (there is a unifying theme about using ring isomorphisms to explain many of the "standard" routines.)
- kurlberg 2y ago
  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 https://hal.science/hal-02070778v2/document A pop-sci description can be found at https://theconversation.com/weve-found-a-quicker-way-to-multiply-really-big-numbers-114923 https://theconversation.com/weve-found-a-quicker-way-to-mult...