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.

- A term contributes to the result only if is 1, since if is 0, then the term becomes 1.
- 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;
}
```

`n % 2`

represents our bit . At each iteration, we only contribute the term to the result only if`n % 2`

is 1.- 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 .