6 ms·
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 multipli
by nickcw 2y ago
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 convert the result back to a number you need to do the carries. So if an element is bigger than 10 you carry the excess to the next digit. You then take the coefficients and turn them into numbers.
That's the basic idea. There is some subtlety I've glossed over due to precision needed for the carries and to be sure that rounding the fft result to the nearest integer is correct. That is the way big number multiplication is done in GMP which is the leading Library for this sort of thing.
- clearprop 2y agoThanks 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 agoFFT 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 agoIn 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 agoThe Karatsuba algorithm idea can also be used for multiplication of polynomials.
- kurlberg 2y agoThere 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 agoPS: 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...