Re: Algorithms

The classic example of an algorithm making a big difference is the discovery of the Fast Fourier Transform by Cooley and Tukey, in 1965.

Digital Fourier transforms decompose a regularly spaced array of data in terms of the associated frequency. They have properties which ease many kinds of data analysis problems. Before 1965, it was believed that dft was O(N**2), quadratic, in the size of the data set. That meant it was only useable for small data sets, and did not scale to larger problem well. Practical uses were few.

With the introduction of the FFT, that all changed. The use of a divide-and-conquer scheme reduced dft from quadratic to O(N*ln N), not much worse than linear. That produced a revolution in signal processing technology. Applications that had been dismissed as unworkable became possible, almost easy.

Besides use in software for data analysis of all kinds, hardware implementations were soon embedded in digital signal processing chips. There, the fft became the basis of digital audio and video products we all use. It is no coincidence that the CD audio sample rate of 44100 Hz is the product of small primes, 2**2 * 3**2 * 5**2 * 7**2. The FFT likes it that way.

CPAN has a number of modules providing FFT. I particularly like the one with PDL because of the handiness of piddles for other processing.

After Compline,
Zaxo

Comment on Re: Algorithms

Replies are listed 'Best First'.
Re: Re: Algorithms by theorbtwo (Prior) on Jun 24, 2003 at 06:14 UTC
In fact, I'd say that the FFT has done more to change society then any other general-purpose computer-based algorythim. FFT made the digital transfer and storage of near-photo-quality images practical, through it's use with JPEG, thus brining porn to the internet, creating huge social issues (see, for example, today's (well, now yesterday's, technicaly) US supreme court rulling), as well, in no small part, fulling the growth of the internet. Also, mp3s, with their own social problems and growth, MPEG and other compressed video, and in general most lossy compression algorithms. FFT has made taking real-life media into the digital world possible, and it's real-life media that creates much of the contriversy of the digital world, and contraversy moves both worlds forward. Warning: Unless otherwise stated, code is untested. Do not use without understanding. Code is posted in the hopes it is useful, but without warranty. All copyrights are relinquished into the public domain unless otherwise stated. I am not an angel. I am capable of error, and err on a fairly regular basis. If I made a mistake, please let me know (such as by replying to this node).	[reply]

Replies are listed 'Best First'.

Re: Re: Algorithms
by theorbtwo (Prior) on Jun 24, 2003 at 06:14 UTC

In fact, I'd say that the FFT has done more to change society then any other general-purpose computer-based algorythim. FFT made the digital transfer and storage of near-photo-quality images practical, through it's use with JPEG, thus brining porn to the internet, creating huge social issues (see, for example, today's (well, now yesterday's, technicaly) US supreme court rulling), as well, in no small part, fulling the growth of the internet. Also, mp3s, with their own social problems and growth, MPEG and other compressed video, and in general most lossy compression algorithms.

FFT has made taking real-life media into the digital world possible, and it's real-life media that creates much of the contriversy of the digital world, and contraversy moves both worlds forward.

Warning: Unless otherwise stated, code is untested. Do not use without understanding. Code is posted in the hopes it is useful, but without warranty. All copyrights are relinquished into the public domain unless otherwise stated. I am not an angel. I am capable of error, and err on a fairly regular basis. If I made a mistake, please let me know (such as by replying to this node).

[reply]