Codes, cryptography and algorithms · Maths EE idea · Ambitious
Why the fast Fourier transform is fast
A research question to start from
How does the fast Fourier transform reduce the work of a discrete Fourier transform from about n² to about n log n operations?
A starting point, not your question: change the case, the comparison or the limit until it is yours. The research-question builder helps you check it.
Why it works as a maths EE
Roots of unity and recursion combine into a provable speed-up.
Mathematics you would need
- Complex roots of unity
- The discrete Fourier transform
- Divide and conquer
- Recurrences for operation counts
Much of this goes beyond the DP course. That is expected in a maths EE, but you must understand and explain everything you use.
One possible line of attack
- Define the DFT and compute small cases.
- Derive the radix-2 FFT splitting.
- Solve the operation-count recurrence.
- Apply to polynomial multiplication.
Scope and difficulty
Ambitious. Ambitious.
Pitfalls
- Signal-processing focus.
- Recurrence not solved.
Where to start reading
Search a library catalogue or a university's open lecture notes for: FFT derivation roots of unity radix-2; polynomial multiplication FFT. Prefer textbooks, lecture notes and journal articles to a single website, and cite everything you use (how to reference a maths EE).
Make it your EE
Similar ideas
- How many comparisons does sorting need?Codes & algorithmsSolid
- Ranking web pages with eigenvectorsCodes & algorithmsAmbitious
- How random are pseudo-random numbers?Codes & algorithmsSolid
- Why RSA encryption worksCodes & algorithmsSolid
All codes, cryptography and algorithms ideas · the full ideas library