20120301, 17:45  #56 
Feb 2012
Athens, Greece
57_{8} Posts 
Well I also want to read more about FFT. It helps to keep in mind that Fast Fourier Transform is simply an optimization for the real thing: the Discrete Fourier Transform (DFT). If it's difficult to find material in English, imagine how difficult it is to find good material in Greek!
Last fiddled with by emily on 20120301 at 17:47 
20120301, 18:05  #57 
Tribal Bullet
Oct 2004
DE3_{16} Posts 
Lately I've found this free book a fascinating read on FFTs, since I've become interested in numbertheoretic transforms and so need to reapply all of the theory it describes but in domains without complex numbers. The web site has other works by Burrus as well, that complement topics that the book glosses over a little.
It's really surprising how difficult it is to get the original papers mentioned in the bibliography. Most are from the 1980s, only Burrus' notes are more recent that I could find. Either you find a copy of Nussbaumer's book in a university library or you pay the IEEE $10 a page for a PDF. At that rate my collection of hobby papers and books would have cost me $100,000. 
20141203, 23:27  #58 
Jun 2014
120_{10} Posts 
Is the carry step like with the GS method? So say if you had (48,52,52,52), would you then get the result 52+520+5200+48000=53772? If not, how else would you do it?
Last fiddled with by legendarymudkip on 20141203 at 23:28 
20141206, 03:15  #59  
∂^{2}ω=0
Sep 2002
República de California
5×2,351 Posts 
Quote:
0: 52, /= 5 (carry), %= 2; 1: 5+52, /= 5 (carry), %= 7; 2: 5+52, /= 5 (carry), %= 7; 3: 5+48, /= 5 (carry), %= 3; 4: 5+0, no carry, hence done. Now *really* in practice we would use a modulo based on nearestint rounding of the DIV result, yielding a balanceddigit representation of the result, 53772, which has much better numerical properties as far as the next FFTsquaring (assuming one occurs) is concerned. Same as above, but everytime the %= result is > 5 (i.e. half the base) we subtract 10 from the current digit and increment the carry by 1 to account for the 10: 0: 52, /= 5 (carry), %= 2; 1: 5+52, /= 6 (carry), %= 3; 2: 6+52, /= 6 (carry), %= 2; 3: 6+48, /= 5 (carry), %= 4; 4: 5+0, no carry, hence done. Check the result: 2 + 10*( 3 + 10*( 2 + 10*( 4 + 10*(5)))) = 53772, as expected. In the case where the "coin lands on its edge" (%= 5 in base10) you can either use an IEEEcompliant roundtonearesteven (if your hardware can do that efficiently), or just take whichever direction your preferred NINT emulation (e.g. NINT(x) = (x + c)  c, where the "magic constant" c = 0.75*2^b and b = #bits of the mantissa in your floating point type)  which of the 2 is not crucial, in my experience with these types of computations. 

20160406, 14:44  #60 
"Cade Brown"
Feb 2016
USA
27_{8} Posts 
How exactly does the FFT reduce to order NlogN ? It seems as though you are still doing a NxN matrix multiplied by a scalar, which seems to be at least N^2 Is there something most programs do to cut it down?

20160407, 04:04  #61  
∂^{2}ω=0
Sep 2002
República de California
5·2,351 Posts 
Quote:
out0 = (a+c) + (b+d) out1 = (ac)+i*(bd) out2 = (a+c)  (b+d) out3 = (ac)i*(bd) So instead of a naive matrix multiply, we first compute the following intermediates  these are the famous radix2 "butterflies": y0 = (a+c) y1 = (ac) y2 = (b+d) y3 = (bd) , which we can do inplace, overwriting the original inputs. (Though there are intricacies such as bitreversal reordering and schemes for avoiding the need for it involved in the deployment of an inplace FFT scheme.) Then combine these to obtain the outputs: out0 = y0 + y2 out1 = y1+i*y3 out2 = y0  y2 out3 = y1i*y3 . Thus radix4 needs 2 passes through the data, each pass doing just linear work, i.e. O(n). For length n = 2^k we need k = lg(n) (lg = base2 logarithm) such passes, each of O(n) cost, hence O(n log n) overall. For n not a power of 2 things are bit more involved, but one can still prove the O(n log n) property, just with a higher implied constant of proportionality. The procedure can be done recursively  it is perhaps most naturally explained that way  or not. Any decent FFT reference has more details, though I found such small worked examples very useful way back when I was first learning this stuff, and especially working out the mechanics of nonpowerof2length FFTs, which relatively few references cover in any useful fashion. 

20190405, 16:39  #62 
"Marv"
May 2009
near the Tannhäuser Gate
804_{10} Posts 
Youtube FFT by hand !
FWIW, here is a Youtube video I found posted Autumn 2018 in which a guy multiplies 41 * 37 by hand with paper and pencil using FFT!
How cooly retro. It's 7 minutes long and has just the basics. Enjoy: https://www.youtube.com/watch?v=YDhsLhTK3Bs Last fiddled with by tServo on 20190405 at 17:00 
20230104, 22:50  #63 
"Ben Bradley"
Sep 2008
Atlanta
6_{10} Posts 
I could write up something describing how to do the transform done by the machine in this link  it doesn't use complex numbers, because it doesn't do a full Fourier Transform. What it does is called a discrete cosine transform. If you also do a discrete sine transform and combine the results as complex numbers, you've got the whole discrete fourier transform. The absolute values of these complex numbers are the amplitudes in each frequency bin, and the phases are of course the phase in each bin.
I see the Fast Fourier Transform as a separate entity, It's essentially a mathematical trick to calculate the DFT with fewer calculations (something like N log N instead of N^2). I do NOT quite understand how the FFT works despite having written FFT code, following the butterfly diagrams and such. One thing common with the FFT is the precalculated "twiddle factors." These values are repeatedly calculated (though perhaps not obviously so) as part of calculating the DFT. You can get the guy's PDF book from this page and see the videos  the first video just goes over the book, the next four show the operation of the machine: https://engineerguy.com/fourier/ 
20230105, 02:25  #64  
If I May
"Chris Halsall"
Sep 2002
Barbados
11092_{10} Posts 
Quote:
Wavelet encoding will be left for a later class... 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Any technology you guys are excited about?  jasong  Lounge  31  20151009 20:55 
These dell guys can't possibly be serious...  Unregistered  Hardware  12  20061103 03:53 
You guys are famous  jasong  Sierpinski/Riesel Base 5  1  20060322 01:06 
Hi guys !  Crystallize  Lounge  6  20030927 13:08 
How do you guys do this?  ThomRuley  Lone Mersenne Hunters  1  20030529 18:17 