Week 61 of 125
TAOCP 4.3.1 The Classical Algorithms
Sign up or sign in to tick these off and give this week a due date.
-
Grade-school arithmetic on arbitrarily long integers: addition, subtraction, multiplication and especially long division, where Knuth gives a careful algorithm for estimating each quotient digit and proves it is almost always right.
Time About 10 hours this week
Why it matters
Every bignum library (Python ints, Java BigInteger, crypto libraries) is built on these. The long division algorithm is notoriously easy to get subtly wrong.
Before you start
- 4.1 Positional Number Systems
How to approach it
Implement all four operations for numbers stored as arrays of 32-bit digits in C, with 64-bit intermediates. Test against Python's integers on random inputs. Spend most of the time on division and its normalization step.
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
- Forgetting to normalize the divisor before division.
- Overflow in the quotient-digit estimate.
- Edge cases: divisor with one digit, leading zero digits, dividend smaller than divisor.
-
NeetCode LeetCode: 2 NeetCode 150 problems
Two problems from the NeetCode 150, in order. One box for the pair.