Very Computer

by kb » Fri, 23 May 2003 23:10:35

I read that gauss had invented fft algorithm.

Did this happen after fourier discovered fourier transform ?

Or did gauss discover "fourier theorem" but did not publish ?

( I find both were contemporaries. )

thanks
shankar

by **robert bristow-johnso** » Sat, 24 May 2003 00:12:56

Quote:> I read that gauss had invented fft algorithm.

i heard it was Cooley and Tukey.

J.W. Cooley and J.W. Tukey, "An algorithm for machine calculation of complex
Fourier series," Mathematical Computation, 19 (1965), 297-301.

http://eamusic.dartmouth.edu/~book/MATCpages/chap.3/chap3.pops/3.4.po...
tml

Quote:> Did this happen after fourier discovered fourier transform ?

Gauss observed that you could break up the calculation of the Discrete
Fourier Transform into two parts, making it more manageable. but taking
that idea far enough to the Radix-2 FFT to reduce the complexity to
O(n*log2(N)) was Cooley's and Tukey's idea.

Quote:> Or did gauss discover "fourier theorem" but did not publish ?

> ( I find both were contemporaries. )

i think that Gauss was on the committee that originally rejected Fourier's
discovery because it lacked proof. indeed Fourier did not show that the
Fourier Series actually did add up to the original periodic function (except
where there are discontinuities) but that *if* it did, the coefficients had
to be as Fourier suggested.

r b-j

by **Dilip V. Sarwat** » Sat, 24 May 2003 01:19:19

>Gauss observed that you could break up the calculation of the Discrete
>Fourier Transform into two parts, making it more manageable. but taking
>that idea far enough to the Radix-2 FFT to reduce the complexity to
>O(n*log2(N)) was Cooley's and Tukey's idea.

According to Cooley himself (Cooley, Lewis and Welch, "Historical
notes on the fast Fourier transform," IEEE Trans. Audio and
Electroacoustics, June 1967), Runge and Konig in 1924 had described
the radix-2 FFT, and this had been implemented by Danielson and
Lanczos in 1942. The Cooley-Tukey FFT algorithm was a generalized
version of the Runge-Konig idea in that it could also be used when
N was composite but not necessarily a power of 2.

--
.-. .-. .-. .-. .-. .-. .-.
/ D \ I / L \ I / P \ / S \ A / R \ W / A \ T / E \
`-' `-' `-' `-' `-' `-'

by **shanka** » Sat, 24 May 2003 01:21:30

How did gauss become interested in sampled-domain Fourier transform ?

Did he understand its relation to analog Fourier transform ?
--
Posted via http://web2news.com the faster web2news on the web
To contact in private, remove nno9spp4a+2mm

by **Jerry Avin** » Sat, 24 May 2003 01:40:30

> How did gauss become interested in sampled-domain Fourier transform ?

> Did he understand its relation to analog Fourier transform ?
> --
> Posted via http://web2news.com the faster web2news on the web
> To contact in private, remove nno9spp4a+2mm

That's a matter of practicality. We plot curves by measuring or
calculating an ordinate for each of several values of abscissa, laying
down the points and then connecting them by eye, with a French curve, a
limber batten, a spline, or what have you. If you want to express such a
curve as a series of sines and cosine pairs, you will certainly not try
to calculate an infinite number of them. Truncating the frequencies is
the same as making the "curve" a set of discrete points. But then, I
guess you knew that.

Jerry
--
Engineering is the art of making what you want from things you can get.

by **fourier** » Sat, 24 May 2003 04:28:19

>> How did gauss become interested in sampled-domain Fourier
>> transform ?

>> Did he understand its relation to analog Fourier transform ?
>That's a matter of practicality. We plot curves by measuring or
>calculating an ordinate for each of several values of abscissa, laying
>down the points and then connecting them by eye, with a French curve, a
>limber batten, a spline, or what have you. If you want to express such
a
>curve as a series of sines and cosine pairs, you will certainly not try
>to calculate an infinite number of them. Truncating the frequencies is
>the same as making the "curve" a set of discrete points. But then, I
>guess you knew that.
>Jerry

