Sign in to watch this lesson
Algorithms - Bits and Number Theory · 4:04
Binary Exponentiation
Compute a^b with O(log b) multiplications by letting the bits of the exponent pick which repeated squares to multiply: 13 = 1101, so 3^13 = 3^8 * 3^4 * 3^1 = 1594323, with the 9 skipped. We trace the iterative loop, add the modulus safely (reduce a first, start from 1 % m, keep products in range), then swap numbers for 2x2 matrices and permutations to get Fibonacci numbers and repeated shuffles from the same skeleton. Measured on this Mac: 10^8 one-by-one multiplications took about 0.4 s against about 0.3 microseconds for the loop, and for moduli near 10^18 the product needs 128-bit arithmetic.
You will learn
- Explain how the binary digits of b decide which repeated squares of a are multiplied, giving a^b in O(log b) multiplications.
- Write the iterative modular version correctly: a %= m first, res = 1 % m, and products that fit (long long for m around 1e9, unsigned __int128 for m near 1e18).
- Apply the same loop to any associative operation: 2x2 matrices for Fibonacci numbers (F(n) mod p for n = 10^18) and permutations applied k times.
- Estimate and measure the speedup over repeated multiplication, and recognise the edge cases b = 0, m = 1 and negative or oversized a.