# Computing Powers

Suppose we wish to compute $$a^n$$ for a given real number $$a$$ and non-negative integer $$n$$. I guess the obvious way to accomplish this is like so:

function simple_power(a, n) {
let result = a;
for (let i = 1; i < n; i++) {
result = a * result;
}
return result;
}

An important question in the analysis of algorithms is:

How many arithmetic operations does this process take?

In this particular example, It’s pretty easy to see that the answer is $$n-1$$, since there’s one multiplication required for each step through the the loop from $$1$$ up to one less than $$n$$. In more complicated examples, we might wish to add code to count the operations. While not necessary in this super simple example, here’s one way to do so:

function trace_simple_power(a, n) {
let cnt = 0;
let result = simple_power(a, n);
return { result, cnt };

function simple_power(a, n) {
let result = a;
for (let i = 1; i < n; i++) {
cnt++;
result = a * result;
}
return result;
}
}

For example, it should take 6 multiplications to compute $$2^7$$:

trace_simple_power(2, 7)

## Reducing the number of steps

Here’s a recursive approach to computing , that results in far fewer computations:

function recursive_power(a, n) {
if (n == 0) {
return 1;
} else {
let x = recursive_power(a, Math.floor(n / 2));
if (n % 2 == 0) {
return x * x;
} else {
return a * x * x;
}
}
}

For example, here are 10 powers of two starting at $$n=0$$:

d3.range(10).map((n) => recursive_power(2, n))

Let’s build some traceing into this function:

function trace_recursive_power(a, n) {
let cnt = 0;

let result = power(a, n);
return { a, n, result, cnt };

function power(a, n) {
if (n == 0) {
return 1;
} else if (n == 1) {
return a;
} else {
let x = power(a, Math.floor(n / 2));
if (n % 2 == 0) {
cnt = cnt + 1;
return x * x;
} else {
cnt = cnt + 2;
return a * x * x;
}
}
}
}

For example, here’s how many multiplications are used to compute the first 20 non-negative powers of 2:

d3.range(20).map((n) => trace_recursive_power(2, n).cnt)

Hmm… looks a little complicated. Let’s plot the number of steps required to compute $$a^n$$ as a function of $$n$$:

Looks like the number of steps required is $$\log_2(n)$$ when $$n$$ is a power of $$2$$, it’s more complicated but less than twice that value when $$n$$ is one less than a power of $$2$$ and somewhere in between when $$n$$ is somewhere in between.

Most importantly, the number of steps required is far less than $$n-1$$ as $$n$$ grows.