THE BOOTH — a dart

BOOTH’S RECODING a run of ones is a subtract-then-add — 0111 = 1000 − 0001

Multiplying by a number full of 1-bits is wasteful: ×7 the naive way is three shift-adds. Booth’s insight: a run of ones from bit i up to bit j equals 2^(j+1) − 2^i — so 7 = 0111 = 1000 − 0001, and ×7 becomes one shift-and-subtract plus one add. Recoding the multiplier into signed digits turns long streaks of 1s into a single subtract at the bottom and add at the top. It is the standard signed-multiply algorithm in hardware, and it handles two’s-complement negatives for free.

THE TECHNIQUE run of 1s (i..j) = 2^(j+1) − 2^i — recode to signed digits

The demo shows ×7 via Booth’s identity 7 = 2³ − 2⁰, i.e. 8M − M, matching the direct product: live demo

HISTORY & CREDIT Andrew D. Booth · 1950

“More 1-bits, more adds.” — Booth turns a whole run of 1s into one subtract and one add, negatives included. cited

the identity · 2^i + … + 2^j = 2^(j+1) − 2^i — a run of ones is a high-minus-low difference.
the recode · scan bit pairs: 0→1 edge means subtract, 1→0 edge means add — signed-digit multiplier.
1950 · Andrew Donald Booth devised it (crystallography computing); still the hardware signed-multiply.

A streak of ones collapsed to one subtract and one add — the same product, signed digits, negatives free. resource

RECOMMEND FOR I-13 the run-of-ones identity, on the compiler

On the canonical compiler, 7×3 via Booth (8·3 − 3) returns 21 — matching the direct product:

$ i13 run tk_booth.i13 # 7*M as (M<<3) - M RUN OK · 18 step(s) · peak stack 2 · call depth 0 booth = 21 -- (3<<3) - 3 = 24 - 3 direct = 21 -- 7 * 3 same = 1 -- run of ones recoded to subtract+add

Recommend as a NULL — resource, with a signed-digit twist. Booth recoding computes the identical product (i13 prints 21) with fewer adds by rewriting runs of 1s as a subtract/add pair; the payoff is op count and free handling of negatives — both squarely resource (B40). The recoding is a change of the multiplier’s digit representation, which brushes the encoding gate (B44) too, but the output relation is untouched. NULL. It complements Russian-peasant (409): both read the multiplier’s bits, one exploiting parity, the other exploiting runs.