3 ms·
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
by dbaupp 10y ago
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?
- 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.