Week 20: TAOCP 1.2.4 Integer Functions and Elementary Number Theory

Floor, ceiling, the mod operation defined for any real numbers, and the basics of congruences: divisibility, primes, relatively prime numbers, and Fermat's theorem.

Time About 7 hours this week

Why it matters

Floor and mod show up in every array index calculation, hash function, ring buffer and pagination bug you will ever write. Knuth's definition of mod for negative numbers is worth comparing with how your favorite language does it, because they differ.

Before you start

1.2.2 Numbers, Powers, and Logarithms

How to approach it

Work every identity about floor and ceiling with a few positive and negative examples. Then write a short program in C or Python comparing x mod y for negative x in Knuth's definition versus your language's % operator. Read the congruence material with pencil; it returns in Vol 2 chapter 4.

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.

Traps

Assuming floor(-x) = -floor(x). It does not.
Assuming C's % is Knuth's mod. For negative operands it is not.