Learning the algorithm

[TheCelticGuy]

Hi

I was wondering if you had useful links to learn and understand the FFT algorithm?

I only partially understand it so far. I've baked my H0k and H0minusk conjugate functions to get displacement of h(k,t).

But when i was reading the code to generate the butterfly texture, and the actual FFT algorithm the code is hard to understand, not sure what "blocks" are suppose to represent ( i assumed stages (log(n)/log(2)) but that didn't seem to make sense either, i also tried to figure out whats going on even when i wrote it out on paper following the numbers for N = 4 to see if i understood it but it was confusing.

I originally followed Keith Lantz article on it, he goes as far as showing the math proof of the symmetry but then just dumps the code with no explanation of whats going on - plus its hard to read since i don't really know C++ too well.

If you know any links that may help - would appreciate it as i am struggling to decode it from reading the files.

[Scrawk]

I cant help much with the FFT as I dont understand the math behind it myself. I just know how to code it and its been a long time since I have looked at it. I also have a port of the Keith Lantz code but in C# which you might find easier to read.

https://github.com/Scrawk/Phillips-Ocean

The number of passes is log(n)/log(2). I cant remember exactly what the number of blocks represents but it has to do with the way certain parts of the array need to be written to during each pass.