Missing const
I see you sprinkled const
almost everywhere. However, you actually missed the one spot where it actually matters most: input
should be a const
pointer:
_Bool fft(const complex_t* input, complex_t* output, const unsigned int size) {
...
}
Use the restrict
keyword if possible
Since input
and output
are of the same type, they can alias. This might prevent the compiler from generating optimal code, as it now must assume that any write to a value of output
might change a value in input
. Annotate these pointers with the restrict
keyword if supported by your compiler.
Note that making input
a const
pointer doesn't prevent aliasing.
Avoid divisions
Divisions are one of the slowest operations on any CPU, but especially on low end CPUs they might take tens of times more cycles than a multiply. You can avoid the division when calculating angle
by writing:
double angle = -M_PI;
for (unsigned int even_to_odd = 2; even_to_odd < size; even_to_odd *= 2) {
angle *= 0.5;
...
}
However, note that the compiler can easily optimize divisions by constants, so there is no need to worry about expressions like skip /= 2
.
But perhaps even better:
Consider using sin/cos look-up tables
cos()
and sin()
are transcedental functions that can take a long time to evaluate, especially on weak microcontrollers. On the other hand, microcontrollers usually have very low memory access latencies. So it might make sense to pre-calculate all the possible values of sin(angle)
and cos(angle)
that you might encounter, and store them in a look-up table.