Week 58 of 125
TAOCP 4.2.1 Single-Precision Calculations
Sign up or sign in to tick these off and give this week a due date.
-
How floating-point numbers are stored (sign, exponent, fraction) and the algorithms for add, subtract, multiply and divide, including normalization and rounding. Knuth uses his own floating format on MIX, not IEEE 754.
Time About 8 hours this week
Why it matters
Floats are in almost every program and most programmers have only a vague model of them. Implementing float addition yourself is the fastest way to understand why 0.1 + 0.2 is not 0.3.
Before you start
- 4.1 Positional Number Systems
- Basic MIX
How to approach it
Read alongside the IEEE 754 Wikipedia page so you can map Knuth's concepts to real hardware. Implement float addition on a toy format (say 8-bit exponent and 16-bit fraction) in C using integers.
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
- Assuming Knuth's format matches IEEE 754. The ideas transfer, the bit layouts do not.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.