One interesting property of the DFT is that you can use it to multiply ArbitraryPrecision integers quickly. If x and y are two (at most) n-digit numbers, you can compute xy mod 2^N + 1 (where N >= 2n * 2^k + k and 2^k divides 2^N) by the following algorithm:
Given: routines DFT (v), IDFT (v), which compute, respectively, the discrete Fourier and inverse discrete Fourier transforms of v
def fft_multiply (x, y):
if n is not a power of 2:
let k be the least power of 2 > n
pad x and y with zeros until they are both k digits long.
(the DFT algorithm likes its input to be of size a power of 2)
split x and y into vectors with components consisting of 2^k digits each.
Call these vectors x[] and y[].
let k be the number of digits in x and y.
let X = DFT (x[]) and Y = DFT (y[]). (X and Y are also vectors of length k)
let X @ Y be the componentwise product of X and Y.
(i.e. (X@Y)_{i} = X_i * Y_i)
return IDFT (X @ Y)
It looks like magic, but it relies on something called the ConvolutionTheorem, which says precisely that IDFT (DFT(x) @ DFT (y)) = x * y.
Anyway, I thought this was pretty cool. :-) You can get more details at:
- http://en.wikipedia.org/wiki/Discrete_Fourier_transform
- http://en.wikipedia.org/wiki/Schönhage-Strassen_algorithm
- http://en.wikipedia.org/wiki/Cooley-Tukey_FFT_algorithm
CategoryMath CategoryAlgorithm