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\):

{
  let w = width < 900 ? width : 900;
  let h = 0.625 * w;
  let div = d3
    .create("div")
    .style("width", `${w}px`)
    .style("height", `${h}px`)
    .style("position", "relative");
  let pts = d3.range(129).map((n) => [n, trace_recursive_power(2, n).cnt]);
  let data = d3.range(129).map((n) => trace_recursive_power(2, n));
  let plot = Plot.plot({
    width: w,
    height: h,
    marks: [
      Plot.line(data, { x: "n", y: "cnt", strokeWidth: 0.8 }),
      Plot.dot(data, {
        x: "n",
        y: "cnt",
        fill: "black",
        title: (d) => `n=${d.n}, cnt=${d.cnt}`,
        r: 4
      }),
      Plot.line(
        d3.range(129).map((n) => [n, Math.log2(n)]),
        { strokeDasharray: [3, 5] }
      ),
      Plot.line(
        d3.range(129).map((n) => [n, 2 * Math.log2(n)]),
        { strokeDasharray: [3, 5] }
      ),
      Plot.ruleX([0]),
      Plot.ruleY([0])
    ]
  });

  div.append(() => plot);

  div
    .append("div")
    .style("transform", `scale(${(w / 900) ** 0.5})`)
    .style("position", "absolute")
    .style("top", `${0.15 * h}px`)
    .style("left", `${0.25 * w}px`)
    .html(tex`\text{cnt} = 2\log_2(n)`.outerHTML);
  div
    .append("div")
    .style("transform", `scale(${(w / 900) ** 0.5})`)
    .style("position", "absolute")
    .style("top", `${0.55 * h}px`)
    .style("left", `${0.6 * w}px`)
    .html(tex`\text{cnt} = \log_2(n)`.outerHTML);

  return div.node();
}

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.