Week 49 of 125
TAOCP 3.2.2 Other Methods
Sign up or sign in to tick these off and give this week a due date.
-
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.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.