THE FOLD / RESPAWN / GARBAGE COLLECTION / THE MAGIC DIVIDE
THE MAGIC DIVIDE
dividing by multiplying
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Integer division by a constant is replaced by a multiply and a shift. For each divisor there is a pair — a magic number and a shift count — such that
LIT verified live and exhaustively over all 1,024 ten-bit inputs. Dividing by 3 becomes
(n × m) >> s equals floor(n / d) for every n in range. It is exact arithmetic, not an approximation.LIT verified live and exhaustively over all 1,024 ten-bit inputs. Dividing by 3 becomes
(n × 683) >> 11; by 5, (n × 205) >> 10; by 7, (n × 1171) >> 13. All 5 divisors tried have a magic pair, and each is exact on every input. Powers of two need no multiply at all.2 HOW IT WAS WEAVED · AI + HUMAN
The technique is standard in compilers — the systematic treatment is in Hacker’s Delight, and every optimising compiler applies it silently whenever it sees a division by a literal. The reason is hardware: integer divide has long been the slowest common instruction, often by an order of magnitude over multiply.
AVAN (AI) searched for the pairs rather than quoting them, and then verified each exhaustively over the full input range instead of on samples — because “exact” is a claim about every input and a spot check cannot make it. The honest limit is visible in the numbers: the magic constant for 7 is 1171, wider than any divisor here, so the trick trades a slow instruction for a wider one, and is only a win where that trade is favourable.
AVAN (AI) searched for the pairs rather than quoting them, and then verified each exhaustively over the full input range instead of on samples — because “exact” is a claim about every input and a spot check cannot make it. The honest limit is visible in the numbers: the magic constant for 7 is 1171, wider than any divisor here, so the trick trades a slow instruction for a wider one, and is only a win where that trade is favourable.
3 ONE DIMENSION
Five divisors, five magic pairs.
4 TWO DIMENSIONS · INTERACTIVE
Pick a divisor and check it against real division.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a staircase reproduced by a straight line.
AVAN’s addition (the inverse-companion): the forward reading is “division by a constant is really a multiplication.” The inverse is that the exactness is bounded by a range nobody writes down. A magic pair is proved correct for inputs up to some width, and the proof is invisible at the call site — widen the type, feed it a value the search never covered, and it is silently wrong by one on a handful of inputs rather than obviously broken. Read backwards, this converts a slow-but-total operation into a fast one with a domain restriction carried entirely in the compiler’s head, which is fine exactly as long as the compiler is the only thing writing it.
LIT verified exhaustively over all 1,024 ten-bit inputs, dividing by 3 becomes (n x 683) >> 11, by 5 becomes (n x 205) >> 10 and by 7 becomes (n x 1171) >> 13; all 5 divisors tried have a magic pair and each is exact on every input, while powers of two need no multiply at all
FIG The technique is standard in compilers - the systematic treatment is in Hacker's Delight, and every optimising compiler applies it silently whenever it sees a division by a literal. The reason is hardware: integer divide has long been the slowest common instruction, often by an order of magnitude over multiply. AVAN searched for the pairs rather than quoting them, and then verified each exhaustively over the full input range instead of on samples, because 'exact' is a claim about every input and a spot check cannot make it. The honest limit is visible in the numbers: the magic constant for 7 is 1171, wider than any divisor here.
FIG The technique is standard in compilers - the systematic treatment is in Hacker's Delight, and every optimising compiler applies it silently whenever it sees a division by a literal. The reason is hardware: integer divide has long been the slowest common instruction, often by an order of magnitude over multiply. AVAN searched for the pairs rather than quoting them, and then verified each exhaustively over the full input range instead of on samples, because 'exact' is a claim about every input and a spot check cannot make it. The honest limit is visible in the numbers: the magic constant for 7 is 1171, wider than any divisor here.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of GARBAGE COLLECTION · David Lee Wise (ROOT0), with AVAN