FAST FOURRIER TRANSFORM

[technology_forever]

hello guys,

im reading the paper titled : The input output complexity of sorting and related problem.
(you can find the paper at http://www.cs.duke.edu/~jsv/Papers/AgV88.IO.pdf)

I got stuck at the second page, the paragraph in titled : FAST FOURIER TRANSFORM

the paragraph says :

Fast Fourier Transform (FFT) Problem Instance: Let N be a power of 2. The internal memory is empty, and the N records reside at the beginning of the disk; that is, x = nil, for 1 5 i 5 M, and x[M + i] = Ri, for 1 5 i 5 N. Goal: The N output nodes of the FFT directed graph (digraph) are “pebbled” (to be explained below) and the memory configuration is exactly as in the original problem instance.

could anybody PLEASE PLEASE try to explain it to me !

[Ivy]

Here

[Ivy]

Thats what I was inspiring you to do more and more, Google, wiki etc etc are the keys to good Homework

[technology_forever]

hehe..thanks...but dont worry...i usually ABUSE google and stuff like that 

its just that this time..i got stuck on this part...plus, its not an assignment..its just a reading im doing..

thanks anyway    if anybody else is knowledgeable about this topic i posted...PLEASE help me out..thanks

[Ivy]

So you want someone to explain thsi to you in easy words.....umm hire a tutor

best of luck!

[Ivy]

With all due respect I know that, but ummm I'm just a lil bored you know, why else would I ask you to google!! Gosh I don't do this!! wonder what Dias has to say about this


besides you deleted those posts you made in between after my first reply, you need to understand we are helping here for free and you need to fix your attitude and know how to ask for help in the first place, instead of just deleting your posts later on.

[Dias de verano]

This is a general computer help and fix advice forum. It is not a university level comp sci site. That is what Dias has to say. I agree with Ivy, in general, but I must say, Ivy, dear, that you should earn the "right to be rude" by having a solid history of giving real help and not just "try Google" and "be patient, somebody might know the answer" type posts.

[Ivy]

I have only done that once, i told him to be patient because he was my friend from the chat room and he was really worried!!!!! I never told anyone to google before!!

Dias check all my posts!!

Gosh you won't change no matter what I do!!!!!

p.s. you mean you have a right to be rude!!

[Dias de verano]

Gosh you won't change no matter what I do!!!!!

Of course not. What did you expect?

p.s. you mean you have a right to be rude!!

I have a right to do anything I want. I am DIAS. Look upon my works, ye mighty, and despair!