Chapter 6 · Transform-and-Conquer
Horner's Rule & Binary Exponentiation
Rewrite the problem in a smarter form. A polynomial becomes nested multiply-and-add steps (Horner), and the exponent n becomes its binary digits, so aⁿ needs only about log₂ n multiplications instead of n − 1.
current column / bit
multiplication
addition / multiply-by-a
finished value
skipped (bit 0)
How to read this
- Horner table
- Top row: the coefficients from the highest power down. Middle row: x times the running value from the previous column. Bottom row: that product plus the coefficient above it. The last bottom cell is p(x); the other bottom cells are the coefficients of the quotient p(x) / (x − x₀), so the same table performs synthetic division.
- Bits of n
- For the exponentiation algorithms the top row is n in binary, most significant bit on the left. Under each bit you see what happened there: S = square, SM = square and then multiply by a. The right-to-left method instead squares a running term a, a², a⁴, a⁸, … and multiplies in only the terms whose bit is 1.
- Counters
- Horner does exactly n multiplications and n additions for a degree-n polynomial, versus n(n + 1)/2 multiplications if every power is computed from scratch. With b = the number of bits of n, binary exponentiation uses between b − 1 and 2(b − 1) multiplications (Levitin §6.5).
Try this
- Book check (Horner). Run the default p(x) = 2x⁴ − x³ + 3x² + x − 5 at x = 3. The bottom row reads 2, 5, 18, 55, 160: p(3) = 160, with 4 multiplications and 4 additions.
- Synthetic division. Try coefficients 1, −6, 11, −6 at x = 1. The remainder is 0, so 1 is a root, and the bottom row gives the quotient x² − 5x + 6.
- a¹³ both ways. n = 13 is 1101 in binary (b = 4 bits). Left-to-right: SM, S, SM after the leading 1, so 5 multiplications. Right-to-left also needs 5. Both sit between b − 1 = 3 and 2(b − 1) = 6.
- Best and worst n. Try n = 64 (1000000: only squarings, 6 multiplications) and n = 63 (111111: every bit costs two, 10 multiplications). The naive method would need 63 and 62.
- Modular power. Set a = 7, n = 560, m = 561. The answer is 1 even though 561 = 3·11·17 is not prime (a Carmichael number), and left-to-right needed only 11 multiplications (560 = 1000110000₂).