News for hackers. Stuff that matters.
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?
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=...

Re:History and Derivation of the Fast Fourier Transform by dbaupp on Monday March 27, 2017 @11:20AM (#13968420)
I see. That sounds like a smaller constant factor, rather than a lower complexity.