|
Audio Asylum Thread Printer Get a view of an entire thread on one page |
For Sale Ads |
In Reply to: tricks, discoveries and such... posted by gnat on May 16, 2000 at 23:40:20:
Hi gnat,>> Take for example FFT, Fast Fourier Transform. Can it be considered
>> as some "conceptual breakthough"? Hmm, basically it's nothing more
>> than a trick. Take a well-known DFT, Discrete FT formula and apply
>> some smart grouping of sum members, that's all. Not a discovery in >> some strict sence, maybe. But it made a whole class of algorithms
>> practically computable.I'm not very familiar with signal processing, but besides the details
the basis of DFT, I think, comes from approximation theory, real
analysis. I didn't say it very well in an earlier post, but I think
there's alot more enlightening than just "grouping of sum members":Anyone who is moderately mathematically sophisticated and who had
an intuition that approximating functions is simply "taking snapshots"
in an infinite-dimensional space, would have had formalized Fourier
Transforms. But only Fourier did. I trully think that mathematical
theories, espcially works by "geniuses", are not simply results of
tricks and hard works, but rather intuitions that normal people like
us don't have (until they point it out).Nothing wrong with tricks and hard works either. All being equal,
these differentiate the goods and the greats. But in my experience
of knowing and reading about mathematicians or theorists, these bright
people are very passionate about their discoveries, significant or
not. And they show that very explicitly. And more importantly
*intuitions* and big pictures are what it's all about, not how fast
you can calculate (remember that scene in which Will and the prof
show off their lightening computational skills?).Will Hunting was probably playing a cool genius. But from what I
know, read, and heard, he doesn't resemble anyone of them, not that
they are all the same. But then, he was also a troubled genius; but
then again, which one isn't.
Hi, caaDespite the algorithm title, Fourier is NOT an inventor of the FFT.
This algorithm was discovered later as a "fast-computing" modification
of the original DFT formula, hence "Fourier" in it's title.
regards, gnat
gnat,Yup, as you've pointed out, *tricks* do make life easier. And yes,
I wouldn't think Fourier would have cared if the computation is
O(n^2) or O(nlogn) as long as it's polynomially computable. But
I'm sure it's entirely different for programmers :)
.
Hi, caaI agree with you about DFT. I think it was a real "conceptual
breakthrough". Thing is, I was talking not about it. The whole
story is about the difference between D(iscrete) FT and F(ast)
FT. These transforms are analytically identical. Trust me,
I programmed both. ;-) The whole difference lies in number
of operations required to perform 'em. With DFT, you have it
proportional to square of samples number. It's really slow
@ big samples numbers. Then someone smart looked at th formula
and noticed ALOT of similar members in it, likeN*M1 + N*M2 + N*M3 + N*M4 + N*M5 + N*M6
Well, let's count operations... six multiplies and five additions.
Eleven. Now let's group it intoN*(M1 + M2 + M3 + M4 + M5 + M6)
One multiply and five additions. Six, almost half of it.
Actually, for FFT the number of operations is proportional to
N * log(N) for N samples. Again, trust me, it makes a WORLD
of difference when obtained @ N bigger than say, 1024!
Okay, sooo the big question is, whether this... let's say,
optimisation is a conceptual breakthrough? Hmm, you decide,
my own vote goes for a trick.
Another big question is the value of it. Well, it's really easy
to do now. Since there's literally thousands of applications and
publications using FFT and ALL of these applications would be
absolutely impossible (impractical) with DFT. Yeah, you would
get the same results with DFT - as I told, the algorithms are
analytically identical. But how long would it take to compute?
So today the answer is just plain wow. But this picture didn't
even exist for Cooley-Tukey. Ohhh, and just think about Gauss...
there was no electronics in his time AT ALL. Indeed I can easily
imagine even that Fourier realised a possibility of such an
optimisation. Not the whole deduction maybe, since it's quite
looong, but the direction. I can imagine how he thinks "so what,
it's just a relatively simple [ha! simple - to him of course,
NOT to me] tweak with NO particular value. Just don't worth
the efforts to proceed." Does that make Fourier a "cool genius"?
Sure no, though it may look like it - now and for us.Same can be with Will. He could be passionate about math things
that HE CONSIDERED as valuable. But these moments weren't shown
in the movie. It's not unrealistic. What we obtained could be
some kind of "routine" for him. Just no reason not to stay cool
about it. And the "discovery" itself... Just think about it,
the college students competition. Yeah, I'm aware of cases when
things like Ferma theorem were using in such competitions. ;-)
But welll... mostly it's not so. Something complex enough, but
of *reasonable* complexity. Not breakthroughs, something difficult
and important, but still reasonable. I have to see the movie once
more to refresh my memory whether it was so. Well, and if yes then
for a genius it could really look like some trick, a piece of
almost routine work.
Your thought about *troubled* genius makes alot of sence to me.
Will is young afterall. And while enjoying his math skills he
can feel that say, *sexual* (social) ones are more important.
Especially if show off of the latter seems harder to him. :)
regards, gnat
This post is made possible by the generous support of people like you and our sponsors: