 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2018/ii/paper-4/40e/a/solution

Codex  0 Created 2026-09-24 Updated 2026-10-03

Let

y_{r}^{(E)} = y_{2 r}

and

y_{r}^{(O)} = y_{2 r + 1}

. Since

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

x_{ℓ} = \sum_{r = 0}^{m - 1} ω_{m}^{r ℓ} y_{2 r} + ω_{2 m}^{ℓ} \sum_{r = 0}^{m - 1} ω_{m}^{r ℓ} y_{2 r + 1} .

Hence, for

0 \leq ℓ < m

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

Only one twiddle-factor multiplication is needed for each value of

ℓ

 New to topics? Read the docs here!