Integer multiplication by FFT

Autor/Urheber:

Dcoetzee

Shortlink:

https://dewiki.de/b/16641e

Quelle:

Wikimedia Commons

Größe:

666 x 580 Pixel (80688 Bytes)

Beschreibung:

A demonstration of an integer multiplication based on fast Fourier transforms (FFTs) using a number theoretic transform in the finite field of order 337, choosing 85 as an 8th root of unity (since the input vectors are of length 8). Base 10 is used (normally a power of 2 would used, but 10 is convenient for demonstration), and this technique is overkill for integers of this size (long multiplication would be superior). Because the inputs have 4 digits and the maximum product of two digits in base 10 is 9², the base was chosen as the first prime p greater than 4×9² = 324 where 8 is invertible in the integers modulo p (in this example any suitable base > 61, such as 73, would suffice, but we don't know that a priori). The computation at the top shows how the same acyclic convolution can be computed naively by "long multiplication without carrying," showing the relationship to multiplication. The computation in the lower right shows recombination/carrying of the result vector by (decimal) shifts and adds to obtain the final integer result. Note that all recursive multiplications are of smaller, 3-digit integers. Values are all accurate and were computed using the following Mathematica code:

Lizenz:

CC0

Bild teilen: