Power (fast exponentiation)

Fast exponentiation: bⁿ = (b^(n/2))² when n is even. Squaring instead of repeated multiplying turns 1000 multiplications into ~10.

Category

Recursion

Time complexity

O(log n)

Space complexity

O(log n)

Pseudocode

if e = 0: return 1
even: h ← power(b, e/2); return h·h
odd: return b × power(b, e−1)
return

Reference implementation

def power(b, e):
    if e == 0: return 1
    if e % 2 == 0:
        h = power(b, e // 2)
        return h * h
    return b * power(b, e - 1)

Open the interactive Power (fast exponentiation) visualisation →