Exponentiation By Squaring

In this post, I want to talk about a fast exponentiation algorithm that I learned recently.

Our goal is to write a function double exp(double x, int n); which returns .

Naive Implementation

double exp(double x, int n) {
  if (n < 0) return 1 / exp(x, -n);
  double result = 1;
  while (n--) result *= x;
  return result;
}

We have an algorithm here. Let’s improve it to be . The algorithm is called Exponentiation by Squaring.

Recursive Approach

In this approach we derive the recursive relation and the implementation is quite straight forward.

Key Property

Implementation

double exp(double x, int n) {
  if (n < 0) return 1 / exp(x, -n);
  if (n == 0) return 1;
  return (n % 2 == 1 ? x : 1) * exp(x * x, n / 2);
}

Since we divide the problem in half at each step, we get our algorithm.

Iterative Approach

In this approach, we iterate through the bits of and accumulate the result to .

Key Property

Consider the binary representation of where each are binary digits.

Plugging this into we get,

We notice 2 things here.

  1. A term contributes to the result only if is 1, since if is 0, then the term becomes 1.
  2. As we iterate through starting from 0, starts at and gets squared every iteration.

Implementation

double exp(double x, int n) {
  if (n < 0) return 1 / exp(x, -n);
  double result = 1;
  while (n > 0) {
    if (n % 2 == 1) result *= x;
    x *= x;
    n /= 2;
  }  // while
  return result;
}
  1. n % 2 represents our bit . At each iteration, we only contribute the term to the result only if n % 2 is 1.
  2. The variable x represents the . It starts at and gets squared on every iteration.

Some Numbers

These are performance numbers for computing for

Approach Time (ms)
Naive 1733
Recursive 1670
Iterative 267
std::pow 7099

Clearly the iterative algorithm is the most efficient and it seems that even though the recursive algorithm is also logarithmic, it’s not actually that much better than the naive version at .