Week 60 of 125
TAOCP 4.2.3 and 4.2.4
Sign up or sign in to tick these off and give this week a due date.
-
Building higher-precision floating arithmetic out of single-precision operations, with care for carries and rounding.
Time About 4 hours this week
Why it matters
The same idea powers double-double and quad-double libraries used when 64-bit floats are not enough.
Before you start
- 4.2.2 Accuracy of Floating Point Arithmetic
How to approach it
Read for the method. Skim MIX-heavy details. If you are curious, look up the two-sum trick, which is the modern building block.
Exercises
This is a light section. Skim the exercises, do the ones rated 10 or under in your head, and spend the spare time catching up on earlier exercises you skipped.
-
Why leading digits of real-world numbers are not uniformly distributed but follow a logarithmic law (smaller leading digits are more common), and what that means for floating-point error.
Time About 4 hours this week
Why it matters
Benford's law is a famous, surprising result that has real uses, including fraud detection. It also explains why some rounding error estimates are pessimistic.
Before you start
- 4.2.2 Accuracy of Floating Point Arithmetic
- 1.2.2 Logarithms
How to approach it
Download any numeric dataset (populations, file sizes) and check the leading-digit distribution. Then read the explanation.
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.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.