THE FAST EXPONENTIATION — a dart

THE FAST EXPONENTIATION square and multiply — b^n in log n steps, not n

To raise a number to the 13th power you do not need twelve multiplications. Write the exponent in binary and square repeatedly, multiplying in the base only where a bit is set: b⁹ = ((b²)²…), folding the exponent one bit at a time. Thirteen collapses to about four squarings — O(log n) instead of O(n). The same idea powers modular exponentiation, the engine under RSA and Diffie-Hellman, where n has hundreds of bits and the naive loop would never finish. It is over two thousand years old: Pingala used it for Sanskrit meter.

THE TECHNIQUE square each step, multiply in b on set bits — O(log n)

The demo computes 3^13 by squaring vs by the naive 13-multiply loop, and shows both reach 1594323 — one in far fewer multiplies: live demo

HISTORY & CREDIT Pingala ~200 BCE · binary exponentiation

“b^n is n multiplications.” — it is about log₂n squarings; the exponent’s binary digits pick which squares to keep. cited

the recurrence · bⁿ = (b²)^(n/2) if n even, else b·(b²)^((n−1)/2) — halve the exponent each step.
the cost · about log₂n squarings + popcount(n) multiplies — exponential speedup.
~200 BCE · Pingala’s Chandahśāstra used it for counting meters; the modern core of RSA/Diffie-Hellman.

The exponent read in binary, folded by squaring — log-many steps to the same power. resource

RECOMMEND FOR I-13 square-and-multiply, on the compiler

On the canonical compiler, 3^13 by squaring and by the naive 13-step loop both return 1594323:

$ i13 run tk_fastexp.i13 # square-and-multiply vs naive loop RUN OK · 333 step(s) · peak stack 5 · call depth 14 r_fast = 1594323 -- ~4 squarings + 3 mults r_slow = 1594323 -- 13 multiplications same = 1 -- identical power

Recommend as a NULL — the resource axis at its most dramatic. Square-and-multiply turns O(n) into O(log n), the difference between finishing and never finishing for cryptographic exponents. And yet the output is bit-identical: i13 prints 1594323 both ways. It is the clearest argument that asymptotic complexity is not an output-relation — two mechanisms computing the same function, one exponentially cheaper, same value. Exactly the B40 gate; NULL, and the batch’s strongest teaching case for it.