Square Dance FFT · ALG 17.1–17.3

FFT evaluates a polynomial P of size n at the n points ω⁰, …, ωⁿ⁻¹, where ω is a primitive n-th root of unity. It splits P(x) = P_s(x²) + x·P_ℓ(x²) and recurses. Explore why this works below, then test yourself in the game.

1. Why roots of unity? Square the points.

n =

2. The graph of a polynomial (ALG 17.1)

number of points = Drag the orange points up and down.

3. The game

time –

score 0

streak 0

best sprint 0

Questions mix all three ideas: where points go when squared, the split into P_s and P_ℓ, and the FFT "butterfly" y_j = s_j ± ω^j·ℓ_j. A butterfly is worth 2 points. Keys: 1–4 pick an answer, Enter = next.

Fun fact: Gauss used this divide-and-conquer trick around 1805 to interpolate asteroid orbits. It was published only after his death, and the method became famous when Cooley and Tukey rediscovered it in 1965.

← ADS2 Arcade