Week 48 of 125
TAOCP 3.1 and 3.2.1
Sign up or sign in to tick these off and give this week a due date.
-
Knuth Knuth 3.1 Introduction
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.
-
The classic generator X_{n+1} = (aX_n + c) mod m. Knuth covers how to choose the modulus, the exact conditions on a and c for the longest possible period, and the notion of potency that rules out multipliers that are technically fine but bad in practice.
Time About 8 hours this week
Why it matters
LCGs are still inside many standard libraries and games, and knowing their weaknesses (low bits with short periods, patterns in higher dimensions) saves you from subtle simulation bugs.
Before you start
- 1.2.4 Integer Functions and Elementary Number Theory
- 3.1 Introduction
How to approach it
Read 3.2.1.1 (modulus), 3.2.1.2 (multiplier) and 3.2.1.3 (potency). Write an LCG with a small modulus like 16 or 64 and print the full sequence to see the period theorem in action. Then print the lowest bit of a power-of-two-modulus LCG and watch it alternate.
Exercises
Do every exercise rated 00 to 20 in your head or on paper; they are quick and they check you actually absorbed the definitions. Then pick two or three rated 20 to 25 (M or not) and grind them out fully. Attempt one M25 to M30 and give yourself a hard 90-minute cap before reading the answer. Always read the answer to every exercise you attempted, even the ones you got, because Knuth's answers often teach a second technique.
Traps
- Using the low bits of a power-of-two LCG. They have tiny periods.
- Assuming full period means good quality. It does not; the spectral test (3.3.4) is about that.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.