# Algorithm Fast-Exponentiate

``````    Algorithm Fast-Exponentiate(x, n)
if n = 0 then
return 1
else if n is even then
return Fast-Exponentiate(x^2, n / 2)
else
return x * Fast-Exponentiate(x^2, (n - 1) / 2)
fi

IN Fast-Exponentiate(2, 10)
10 is even:
IN Fast-Exponentiate(4, 5)
5 is odd:
IN Fast-Exponentiate(16, 2)
5 is odd:
IN Fast-Exponentiate(256, 1)
5 is odd:
IN Fast-Exponentiate(32768, 0)
return 1
return 256
return 256
return 1024
return 1024
``````

Correctness: We prove this using induction on n. The base case, when n is 0, is easy: Fast-Exponentiate(x, 0) = 1 = x\^0. Say it works for all n smaller than k. Does it work for k? If k is even, then k/2 is smaller than k, so

``````      Fast-Exponentiate(x, k) = Fast-Exponentiate(x^2, k / 2)
= (x^2)^(k / 2)
= x^(2(k/2))
= x^k
``````

If k is odd, then (k - 1)/2 is smaller than k, so

``````      Fast-Exponentiate(x, k) = x * Fast-Exponentiate(x^2, (k - 1) / 2)
= x * (x^2)^((k - 1) / 2)
= x * x^(2((k - 1)/2))
= x * x^(k - 1)
= x^k
``````

Time bound: We use a recurrence.

``````      T(1) = 1
T(n) < T(n / 2) + 1
``````

Using the Master Theorem (see textbook appendix), we see that

``````      T(n) = O(log_2 n)
``````