4 ms·
I recommend Fast Algorithms for Digital Signal Processing, by Blahut, 1985 for a mind-expanding survey of all the work in this area up to that time. Winograd FF
by hughw 10y ago
I recommend Fast Algorithms for Digital Signal Processing, by Blahut, 1985 for a mind-expanding survey of all the work in this area up to that time. Winograd FFT is even lower complexity than C-T. And the book spends a lot of time on fast DFTs over integer fields of size a Mersenne or Fermat prime. It's tragic how many transistors we've wasted doing floating point math on what is essentially an integer problem.
- dbaupp 10y agoMy 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?
- hughw 10y agoA 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=PA396&dq=blahut+winograd+fft&source=bl&ots=fpxNovGZgd&sig=lg7WxOLB2rfVMBAuagSKzfQPxVM&hl=en&sa=X&ved=0ahUKEwjFpKT5rObSAhWBKCYKHTRSAXgQ6AEIJDAC#v=onepage&q=blahut%20winograd%20fft&f=false https://books.google.com/books?id=8sbS2Bi4BmIC&pg=PA396&lpg=...
- dbaupp 10y agoI see. That sounds like a smaller constant factor, rather than a lower complexity.