Talk:Split-radix FFT algorithm

I have edited this post to correct some miscalculations. I thought I had improved on the total operation count, but I had miscounted.

Michael Rolle (talk) 07:10, 29 December 2008 (UTC)

I worked out the counts of adds and multiplies separately. I use 4 real multiplies and 2 real adds for a complex multiply. The results are:

I will give the new operation count formula, with adds and multiplies separately. This is of interest for implementations on devices, such as the Intel Core and the AMD Barcelona, which have equal add and multiply bandwidth.

Real adds = 8/3 N log2 N - 22/9 N + 14/9 (-1)^{log2 N} + 2.

Real multiplies = 4/3 N log2 N - 32/9 N - 14/9 (-1)^{log2 N} + 6.

Real total ops = 4 N log2 N - 6 N + 8. (Corrected this line on 3/20/09)

Yavne's original paper, as cited in Johnson's tangent FFT paper, gives different formulas for adds and multiplies: more adds, fewer multiplies, same total count. The counts I have here are 12% fewer in the adds, which will be the dominant element on Core, Barcelona, et al.

By the way, the article lists (-1 + i) and (-1 - i) as the twiddles for k = N / 8. I believe these should be +1 instead of -1. Michael Rolle (talk) 05:56, 28 December 2008 (UTC)

The count given in the article is in agreement with the published references, so if you can further improve the count (other than by the techniques recently published in 2007) it would be original research and you would need to publish it elsewhere before putting it in Wikipedia.

However, at first glance I don't think your analysis is correct. First, the N/8 case is well known and its exploitation is already included in the published count. Second, the N/16 technique you are using doesn't work because it destroys a common subexpression: you also need to compute (s + c i) Z_k - (c + s i) Z'_k = s (Z_k - i Z'_k) - c(Z'_k - i Z_k ), and with your factorization you can't re-use the multiplications between the two cases. So you still end up with the same number (8) of total multiplications for the butterfly.

(There are ways to trade off one multiply for one addition in each twiddle multiplication, but these are well known too and don't change the total operation count, nor do they seem to be beneficial on current hardware.)

(Getting the count right is notoriously difficult; there have been several published incorrect claims of improvements in the operation count that were later refuted as simple miscountings.)

If you like to play with these things, I should also mention that there is a variant, the conjugate-pair split-radix algorithm, that has twiddle factors w^k and w^-k instead of w^k and w^3k, which makes the sharing of sine/cosine factors between the two twiddles more obvious (and therefore makes it easier to save some operations by refactoring). This is actually the basis for the improved algorithms published in 2007, which work by pulling out a sine or cosine factor to get 1±itan twiddle factors and similar, and with various rearrangements and refactorizations this eventually leads to some saved multiplications.

You're right that the twiddle factor for N/8 was multiplied by -i; this should now be fixed.

—Steven G. Johnson (talk) 15:43, 28 December 2008 (UTC)

(Okay, now that Michael has corrected his original remarks, my response doesn't make sense anymore. Michael, in Talk pages it's better to preserve continuity by adding new comments rather than going back and drastically revising your remarks in response to comments, so that other people can follow the discussion.)

Regarding the difference in your separate add and multiply counts compared to the published counts, I haven't looked at them in detail but probably there is a simple explanation. The obvious way to do a complex multiplication requires 4 real multiplications and 2 real additions. However, many of the older papers on split-radix algorithms use a trick to multiply by a root of unity in 3 real multiplications and 3 real additions. This trades off multiplications for additions, without changing the total operation count of course. And there are probably other ways to get slight tradeoffs of this sort. See, for example:

H. V. Sorensen, M. T. Heideman, and C. S. Burrus, "On computing the split-radix FFT", IEEE Trans. Acoust. Speech Sig. Proc. 34 (1), 152-156 (1986).

—Steven G. Johnson (talk) 15:41, 30 December 2008 (UTC)

Corrected formulae (again)

Real adds = 8/3 N log2 N - 16/9 N - 2/9 (-1)^{log2 N} + 2.

Real multiplies = 4/3 N log2 N - 38/9 N + 2/9 (-1)^{log2 N} + 6.

Real total ops = 4 N log2 N - 6 N + 8.

The recursions are:

adds4N = 2 addsN + adds2N + 16 N - 4

muls4N = 2 mulsN + muls2N + 8 N - 12

Michael Rolle (talk) 07:37, 21 March 2009 (UTC)

"Corrected" from what? This doesn't contradict anything in the article. These are just the well-known counts for the case when complex multiplies are done as 4 multiplications and 2 additions. The problem with reporting the add and multiply counts separately, though, is that you can trade off some multiplications for additions if you want by using the 3/3 multiply trick, so you have to be careful to precisely define how you are implementing the algorithm. This ambiguity is avoided by simply reporting the total, which is invariant. (See also http://cnx.org/content/m12031/latest/, which quotes the counts, and the paper by Sorensen et al that gives the 4/2 counts and recurrence relations.) Historically, the 3/3-complex-multiply counts (~N lg N multiplies and ~3 N lg N adds) are more important, as split-radix was developed at a time when people thought that minimizing the multiplication count was the most important thing...most authors in the 1980s quoted the 3/3 multiply counts. —Steven G. Johnson (talk) 17:06, 21 March 2009 (UTC)

Steven, I only just now noticed your latest comments, as of March.

"Corrected" means a correction of my previously posted formulae, not a reference to the actual article itself.

Yes, my formulae apply to the 4/2 method, rather than the 3/3 method. I guess I should have made that explicit.

24.130.128.254 (talk) 09:00, 26 August 2009 (UTC)

Discrepancy in the text

"The split-radix algorithm can only be applied when N is a multiple of 4" "These considerations result in a count: 4Nlog2N − 6N + 8 real additions and multiplications, for N a power of two greater than 1."

So can the split-radix algorithm formally be applied when N is 2, or only when N is 4 (or larger powers of 4)? — Preceding unsigned comment added by Knutinh (talk • contribs) 15:05, 4 October 2011 (UTC)

For N an odd power of 2, the leftover factor of two must be handled by a radix-2 step (or just done directly, since a DFT of size 2 by the naive definition requires 2 adds and 2 mults, the same as a radix-2 FFT). That is assumed in the 4Nlog2N − 6N + 8 count (which works fine for 2^1, but not for 2^0). — Steven G. Johnson (talk) 15:22, 4 October 2011 (UTC)

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Split-radix FFT algorithm. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

• Added archive https://web.archive.org/web/20061130110013/http://home.comcast.net:80/~kmbtib/ to http://home.comcast.net/~kmbtib/

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
• If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 06:56, 30 December 2016 (UTC)