search

liamappelbe / fftea

A simple and efficient FFT implementation for Dart
Apache License 2.0
63 stars 1 forks source link

Investigate supporting non-power-of-two FFT sizes #10

Closed liamappelbe closed 2 years ago

liamappelbe commented 2 years ago

How hard would this be? Is it worth the effort? Last time I implemented non-power-of-two sizes it was really complicated and had serious numerical precision issues. Maybe could do one of the factorization based algorithms with an O(n^2) fallback for prime sizes?

liamappelbe commented 2 years ago

For non-power of two sizes, use the generalized Cooley–Tukey algorithm, to recursively factorize the FFT (aka mixed-radix): https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm#Variations

For stages of this decomposition involving large prime factors, use Rader's algorithm to zero pad the FFT to a power of two: https://en.wikipedia.org/wiki/Rader%27s_FFT_algorithm

It's possible to do a mixed-radix bit reversal, but we can set that aside for a future optimization.