TAOCP 3.2.2 Other Methods: reading guide

Generators beyond the basic LCG: quadratic and higher-order congruences, additive (lagged Fibonacci) generators, combining generators, and shuffling the output of one generator using another to break up patterns.

Time About 7 hours this week

Why it matters

Modern generators like xorshift, PCG and Mersenne Twister descend from these ideas. Knowing the families helps you judge a library's choice.

Before you start

3.2.1 The Linear Congruential Method

How to approach it

Implement an additive lagged-Fibonacci generator and a shuffling combiner. Do not try to absorb every proof; aim to know what each family is and its main trade-off.

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

Thinking combining two weak generators always gives a strong one. Sometimes it does, sometimes it does not.