Is there a way to further optimise my FFT? I've written my own FFT but wanted to know if there was perhaps a way to combine the Cooley and Turkey methods. So far I've got N/2 log N real multiplies for transforming a real signal.

My current implementation has N log N multiplies (well a little more because I've not optimised out the case of the complex sinusoid at 0 radians), but I have an optimisation that reduces the number of multiplies by 50%.

Note: this is absolutely not homework, I've written this algorithm because I found the explanations of the Cooley/Turkey method far too convoluted, and at the same time I wanted the ability to select which bins I processed in both the FFT and IFFT as well as being able to output the IFFT to multiple channels. So I just decided to figure out my own radix-2 while at the same time understanding how and why the transform works (which I have).

ORIGINAL QUESTION (edited for clarity) ---

Example code: kfft.c

I wanted to know whether there is a similar FFT algorithm to mine.

I basically perform FFT by factorising calculations by recursively subtracting the second half of a signal from the first, meaning x[n] only needs to be multiplied by the complex sinusoid for only half of the duration, resulting in N/2 log N real multiplies (shown below). The summed signal is for multiplying with complex sinusoids that are multiples of the sampling period. For example groups {2, 6} are multiples of 2, and therefore have a periodicity of 4 samples.

// For bins { 1, 3, 5 and 7 }

x1[0] = x0[0] - x0[4]
x1[1] = x0[1] - x0[5]
x1[2] = x0[2] - x0[6]
x1[3] = x0[3] - x0[7]
// Calculate sum (required for the next level of bins)
x0[0] = x0[0] + x0[4]
x0[1] = x0[1] + x0[5]
x0[2] = x0[2] + x0[6]
x0[3] = x0[3] + x0[7]

// For bins { 2 and 6 }

x2[0] = x0[0] - x0[2]
x2[1] = x0[1] - x0[3]
// Calculate sum (required for the next level of bins)
x0[2] = x0[0] + x0[2]
x0[3] = x0[1] + x0[3]

// For bin { 4 }
x3[0] = x0[0] - x0[1]
x3[1] = x0[0] + x0[1] // &lt;-- This is the 0hz bin (sum)
Indeed, this is more or less the usual butterfly used in radix-2 FFT (can be extended to any prime number): http://en.wikipedia.org/wiki/Butterfly_diagram