How powerful was Knuth’s computer?

Question

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?

Answer 1

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):

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).

Answer 2

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: https://en.wikipedia.org/wiki/IBM_System/360_Model_67

Answer 3

Knuth was at CalTech before moving to Stanford in 1968 and continued consulting with Burroughs until that time. As ShreevatsaR mentions, he worked on an Algol-58 compiler for the Burroughs 205 (1954), which was a decimal, drum-memory, vacuum tube system with a 143KHz clock rate, 11-digit words (10 plus sign), and sequential, digit-by-digit arithmetic. Average access time on the main portion of the memory drum was 8.4ms, but there was a small portion of the drum that provided 10x faster access.

Execution of an integer or floating-point add (including fetch) would typically take 2.5ms if executed from the fast portion of the drum and 18ms if from the main portion. [private correspondence with Prof. Knuth and Tom Sawyer]

Knuth also worked on the BALGOL compiler for the Burroughs 220 (1958). This was a core-memory system with a 200KHz clock rate. It used essentially the same digit-sequential arithmetic as the 205. Integer add time was 0.185-0.245ms; floating add took 0.215-0.415ms. B220 Operational Characteristics

Knuth also worked during this time on the Burroughs B5000/B5500. This ran at 1MHz and used a 48-bit binary word with a 4-6µs memory access time. It used a unified integer/floating numeric format where integers were considered specially-normalized floating-point numbers. Add times are difficult to generalize due to stack adjustment and variance in normalization, but it had a 1-clock parallel adder, so my guess is that most adds took about 10µs. B5281 Processor Training Manual, B5000 Processor Flow Charts

Answer 4

The answer can perhaps be inferred from this page with results from the Whetstone benchmarks.

A B5500 clocks in at 0.064 "million whetstone instructions per second", an HP Pentium II system gets 169.

I selected the B5500 since Knuth is known to have been associated with Burroughs at that time (see other answers), and the HP system since it was the most recent Intel-based computer I could see at a quick glance.

The Whetstone benchmark is explained at the same site, in case you're not familiar with it.