Trinity S³AI
The FFT butterfly: N log N instead of N^2
Pick a size, an input and a stage. See every butterfly pair, its twiddle on the unit circle and the values flowing through, and count the work against a direct DFT.
Trinity S³AI
Pick a size, an input and a stage. See every butterfly pair, its twiddle on the unit circle and the values flowing through, and count the work against a direct DFT.