FFT - CT
The implementation uses recursion for space reasons - probably not so suitable for 10^6 modes+...
There are two slightly immoral things here: two rotations (one complex, one array, neither "suspicious") are included that are not existing libraries (but should be). Also, concat() is turned into c(). Again, more humane.
Note that exact output is a convention. E.g. Mathematica disagrees with Wikipedia; I give exactly that given by CT.