Re:History and Derivation of the Fast Fourier Transform
by dbaupp on Monday March 20, 2017 @06:41PM
(#13918280)
My impression is Winograd FFT is still O(N log N), i.e. exactly the same complexity as Cooley-Tukey. That said, they work best on different N, which is possibly what you're referring to?
[ Parent
| on HN ]
Re:History and Derivation of the Fast Fourier Transform
by hughw on Monday March 20, 2017 @08:39PM
(#13918894)
A nice table from the book at [1]. For block length 1024, CT radix 2 requires ~20k multiplies and ~30k adds. Block length 1008 Winograd requires ~4k multiplies and ~35k adds.
[1] https://books.google.com/books?id=8sbS2Bi4BmIC&pg=PA396&lpg=...