FAO Louster or any other brilliant maths person

[TdC]

could you spare a minute and explain what a Fast Fourier Transform is in extremely simple language? I've not had much sleep and so the wiki page means nothing to me

cheers in advance

 

[Trem]

It basically means that Dutch people like willy.

Hope this helps.

 

[TdC]

only if said willy is a member of certain groups, and it doesn't matter if it's a prime willy or not

 

[Louster]

Sorry, they only start on Fourier stuff this year. What's the context, out of curiosity?

 

[Paradroid]

http://en.wikipedia.org/wiki/Discrete_Fourier_transform

In mathematics, the discrete Fourier transform (DFT), sometimes called the finite Fourier transform, is a Fourier transform widely employed in signal processing and related fields to analyze the frequencies contained in a sampled signal, to solve partial differential equations, and to perform other operations such as convolutions. The DFT can be computed efficiently in practice using a fast Fourier transform (FFT) algorithm.

I couldn't really be arsed with Fourier transforms myself, just knew enough to get by, and that was 15 years ago...back then calculators could do fourier series stuff, a contact lense should be able to do the same today.

 

[leggy]

The fundamental principle is that any complex waveform can be said to be constructed of a series of sin() or cos() functions; the only difference between the two functions is phase.

Fourier transforms allow you to analyse and single out these individual sin/cos functions.

This is all I remember really. Discrete fourier transforms can pick out individual functions and I'm assuming fast fourier transforms are just a more effiecient method of doing that same job.

Maybe I'm off the mark a bit though.

Oh and they convert a waveform from the time domain to the frequency domain.

 

[Trem]

A little bit of my love for you died after reading that post Leggy

If I want Stephen Hawkings I will go and wheel him off his feet.

I want someone who is dumb and believes that my peen is a surpository

 

[leggy]

I Believe!!!!!

 

[TdC]

I never pegged you as a Hawkings affectionado Trem


the context was that I am mucking about with overclocking an athlon 57 fx, and run stress tests to determin the stability of the system. one of the tests is a program called prime95 from the people at mersenne.org (who search for new prime numbers)

prime95 contains an option called "torture test" where a Lucas-Lehmer test is performed together with a Fast Fourier Transform.

The Lucas-Lehmer primality test is remarkably simple. It states that for P > 2, 2P-1 is prime if and only if Sp-2 is zero in this sequence: S0 = 4, SN = (SN-12 - 2) mod (2P-1). For example, to prove 27 - 1 is prime:

S0 = 4
S1 = (4 * 4 - 2) mod 127 = 14
S2 = (14 * 14 - 2) mod 127 = 67
S3 = (67 * 67 - 2) mod 127 = 42
S4 = (42 * 42 - 2) mod 127 = 111
S5 = (111 * 111 - 2) mod 127 = 0

To implement the Lucas-Lehmer test efficiently, one must find the fastest way to square huge numbers modulo 2P-1. Since the late 1960's the fastest algorithm for squaring large numbers is to split the large number into pieces forming a large array, then perform a Fast Fourier Transform (FFT), a squaring, and an Inverse Fast Fourier Transform (IFFT). See the "How Fast Can We Multiply?" section in Knuth's Art of Computer Programming vol. 2. In a January, 1994 Mathematics of Computation article by Richard Crandall and Barry Fagin titled "Discrete Weighted Transforms and Large-Integer Arithmetic", the concept of using an irrational base FFT was introduced. This improvement more than doubled the speed of the squaring by allowing us to use a smaller FFT and it performs the mod 2P-1 step for free.

Aparantly they use FFTs and IFFTs to help work large number equasions. As I have no idea how to play with large numbers, let alone small ones, I was wondering what an FFT was.

 

[Trem]

I never pegged you as a Hawkings affectionado Trem

Oh he would get it hard tbh.

 

[TdC]

genius jizz! you could sell it!

 

[Ch3tan]

I am already selling my jizz as an elixir of eternal life. Niche market and I got there first. I do not welcome unwanted competition.

/sends Throd round with a shotty.

 

[TdC]

but ours is gargled. it's a completely different process

 

[Ch3tan]

*Produces patents on the gargling process filed looong before teeds thought of it*

 

[caLLous]

You're joking aren't you? TdC practically invented gargling cum.

 

[TdC]

see? my gargleor has spoken!

 

[Ch3tan]

You may have invented it, but your lazy with those patent applications.

I aer profiting from your cum gargling skills!