File:Integer multiplication by FFT.svg
Summary
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 92, the base was chosen as the first prime p greater than 4×92 = 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:
Licensing
Lua error in package.lua at line 80: module 'strict' not found.
File history
Click on a date/time to view the file as it appeared at that time.
| Date/Time | Thumbnail | Dimensions | User | Comment | |
|---|---|---|---|---|---|
| current | 23:22, 13 January 2017 | | 666 × 580 (79 KB) | 127.0.0.1 (talk) | 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<sup>2</sup>, the base was chosen as the first prime <i>p</i> greater than 4×9<sup>2</sup> = 324 where 8 is invertible in the integers modulo <i>p</i> (in this example any suitable base > 61, such as 73, would suffice, but we don't know that <i>a priori</i>). 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: |
- You cannot overwrite this file.
File usage
The following 2 pages link to this file:
