A pretty simple but fast FFT :-)

In this project there are 4 implementations of FFT's, 2 for C and 2 for Odin, 2 for f32 and 2 for f64. Those implementation are simple but they are fast for code that doesn't have explicitly SIMD instruction.
They are for both C and Odin :

1. Cool FFT f32 SOA ( Structure Of Arrays )
   This is the fastest implementation of FFT f32 that generate a table for reverse_bits.
   And that separates the real and imaginary parte of a Complex f32 number into two separate arrays, one ofr the reals and one for the imaginaries.
   That will allow for a faster prediction of acess patterns and for a faster prefetching of data from memory/caches.

2. Cool FFT f64 SOA ( Structure Of Arrays )
   This is the fastest implementation of FFT f64 that generate a table for reverse_bits.
   And that separates the real and imaginary parte of a Complex f64 number into two separate arrays, one ofr the reals and one for the imaginaries.
   That will allow for a faster prediction of acess patterns and for a faster prefetching of data from memory/caches.

I tested the f64 version on my AMD Ryzen Zen 3 G series computer and the cool_fft_f64_SOA, without SIMD instructions, is 4x slower then the best in class, hand crafted and highest tunned FFFTW - The Fastest FFT in the West. This using Clang 18.

C programs

cd cool_fft_f32_SOA
make f32_floats
make run_f32

cd cool_fft_f64_SOA
make f64_doubles
make run_f64

Odin programs

cd cool_fft_f32_SOA
make odin
make run_odin

cd cool_fft_f64_SOA
make odin
make run_odin

MIT Open Source license

Best regards,
Joao Carvalho