Discrete Fourier Transform

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:

--PaulMiller

CategoryMath CategoryAlgorithm