IIRC, the "curve" that Gauss was trying to "fit" was the orbit of
a planet. Hopefully someone else can name the planet and give more
detail.

fourierr at fastermail dot com
--
Posted via http://web2news.com the faster web2news on the web

by **santosh na** » Sat, 24 May 2003 05:18:28

> I read that gauss had invented fft algorithm.

> Did this happen after fourier discovered fourier transform ?

> Or did gauss discover "fourier theorem" but did not publish ?

> ( I find both were contemporaries. )

> thanks
> shankar

Most probably the name "FFT" is not coined by Gauss(1777-1855). His
works on orbit are concentrated arround 1801. He published the famous
number theory book "Disquisitioues Arithmeticae" in the same year. The
efficient interpolation on the orbits of asteroid(CERES!)on which FFT
is related is arround that time(Logically I think!). Fourier published
his work on heat propagation arround 1807 which is later known to his
name.

Hence Gauss's FFT may not be related to Fourier's work.!!

So I doubt any of your above speculations!!

Secondly, J.W.Cooley(Tukey!) in his "The re-discovery of the fast
fouier transform algorithm",1987,PP33-35 did not avoid Gauss's
original work. But Gauss's purpose was different from Tukey/Cooley.
Nobody denies that DSP lies in the 17-19th century rich mathematics.
We should not also deny classic intutive work by the two scientists
which revolutioned DSP in a bigger way.

Regards,
Santosh

by **Will Se** » Sat, 24 May 2003 05:41:35

> I read that gauss had invented fft algorithm.

> Did this happen after fourier discovered fourier transform ?

> Or did gauss discover "fourier theorem" but did not publish ?

> ( I find both were contemporaries. )

> thanks
> shankar

Cooley and Tukey introduced the FFT in the paper

Cooley, J. W. and Tukey, O. W. "An Algorithm for the Machine
Calculation of Complex Fourier Series." Math. Comput. 19, 297-301,
1965.

which is the most-cited paper of all time.

Later, someone noticed that Gauss, "Mr. Few-But-Ripe", had worked out
the same algorithm but did not publish it. Credit really belongs to
Cooley and Tukey because they launched the FFT revolution.

Fourier himself did not find the Fast Fourier Transform. Fourier
found Fourier series when he was studying the conduction of heat.
Fourier used to sit in his overheated room wrapped in layers of
clothing.

by **Herman Rub** » Sat, 24 May 2003 06:42:46

>> I read that gauss had invented fft algorithm.
>i heard it was Cooley and Tukey.
>J.W. Cooley and J.W. Tukey, "An algorithm for machine calculation of complex
>Fourier series," Mathematical Computation, 19 (1965), 297-301.
>http://eamusic.dartmouth.edu/~book/MATCpages/chap.3/chap3.pops/3.4.po...
>tml
>> Did this happen after fourier discovered fourier transform ?
>Gauss observed that you could break up the calculation of the Discrete
>Fourier Transform into two parts, making it more manageable. but taking
>that idea far enough to the Radix-2 FFT to reduce the complexity to
>O(n*log2(N)) was Cooley's and Tukey's idea.

Cooley and Tukey came up with this, not knowing what Gauss had
done. In fact, it was after many papers had been written using
more general decompositions than powers of 2 that the paper of
Gauss was found and attached to this.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Deptartment of Statistics, Purdue University

by **robert bristow-johnso** » Sat, 24 May 2003 12:15:05

>>> Gauss observed that you could break up the calculation of the Discrete
>>> Fourier Transform into two parts, making it more manageable. but taking
>>> that idea far enough to the Radix-2 FFT to reduce the complexity to
>>> O(n*log2(N)) was Cooley's and Tukey's idea.

>> According to Cooley himself (Cooley, Lewis and Welch, "Historical
>> notes on the fast Fourier transform," IEEE Trans. Audio and
>> Electroacoustics, June 1967), Runge and Konig in 1924 had described
>> the radix-2 FFT, and this had been implemented by Danielson and
>> Lanczos in 1942. The Cooley-Tukey FFT algorithm was a generalized
>> version of the Runge-Konig idea in that it could also be used when
>> N was composite but not necessarily a power of 2.

> Actually, you're all a little bit off.

