fix_fftr algorithm does not produce correct output

[michaelkrzyzaniak]

This code has been floating around for a very long time. Since there seems to be some interest amongst Arduino users, I want to pont out that the fix_fftr algorithm has always been incorrect. The reasons are as follows:

1. It does not produce correct or sensible output when compared to other fft libraries or compared to expectations.

2. Calling it does not produce equivalent output to calling fix_fft() with imaginary part set to all zeros (which does produce correct output).

3. The code does not do what the comment says it does. Firstly, the code from line 201 to 205 does not produce correctly de-interleaved data as the comment describes, and secondly because line 207 passes real and imaginary parts in opposite order than what the comment describes.

4. Neither the comment nor the code follow a valid approach. There does exist an approach that starts by de-interleaving even and odd samples, and using an N/2 point DFT as is described in the comment. However, this approach requires an additional post-processing step called a "split" operation as described in https://www.ti.com/lit/ml/spra291/spra291.pdf?ts=1679740480149. This approach requires twice as much memory as is used by fix_fftr, and produces two-sided complex output (2^m real and 2^m imaginary samples output). The input data would have to be properly de-interleaved for this to work, which would normally be implemented using 2x memory as well.

There exists another approach that does not require de-interleaving or extra memory. It is described in https://sci-hub.st/10.1109/tassp.1987.1165220. However, it does not use the normal complex dft algorithm, and could not be implemented with a call to fix_fft() plus extra steps.

I think the original authors of this code were confused when they wrote the fix_fftr algorithm.

I would honestly recommend removing the entire function as it is a trap for young players, or replacing it with the second approach described above which is not too difficult to implement.