The Art of Computer Programming, volumes 1–3, was written in the late 1960s, with vol 3 finalized in Sept 1972 after a delay of “almost 3 years” because of rapid development of the subject matter.

I recall a statement (though I can’t find the actual page) where Knuth says 10! (About 3.6 million) separates the size of a problem that can be solved by brute force from those where such is impractical.

Now from Moore's Law, doubling every 18 months, I would estimate a modern computer would be faster by a factor of a billion. But, that seems to be an overestimate based on my benchmarks and surmising that it would have taken Knuth a matter of days to run.

Now Moore's law applies to equal cost, so comparing a major industrial machine against a desktop PC brings them closer together. Moore’s Law might not have started yet. Scale factors might be more complex— e.g. was I wasting power because I could have been manipulating 64-bit quantities and the problem only used 8?

So I wonder, just what were the performance characteristics of the kind of machine Knuth was familiar with at Princeton in the mid to late 1960s?

  • 9
    Moore's Law doesn't predict computer performance, it predicts transistor counts in integrated circuits doubling every two years. For the last 10 to 15 years computer performance hasn't come anywhere close to doubling every 18 months. – Ross Ridge Aug 16 '17 at 15:11
  • Single-threaded uniprocessor performance hasn't been doubling every 2 years, but that methodology is obsolete for current brute-force problem solving. – hotpaw2 Aug 16 '17 at 19:19
  • 2
    @hotpaw2 ...for problems that can be parallelized. While admittedly many do, not all problems lend themselves well or even at all to parallelizable solutions. Anything involving numerical integration, for example, (or anything where the output from one step forms the input to the next, more precise, step) probably doesn't parallelize too well. Anything where one attempt can be made independent of any other attempt certainly does parallelize very well; the extreme case of that being something like brute force exhaustive key search on symmetric encryption algorithms. – a CVn Aug 16 '17 at 19:32
  • Granted. For bit-serial problems without parallel brute force (or QM) solutions, the advantage today is probably below 1e6. For problems with parallel solutions at a cost of, say 1 year of a Stanford professor's salary at the time, the delta today is likely well over 1e9, possibly near 1e12. – hotpaw2 Aug 16 '17 at 19:49

In the mid-1960's, an IBM 360/6x mainframe cost a few million (in USD at that time, adjusted for inflation it would be more) and could do on the order of a megaflop, maybe half that. Today, a Raspberry Pi Zero W cost about $10, and can easily do over a gigaflop, maybe two. But the price/performance of brute force numerical stuff on a contemporary GPU might be even better (near 100 teraflops for under a $1000). For some types of computational problems, one can rent multiples of brute-force crunching capability from the "cloud", and not even incur sunk hardware costs.

Added: This wikipedia page suggests that Princeton had an IBM 360/67 in the 1960's:

  • Nitpick: contemporary GPUs are closer to the 10 teraflop range (in single precision) in the under-$1000 price point. This number is always increasing, though; the upcoming Volta architecture from NVIDIA has some specific functional units that juice this up closer to 100 teraflops for some half-precision operations, targeted at deep learning. – Jason R Aug 18 '17 at 11:28
  • Thanks! I did some more figuring based on S/360. Indeed, a billion in terms of processing power per dollar. About a million in computing with these different classes of machine. – JDługosz Aug 18 '17 at 18:54

The comment you mention occurs in The Art of Computer Programming, Volume 1 (Fundamental Algorithms), Chapter 1 (Basic Concepts), Section 1.2 (Mathematical Preliminaries), Subsection 1.2.5 (Permutations and Factorials):

TAOCP Vol 1 p. 47

The calculation says that if checking each case takes about a millisecond, then 10! is about the number of cases you can check in an hour: this calculation is as true today as it was in 1968 (when Vol 1 was first published). What has changed is that today you can check a lot more in a millisecond than you could then: you can solve more difficult problems.

We actually know a fair bit about the kind of computers Knuth cut his teeth on:

  • As an undergraduate student at Case Institute of Technology, he worked on the “type 650 computer”, to which he dedicated the TAOCP series of books. He has spoken about how enlightened the computer administrators at the college were for allowing undergraduates to use the machine. There he co-wrote a compiler called RUNCIBLE (which led in 1959 to his second ever publication, after the one in MAD Magazine) (watch him talk about it starting here). According to this IBM page, the speed of this machine was as follows:

    Approximate calculating speeds (optimally programmed)
    78,000 additions or subtractions per minute
    5,000 multiplications per minute (multiplier = 5,555,555,555)
    3,700 divisions per minute (divisor = 5,555,555,555)
    138,000 logical decisions per minute

  • On the strength of this compiler experience, he got a job as a consultant at Burroughs (while still a student) to write an Algol compiler for the Burroughs 205 (read Richard Waychoff's account of it in the “III. The Summer Of 1960 (Time Spent with don knuth)” part of “Stories about the B5000 And People Who Were There” (PDF). This page doesn't list how fast this machine was. And if you're interested you can read the compiler's source code.

  • And so on; Knuth cares a lot about history and you can see some stuff he wrote, or collected, in his archives that he donated to the Computer History Museum: mentioned computers from the 1960s include the Burroughs 205, the SDS 900 (execution time 16 microseconds for additions, 32 microseconds for multiplications, 250–300 microseconds for operations on (24+9)-bit floating point), etc (lots on that page).

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.