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

More About Fast-Exponentiate

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)