Knuth · Weeks 64 to 89

TAOCP Volume 2: Seminumerical Algorithms

Volume 2 is about numbers as computers see them. Chapter 3 is random numbers: how to generate them, how to test them, and how to turn them into shuffles and samples. Chapter 4 is arithmetic: floating point, bignums, fast multiplication, gcd, factoring and polynomials. Some sections are deep number theory; the guides tell you where to dig in and where to skim.

26weeks

30reading guides

918exercises

~198hours

Every section, week by week

Section	Week	Exercises	Picked	Time
3.1 Introduction	64	23 (10 to M48)	8	3 h
3.2.1 The Linear Congruential Method	65	49 (10 to 40)	8	8 h
3.2.2 Other Methods	66	37 (00 to M40)	8	7 h
3.3.1 General Test Procedures	67	25 (00 to HM48)	8	7 h
3.3.2 Empirical Tests	68	35 (00 to M46)	8	8 h
3.3.3 Theoretical Tests	69	28 (M10 to M40)	8	5 h
3.3.4 The Spectral Test	70	32 (M10 to HM47)	8	9 h
3.4.1 Numerical Distributions	71	33 (10 to HM40)	8	9 h
3.4.2 Random Sampling and Shuffling	72	17 (M12 to M39)	8	6 h
3.5 What Is a Random Sequence?	73	44 (10 to HM50)	8	6 h
3.6 Summary	73	15 (15 to 46)	7	2 h
4.1 Positional Number Systems	74	34 (00 to M40)	8	5 h
4.2.1 Single-Precision Calculations	75	19 (10 to 40)	8	8 h
4.2.2 Accuracy of Floating Point Arithmetic	76	31 (10 to M40)	8	8 h
4.2.3 Double-Precision Calculations	77	9 (16 to M42)	5	4 h
4.2.4 Distribution of Floating Point Numbers	77	20 (13 to 42)	7	4 h
4.3.1 The Classical Algorithms	78	43 (10 to 42)	8	10 h
4.3.2 Modular Arithmetic	79	14 (M10 to M30)	8	6 h
4.3.3 How Fast Can We Multiply?	80	19 (M15 to M49)	8	9 h
4.4 Radix Conversion	81	19 (16 to M47)	8	6 h
4.5.1 Fractions	82	16 (10 to 42)	6	3 h
4.5.2 The Greatest Common Divisor	82	42 (18 to HM49)	8	7 h
4.5.3 Analysis of Euclid's Algorithm	83	51 (20 to HM46)	8	8 h
4.5.4 Factoring into Primes	84	47 (10 to M50)	8	10 h
4.6.1 Division of Polynomials	85	31 (10 to M40)	8	7 h
4.6.2 Factorization of Polynomials	86	41 (20 to M47)	8	7 h
4.6.3 Evaluation of Powers	87	42 (10 to M50)	8	7 h
4.6.4 Evaluation of Polynomials	88	74 (15 to M50)	8	9 h
4.7 Manipulation of Power Series	89	28 (M00 to HM35)	8	5 h
Vol 2 review	89	918 (00 to HM50)	8	5 h

Each section links to its reading guide: what it covers, how to approach it, exercises picked from the book with their ratings, common traps and links. Picked is how many exercises the guide recommends; time is its budget for the week.

What you will be able to do

Pick, use and test a random number generator, and avoid the classic biased-shuffle and modulo-bias bugs.
Explain floating-point error and write numerically careful code.
Implement arbitrary-precision arithmetic, including long division and a faster-than-schoolbook multiply.
Implement gcd, modular inverses, primality testing and Pollard rho factoring.

Before you start

Vol 1 math, especially 1.2.4 (number theory) and 1.2.9 (generating functions).
Basic probability and statistics: mean, variance, distributions.
C or another language with 64-bit integers for the bignum work.

Getting the book

The current edition is the third edition (1997), ISBN 0-201-89684-2.

Vol 2, 3rd edition is about $64 new from InformIT, less used. Borrow before you buy: many public and university libraries give you free access to O'Reilly Learning, which carries TAOCP; Libby/OverDrive and interlibrary loan (search WorldCat) work too. Older used editions are fine for Vols 1 to 3; section numbers barely changed. If you buy the eBook, get the PDF from InformIT. Knuth himself warns that the Kindle and ePUB versions mangle the math.

What you need has every option with prices, and which edition do I need covers the differences.

Tips

3.3.3 and parts of 3.5, 4.5.3 and 4.6.2 are heavy math. It is fine to read for ideas and move on.
Turn the bignum work into a small library with tests; you will reuse it.

Questions

How long does TAOCP Volume 2 take?

On the cracked.guide path it takes 26 weeks (weeks 64 to 89), about 6 months, and the reading guides budget about 198 hours in all.

How many exercises are in TAOCP Volume 2?

918 in the sections the path covers, rated 00 to HM50, and about 240 of them carry Knuth's triangle for recommended. Each reading guide picks the ones worth your time.

Which edition of Volume 2 do I need?

The current one is the third edition (1997). Older used editions work for most of it; section numbers barely changed. Buy the PDF, not Kindle, if you want an eBook.