Fast Exponentiation

The Idea

Write the exponent in binary. 13 is 1101, so 3**13 is 3**8 * 3**4 * 3**1.

Each rung of the ladder is the square of the one below it, so reaching 3**8 costs three multiplications rather than seven. Keep the rungs whose digit is 1 and the whole power lands in about log n steps.

Real-World Example

Public-key handshakes raise a number to a 2048-bit exponent on every TLS connection. Multiplying one at a time would outlast the universe; squaring means roughly 2048 steps, which is why pow(base, exp, mod) finishes before the page loads.

The Code

def power(base, exp, mod):
    result = 1
    while exp:                          # one pass per binary digit
        if exp & 1:                     # this digit is on -> keep the rung
            result = result * base % mod
        base = base * base % mod        # climb: b, b², b⁴, b⁸ …
        exp >>= 1
    return result

print(power(3, 13, 10 ** 9 + 7))  # 1594323
print(power(3, 13, 1000))         # 323
print(power(2, 1000, 1000))       # 376  -> last three digits of 2**1000

print(power(2, 10, 1000))