TAOCP 3.1 Introduction: reading guide

What "random numbers" means for a computer, why truly random sources are awkward, and a tour of early attempts at generating pseudorandom numbers, including the middle-square method and why many ad hoc generators fail badly.

Time About 3 hours this week

Why it matters

Simulations, games, load testing, hashing and cryptography all depend on random numbers. This section is a warning against inventing your own generator.

Before you start

Vol 1 chapter 1 math

How to approach it

Implement the middle-square method and watch it fall into a short cycle. That one experiment teaches the whole section. Read Knuth's story of his own "super-random" generator failing; it is a great lesson in humility.

Exercises

Work every exercise rated 10 to 20; most are about tracing the algorithm by hand or tweaking one step, which is exactly the skill you want. Pick one or two rated 20 to 25 that involve modifying the algorithm and implement your modification in a real language with tests. Skip HM exercises unless you enjoy calculus, and treat anything rated 40+ as a research problem, not homework.

Traps

Believing that complicated means random. The section's whole point is that it does not.