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

In reply to Re: Algorithms by Zaxo
in thread Algorithms by artist

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.