mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2012-03-01, 17:45   #56
emily
 
Feb 2012
Athens, Greece

2F16 Posts
Default

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 2012-03-01 at 17:47
emily is offline   Reply With Quote
Old 2012-03-01, 18:05   #57
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

32×5×79 Posts
Default

Lately I've found this free book a fascinating read on FFTs, since I've become interested in number-theoretic transforms and so need to re-apply 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.
jasonp is online now   Reply With Quote
Old 2014-12-03, 23:27   #58
legendarymudkip
 
legendarymudkip's Avatar
 
Jun 2014

23×3×5 Posts
Default

Quote:
Originally Posted by ewmayer View Post
Since all the output digits happen to be less than 10 and nonnegative, we don't need to do any carry step
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 2014-12-03 at 23:28
legendarymudkip is offline   Reply With Quote
Old 2014-12-06, 03:15   #59
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

1175510 Posts
Default

Quote:
Originally Posted by legendarymudkip View Post
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?
Assuming digit significance (power of 10) decreases from left to right, yes. But in practice we would start with the 0-index output term, the rightmost 52 in your notation, and work our way upward (leftward) like so, with the left-column index indicating power of 10, and /= denoting integer (truncating) divde and %= indicating (nonnegative-output) modulo:

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 nearest-int rounding of the DIV result, yielding a balanced-digit representation of the result, 53772, which has much better numerical properties as far as the next FFT-squaring (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 base-10) you can either use an IEEE-compliant round-to-nearest-even (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.
ewmayer is offline   Reply With Quote
Old 2016-04-06, 14:44   #60
CadeBrown
 
CadeBrown's Avatar
 
"Cade Brown"
Feb 2016
USA

101112 Posts
Default

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?
CadeBrown is offline   Reply With Quote
Old 2016-04-07, 04:04   #61
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

101101111010112 Posts
Default

Quote:
Originally Posted by CadeBrown View Post
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?
The core aspect of the FFT is that no matrix multiplies are done ... consider the length-4 vector Fourier transform example I give in post #5, in matrix-multiply form. See the obvious redundant operations? Adding a few () and a few rearrangements of the inputs to make things more obvious, our 4 DFT outputs are

out0 = (a+c) + (b+d)
out1 = (a-c)+i*(b-d)
out2 = (a+c) - (b+d)
out3 = (a-c)-i*(b-d)

So instead of a naive matrix multiply, we first compute the following intermediates - these are the famous radix-2 "butterflies":

y0 = (a+c)
y1 = (a-c)
y2 = (b+d)
y3 = (b-d) ,

which we can do in-place, overwriting the original inputs. (Though there are intricacies such as bit-reversal reordering and schemes for avoiding the need for it involved in the deployment of an in-place FFT scheme.)

Then combine these to obtain the outputs:

out0 = y0 + y2
out1 = y1+i*y3
out2 = y0 - y2
out3 = y1-i*y3 .

Thus radix-4 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 = base-2 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 non-power-of-2-length FFTs, which relatively few references cover in any useful fashion.
ewmayer is offline   Reply With Quote
Old 2019-04-05, 16:39   #62
tServo
 
tServo's Avatar
 
"Marv"
May 2009
near the Tannhäuser Gate

22·3·67 Posts
Default 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 cool-y 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 2019-04-05 at 17:00
tServo is offline   Reply With Quote
Old 2023-01-04, 22:50   #63
benbradley
 
"Ben Bradley"
Sep 2008
Atlanta

610 Posts
Default

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/
benbradley is offline   Reply With Quote
Old 2023-01-05, 02:25   #64
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

22·47·59 Posts
Default

Quote:
Originally Posted by benbradley View Post
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.
That would be welcomed. Remember that DCT is rather important for JPEG and even early MPEG.

Wavelet encoding will be left for a later class...
chalsall is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Any technology you guys are excited about? jasong Lounge 31 2015-10-09 20:55
These dell guys can't possibly be serious... Unregistered Hardware 12 2006-11-03 03:53
You guys are famous jasong Sierpinski/Riesel Base 5 1 2006-03-22 01:06
Hi guys ! Crystallize Lounge 6 2003-09-27 13:08
How do you guys do this? ThomRuley Lone Mersenne Hunters 1 2003-05-29 18:17

All times are UTC. The time now is 14:16.


Wed Feb 8 14:16:05 UTC 2023 up 174 days, 11:44, 1 user, load averages: 0.81, 0.79, 0.79

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