 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2010/ii/paper-2/39a/1/solution

Separate even and odd indices, using

ω_{2 m}^{2} = ω_{m}

. Then

x_{ℓ} = x_{ℓ}^{(E)} + ω_{2 m}^{ℓ} x_{ℓ}^{(O)}, x_{ℓ + m} = x_{ℓ}^{(E)} - ω_{2 m}^{ℓ} x_{ℓ}^{(O)} (0 \leq ℓ < m) .

The second identity uses

ω_{2 m}^{m} = - 1

. Each FFT butterfly uses one shared twiddle-factor product and two additions, so assembly costs

m

2 m

 New to topics? Read the docs here!