Greatest Common Measure

While working through Stepanov and Rose's From Mathematics to Generic Programming, it struck me that the pencil and paper exercises I performed in order to understand the algorithms presented in the text would pose an interesting challenge if I wanted to recreate them... programatically. As the difficulty of the text and its examples ramps up, I wanted to begin with some milder exercises which might lend themselves most easily to visualization.

This example is an illustration a method for finding the greatest common "measure" for two line segments for which a common measure exists (also known as the greatest common divisor). For example, gcd(14, 21) = 7. This is Pythagoras's world: numbers are expected to come in discrete, whole units. And in Euclid's world, those numbers are line segments with nonzero length. Although this greatest common measure algorithm may be humble in what it accomplishes, this example demonstrates an approach to visualizing the work done by an algorithm which even includes recursion.

A history of work performed is created by emitting actions along with pieces of useful information throughout the algorithm's execution. The history (an array of actions) is played forward in time by rendering changes to a visual representation of the state of the algorithm. In this particular case, the state of the algorithm was that of two line segments which are lengthened, shortened, and "swapped" during the course of the algorithm. Alternative visualizations might benefit from choosing spatial separation of the steps of an algorithm over temporal separation (as this example uses).

See pages 48-49 of From Mathematics to Generic Programming.

See also a wiki of solutions (in progress).

<!DOCTYPE html>
<meta charset="utf-8">
<script src="https://d3js.org/d3.v4.min.js"></script>
<svg width="960" height="500"></svg>
<script src="gcd.js"></script>
<script>

var svg = d3.select("svg"),
    width = +svg.attr("width"),
    height = +svg.attr("height"),
    margin = { left: 50, right: 50 };

var a = 45,
    b = 6,
    actions = [];

gcd(a, b, actions);
actions.reverse();

var x = d3.scaleLinear()
    .domain([0, a])
    .range([margin.left, width - margin.right]);

var y = d3.scaleLinear()
    .domain([0, 1]) // Reset after first test.
    .range([5 * height / 11, 7 * height / 11]);

var color = d3.scaleOrdinal()
    .domain([0, 1])
    .range(["#000", "#D62728"]);

var text = svg.selectAll("text")
    .data([a, b]);

text.enter().append("text")
    .attr("x", function(d) { return x(d / 2); })
    .attr("y", function(d, i) { return y(i); })
    .attr("dy", -10)
    .attr("font-family", "helvetica")
    .attr("font-size", "18px")
    .attr("text-anchor", "middle")
    .text(function(d) { return d.toString(); });

var segmentA = svg.append("line")
    .attr("x1", x(0))
    .attr("y1", y(0))
    .attr("x2", x(a))
    .attr("y2", y(0))
    .attr("stroke", color(0))
    .attr("stroke-width", "5px");

var segmentB = svg.append("line")
    .attr("x1", x(0))
    .attr("y1", y(1))
    .attr("x2", x(b))
    .attr("y2", y(1))
    .attr("stroke", color(1))
    .attr("stroke-width", "5px");

var timer = d3.interval(function(elapsed) {
  animate(actions.pop());
  if (actions.length === 0) timer.stop();
}, 2000);

function animate(action) {
  var t = segmentB;

switch(action.type) {
    case "shorten":
      svg.selectAll("text").data([action.a, action.b])
        .transition()
          .delay(function(d, i) { return - 200 * i + 200})
          .duration(750)
          .attr("x", function(d) { return x(d / 2); })
          .text(function(d) { return d.toString(); });

segmentA
          .attr("x1", x(action.b))
        .transition().delay(200).duration(750)
          .duration(500)
          .attr("x1", x(0))
          .attr("x2", x(action.a));

segmentB
        .transition()
          .duration(750)
          .attr("x2", x(action.b));

break;

case "swap":
      segmentA.transition()
          .duration(300)
          .ease(d3.easeLinear)
          .attr("y1", y(1))
          .attr("y2", y(1))
          .attr("stroke", color(1));

segmentB.transition()
          .duration(300)
          .ease(d3.easeLinear)
          .attr("y1", y(0))
          .attr("y2", y(0))
          .attr("stroke", color(0));

svg.selectAll("text").data([action.a, action.b])
        .transition().duration(200)
          .attr("opacity", 0)
          .on("end", function() {
            d3.select(this)
                .attr("x", function(d) { return x(d / 2); })
              .transition().duration(300)
                .attr("opacity", 1)
                .text(function(d) { return d.toString(); });
          });

segmentB = segmentA;
      segmentA = t;
      break;

case "lengthen":
      segmentB
          .attr("stroke-dasharray", "5, 5")
        .transition()
          .duration(500)
          .ease(d3.easeCubicIn)
          .attr("x2", x(action.b));

svg.selectAll("text").data([action.a, action.b])
        .transition().duration(500)
          .ease(d3.easeCubicIn)
          .attr("x", function(d) { return x(d / 2); })
          .text(function(d) { return d.toString(); });
      break;

case "reset":
      segmentB
        .transition()
          .duration(300)
          .ease(d3.easeCubicIn)
          .attr("x2", x(action.b))
          .on("end", function() {
            d3.select(this)
              .attr("stroke-dasharray", "none");
          });

svg.selectAll("text").data([action.a, action.b])
        .transition().duration(300)
          .ease(d3.easeCubicIn)
          .attr("x", function(d) { return x(d / 2); })
          .text(function(d) { return d.toString(); });

break;

case "end":
      segmentA.transition()
        .duration(250)
        .attr("stroke-opacity", 1);

segmentB.transition()
        .duration(250)
        .attr("stroke", "none");

text = svg.selectAll("text").data([action.a])
        
      text.transition().duration(250)
          .attr("text-anchor", "start")
          .attr("x", function(d) { return x(0); })
          .text(function(d) {
            return "gcd(" + a + ", " + b + ") = " + d.toString();
          })

text.exit().remove();
      break;
  }
}
</script>

https://d3js.org/d3.v4.min.js