Talk:Split-radix FFT algorithm
I have found a slight improvement on the operation count in this article. There are three cases in which the expression ( wNk Zk + wN3k Z'k ) can be calculated with fewer than the usual 2 complex adds and 2 complex multiplies, or 8 real adds and 8 real multiplies. Two of them are mentioned in the article already.
The first case is the trivial k = 0, which eliminates 4 real adds and 8 real multiplies.
The second case is k = N / 8. The total recursive count of operations given in the article is based on counting each of the terms as 2 real multiplies, since the real and imaginary parts of wk are the same absolute value. The real multiplies can be done after multiplication by (1 + i) or (-1 + i). Thus it saves 4 real multiplies.
When I take, for N >= 4, a total of 2 N real multiplies, minus the 12 that have been saved so far, the recursive total including adds comes out to 4 N log2 N - 6 N + 8, as the article says.
However, the second case only requires 2 real multiplies, because they can be done after the two terms are added, rather than separately on each term. This makes a saving of 14 so far.
The third case is k = N / 16 or 3 N / 16. In the first case, wk = (s + c i) and w3k = (c + s i), where s and c are the sin and cos of pi / 16.