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?

  • 12
    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.
    – user722
    Aug 16, 2017 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, 2017 at 19:19
  • 3
    @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.
    – user
    Aug 16, 2017 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, 2017 at 19:49

4 Answers 4


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


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

  • 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, 2017 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, 2017 at 18:54

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

  • For context, that puts the B5000 in the same general ballpark as a circa-1980 microprocessor like the 6502, Z80, or 6809. The 220 and 205 were orders of magnitude slower. I'd say 4 million elements is indeed around the upper end of what the B5000 could comfortably handle.
    – Chromatix
    Sep 15, 2019 at 17:01

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.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .