The FFT Butterfly

Split the sum by parity and the transform collapses from n² terms to log₂n passes of a two-line butterfly — the same multi-pass gather every ladder in this course uses.

6 tasks

1. Where the Saving Comes From
2. The Butterfly: One Thread, One Output
3. Put the Input in the Right Order
4. Drive log₂n Passes
5. Same Answer, Two Centuries Apart
6. Run It Backwards for Free

Start this module →

This page is an interactive exercise — the editor, the GPU runner and your saved progress need JavaScript. The text above is the full brief.