TAOCP 3.2.1 The Linear Congruential Method: reading guide

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.