3 ms·
The Fast Fourier Transform (1965) is one very important algorithm that comes to mind, speeding up Fourier Transforms from O(N^2) to O(N log N). Quicksort (publi
by kens 6y ago
The Fast Fourier Transform (1965) is one very important algorithm that comes to mind, speeding up Fourier Transforms from O(N^2) to O(N log N). Quicksort (published 1961) might be another example, but since sorts in the 1950s usually ran on tape drives, it's hard to compare.
On the whole, computers of the 1950s were extremely memory-limited, so many modern algorithms aren't entirely relevant. For example, the IBM 7090 (1959) was a large-scale scientific computer and had an address space of 32K words. As for performance, it did 39,500 multiplications per second. A modern supercomputer is trillions of times faster; that makes up for a lot of bad algorithms.
Most modern problems are going to have a hard time fitting in a 1950s computer, regardless of the algorithm. On the whole, I think you'd be better off with 1950s algorithms on a modern computer than vice versa. On the other hand, modern cryptographic algorithms on old hardware would be infinitely better than old algorithms on modern hardware.
- rstuart4133 6y agoMerge sorts are typically used when sorting data on magnetic tapes. Polyphase merge was popular. All merge sorts are O(N log(N)). They were ideal for tapes as they read and write data sequentially.
- rsecora 6y agoThis is why I love HN. I was going to the shelving to check the cost in the Wirth book [1], and the right number was already published in HN. [1] Algorithms + Data Structures = Programs / Niklaus Wirth.
- joycian 6y agoI just want to add, because some people might find it interesting, that a version of the fast Fourier transform was already known to Gauss (though not published in his lifetime). More info can be found in the article "Gauss and the history of the fast Fourier transform" by T. Michael.
- rsecora 6y agoAs you point out, the sorting of arrays and sequential access files (tapes) have different algorithms. the cost of access to a tape record is not negligible and it is the main cost. But for arrays/memory it's almost 0, the weight of memory access. Niklaus Wirth describes this in the classic book "(Algorithms + Data Structures = Programs)". There is a full chapter comparing the best/normal/worst case for each approach. Those were "Elegant weapons for a more civilized Age.".