Counting steps

Since we’re beginning this course in discrete mathematics with a focus on counting and since we’re mostly computer science majors, let’s take a look at how counting comes up in the analysis of algorithms. In the process, we might bump into a new friend.

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.

Double loop counts

Here’s a simple function that counts number of times through a double loop:

function count_ops(n) {
  let cnt = 0;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      // Do something symmetric in i and j
      cnt++;
    }
  }
  return cnt;
}

Let’s try it for the first 16 integers:

d3.range(16).map((n) => count_ops(n))

Hmm… Those numbers look familiar. In fact, we see the positive integers in that list along the second diagonal of Pascal’s triangle:

pascals_triangle

That suggests that these numbers are exactly \[{{n}\choose{2}}.\]

import { pascals_triangle } from "6fe4d0894b6a9673"