well, coming from Mr. Fastest Friggin' FT in the West (wait until he hooks
up with Comrade Igor in the East at high noon), i will take this as
authoritative.

r b-j

by **Steven G. Johns** » Sat, 24 May 2003 15:28:53

> Most probably the name "FFT" is not coined by Gauss(1777-1855). His
> works on orbit are concentrated arround 1801.

(1805 is considered the likely date for his FFT work, in the
references I've seen.)

Quote:> He published the famous
> number theory book "Disquisitioues Arithmeticae" in the same year. The
> efficient interpolation on the orbits of asteroid(CERES!)on which FFT
> is related is arround that time(Logically I think!).

Are you sure it's Ceres?

In his notes, Gauss analyzes two examples. The first, a 12-point DFT
by radix-3 DIT, is of the declination vs. ascension angles of the
asteroid Pallas [1]. In the second example, he analyzes the path of
the asteroid Juno (what he calls "the new planet Juno:" "aequatio
centri pro novo planeta Iunone") via a radix-6 DIT decomposition of an
18-point DFT.

The only other data I can find in his FFT work ("Theoria
interpolationis methodo novo tractata") is on the sun and moon ("solis
et luna"), but he looks at this in the sections before developing the
FFT.

(My high-school Latin teacher would be so happy to read this
discussion...although Gauss' Latin is a bastardized form called
"neo-Latin.")

Cordially,
Steven G. Johnson

[1] "In commercio literario a clar. barone de Zach edito, vol. X p.
188 invenitur tabula, limitem borealem et australem zodiaci Palladis
exhibens." = "[In such-and-such reference] you find a table exhibiting
the northern and southern limits of the path [zodiac] of Pallas."
(This is followed by a 12-point excerpt from the table, which he
proceeds to analyze.)

by **Steven G. Johns** » Sat, 24 May 2003 15:33:48

> In the second example, he analyzes the path of
> the asteroid Juno (what he calls "the new planet Juno:" "aequatio
> centri pro novo planeta Iunone") via a radix-6 DIT decomposition of an
> 18-point DFT.

Correction: a radix-6 DIT decomposition of a 36-point DFT.

by **Steve Underwoo** » Sun, 25 May 2003 00:18:22

>>Gauss observed that you could break up the calculation of the Discrete
>>Fourier Transform into two parts, making it more manageable. but taking
>>that idea far enough to the Radix-2 FFT to reduce the complexity to
>>O(n*log2(N)) was Cooley's and Tukey's idea.

> According to Cooley himself (Cooley, Lewis and Welch, "Historical
> notes on the fast Fourier transform," IEEE Trans. Audio and
> Electroacoustics, June 1967), Runge and Konig in 1924 had described
> the radix-2 FFT, and this had been implemented by Danielson and
> Lanczos in 1942. The Cooley-Tukey FFT algorithm was a generalized
> version of the Runge-Konig idea in that it could also be used when
> N was composite but not necessarily a power of 2.

What exactly does "implemented" imply in this context? Was it some kind
electromechanical affair? A real Babbage style FFT box sounds kind of fun.

Regards,
Steve

by **Steven G. Johns** » Sun, 25 May 2003 03:30:32

Quote:> [1] "In commercio literario a clar. barone de Zach edito, vol. X p.
> 188 invenitur tabula, limitem borealem et australem zodiaci Palladis
> exhibens." = "[In such-and-such reference] you find a table exhibiting
> the northern and southern limits of the path [zodiac] of Pallas."
> (This is followed by a 12-point excerpt from the table, which he
> proceeds to analyze.)

Ahem, for the *retentive: "invenitur tabula" is "a table is
found," not "you find a table" ("invenis tabulam," if I remember
correctly). My Latin is a bit rusty. =)

Very Computer

FFT - gauss and fourier

FFT - gauss and fourier

FFT - gauss and fourier

FFT - gauss and fourier

FFT - gauss and fourier

FFT - gauss and fourier

FFT - gauss and fourier

FFT - gauss and fourier

FFT - gauss and fourier

FFT - gauss and fourier

FFT - gauss and fourier

FFT - gauss and fourier

FFT - gauss and fourier

FFT - gauss and fourier

FFT - gauss and fourier