Skip to content

Instantly share code, notes, and snippets.

@bmershon

bmershon/.block

Last active March 3, 2017 05:47
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bmershon/496aa57731fdc6b83b0d7ea8d75cda62 to your computer and use it in GitHub Desktop.
Save bmershon/496aa57731fdc6b83b0d7ea8d75cda62 to your computer and use it in GitHub Desktop.
Download ZIP
Greatest Common Measure
Raw
.block
border: no
license: MIT
Raw
README.md

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).

Raw
gcd.js
// Returns the greatest common denominator of
// a and b, where a is greater than or equal to b.
// The given pair a, b must have a common divisor.
// The actions array is populated with a history of
// objects representing actions along with snapshots
// of the state of the algorithm throughout the procedure.
function gcd(a, b, actions) {
function _gcd(a, b) {
while (a !== b) {
a = remainder(a, b);
actions.push(reset(a, b));
[a, b] = [b, a];
actions.push(swap(a, b));
}
actions.push(end(a));
return a;
}
// a is greater than or equal to b
function remainder(a, b) {
if (a <= b) return a;
if (a - b <= b) {
actions.push(shorten(a - b, b));
return a - b;
}
actions.push(lengthen(a, b + b));
a = remainder(a, b + b);
if (a <= b) return a;
actions.push(reset(a, b));
actions.push(shorten(a - b, b));
return a - b;
}
function swap(a, b) {
return { type: "swap", a: a, b: b};
}
function shorten(a, b) {
return { type: "shorten", a: a, b: b };
}
function end(a) {
return { type: "end", a: a };
}
function lengthen(a, b) {
return { type: "lengthen", a: a, b: b };
}
function reset(a, b) {
return { type: "reset", a: a, b: b };
}
return _gcd(a, b);
}
Raw
index.html
<!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>
@bmershon
Copy link
Author

bmershon commented Mar 2, 2017

The shorten() event should not affect segment b's length. Let reset() reduce b back to its original length before a and b are swapped.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment