Week 64 of 125
TAOCP 4.4 Radix Conversion
Sign up or sign in to tick these off and give this week a due date.
-
Converting numbers between bases efficiently, for integers and fractions, by multiplication or division, and how to do it correctly with floating point and multiple precision.
Time About 6 hours this week
Why it matters
Printing and parsing numbers correctly (especially floats) is surprisingly hard; many languages had bugs here for decades.
Before you start
- 4.1 Positional Number Systems
- 4.3.1 The Classical Algorithms
How to approach it
Implement integer to decimal string for your bignums. Then read about fraction conversion and think about why printing the shortest float that round-trips is hard.
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
- Converting fractions with floats and accumulating rounding error.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.