Pseudocode of the 'The Fast Fourier Transform Algorithm'

fft_pseudocode.txt

function FFT(A, ω)
  Input: Coefficient representation of a polynomial A(x) of degree ≤ n − 1, where n is a power of 2
  Output: Value representation A(ω^0), . . . , A(ω^n−1)

  if ω = 1: return A(1)
  express A(x) in the form Ae(x^2) + xAo(x^2)
  call FFT(Ae, ω^2) to evaluate Ae at even powers of ω
  call FFT(Ao, ω^2) to evaluate Ao at odd powers of ω
  for j = 0 to n − 1:
    compute A(ω^j) = Ae(ω^2j) + ω^jAo(ω^2j)
  return A(ω^0), . . . , A(ω^n−1)

I think there is a typo in line 8, shouldn't it be odd?

Yes! It should be fixed now 🙂.