Quickly multiply two big integers via Fourier Transform

Week 4: Laplace and Fourier Transform


The fastest known algorithms for the multiplication of very large integers use the “polynomial multiplication method” which uses Fourier transform. [5]

 

Multiplying huge integers is an operation that occurs in many fields of Computational Science: Cryptography, Number theory, just to name a few. The problem is that traditional approaches to multiplication require O(n2) multiplication operations, where n is the number of digits. To see why, assume for example that we want to multiply the numbers 123 and 456. The normal way to do this is shown below.

We see that for two integers of length 3, this multiplication requires 3 x 3 = 9 operations, hence its O(n2complexity. Executing an O(n2) algorithm for huge n is very costly, so that is why it is preferred to use more efficient algorithms when multiplying huge integers. One way to do this more efficient (in O(n log(n))), is by using FFT’s (Fast Fourier Transforms).[4]

So how?

“a number can indeed be divided on a decimal basis and the product of two of them is equivalent to the convolution product which on its turn can be handled fastly with FFT.”[3]

1] Represent the integer as a polynomial

2] Use the multiplication algorithm for polynomials using FFT

3] O(n) carry-propagation step

Sources:

[1] https://www.quora.com/What-are-some-non-obvious-applications-of-the-Fourier-transform/answer/Lionel-Chiron (visited on May 21, 2017).

[2] https://math.stackexchange.com/questions/116674/what-is-the-fastest-way-to-multiply-two-digit-numbers#comment271358_116674 (visited on May 21, 2017).

[3] https://www.quora.com/What-are-the-major-applications-of-the-Fast-Fourier-Transform-FFT-to-algorithms-in-Computer-Science/answer/John-McGonagle (visited on May 21, 2017).

[4] (2017). Cs.rug.nl. Retrieved 21 May 2017, from http://www.cs.rug.nl/~ando/pdfs/Ando_Emerencia_multiplying_huge_integers_using_fourier_transforms_paper.pdf

[5] https://en.wikipedia.org/wiki/Discrete_Fourier_transform#Polynomial_multiplication (visited on May 21, 2017).
[6] https://en.wikipedia.org/wiki/Multiplication_algorithm#Fourier_transform_methods (visited on May 21, 2017).

Advertisements