Number of Primes

A proposed solution to exercise 3.3 from Stepanov and Rose's From Mathematics to Generic Programming. The exercise asks us to graph the number of primes less than n using an analytic approximation.

The black line represents the actual number of primes less than x.
The dashed red line represents an approximating function π = (x) => x / Math.log(x).
Orange dots represent the measured time taken to sift a sieve for the given input size. Their scale is necessarily different from the one used for displaying the counts of primes; it reflects relative differences in the milliseconds taken to run the Sieve of Eratosthenes algorithm.

A Web Worker performs each test of increasing input size and reports back to the main thread with the number of primes found that are less than the input. Only one test actually needs to be run in order to graph the prime-counting function; however, by running each test separately in a WebWorker (each with a successively larger different input size), one can perform a complexity analysis of the various implementations of the Sieve of Eratosthenes.

Using Web Workers in this example also helps us avoid locking up the main user interface thread while the algorithm is executing.

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

var svg = d3.select("svg"),
    chart,
    width = svg.attr("width"),
    height = svg.attr("height"),
    margin = { left: 50, right: 50, top: 20, bottom: 20 },
    worker = new Worker("./worker.js"),
    min = 1e1,
    max = 1e7,
    numTrials = 20,
    step = (max - min) / numTrials,
    results = [];

chart = svg.append("g")
  .attr("transform", "translate(0" + "," + -20 + ")");

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

var y = d3.scaleLinear()
    .domain([0, Infinity]) // Reset after first test.
    .range([+height - margin.bottom, 10]);

var y2 = d3.scaleLinear()
    .domain([0, Infinity]) // Reset after first test.
    .range([+height - margin.bottom, 10]);

// Analytic Approximation.
var π = function(x) { return x / Math.log(x); }

axis = chart.append("g")
    .attr("transform", "translate(0," + y(0) + ")")
    .call(d3.axisBottom(x)
            .tickFormat(d3.format("d")));

var line = d3.line()
    .x(function(d) { return x(d.n); })
    .y(function(d) { return +y(d.count); });

var analyticLine = d3.line()
    .x(function(d) { return x(d.n); })
    .y(function(d) { return +y(π(d.n)); });

var rect = svg.append("rect")
    .attr("x", 0)
    .attr("y", 0)
    .attr("width", 0)
    .attr("height", 3)
    .attr("fill", "rgb(240, 0, 0)");

path = chart.append("path");

// Run tests to generate primes, starting at those primes
// less than 1,000 and ending at those primes less than 100,000,000.
let tests = d3.range(min, max, step).map(function(d) { return { n: d}; });

// Dispatcher.
worker.onmessage = function(event) {
  switch (event.data.type) {
    case "end": return ended(event.data);
  }
};

// Start first test.
worker.postMessage(tests.shift());

// Render analytics when computation is done.
function ended(data) {
  var yMax;

results.push(data);

// Progress bar tweening, remove when all tests have run.
  rect.transition().duration(200)
      .attr("width", results.length * width / numTrials)
      .on("end", function() {
        if (results.length === numTrials) {
          d3.select(this).remove();
        }
      });

yMax = d3.max(results, function(d) { return d.count; }) || Infinity;
  y2Max = d3.max(results, function(d) { return d.elapsed; }) || Infinity;

x.domain([0, results[results.length - 1].n]);

axis.call(d3.axisBottom(x)
              .tickFormat(d3.format("d")));

// Update y-axis domain.
  y.domain([0, yMax * 1.1]);
  line.y(function(d) { return +y(d.count); });
  y2.domain([0, y2Max * 1.1]);

path.datum(results)
      .attr("d", line)
      .attr("fill", "none")
      .attr("stroke-opacity", 0.2)
      .attr("stroke", "#000")
      .attr("stroke-width", "2px");

// Render the final graph.
  if (results.length === numTrials) {
    label = chart.selectAll(".label")
      .data(results);

chart.append("path")
      .datum(results)
        .attr("d", analyticLine)
        .attr("fill", "none")
        .attr("stroke-dasharray", "5, 5")
        .attr("stroke", "#eb9394")
        .attr("stroke-width", "2px");

label.enter().append("text")
        .attr("x", function(d) { return x(d.n); })
        .attr("y", function(d) { return +y(d.count); })
        .attr("text-anchor", "end")
        .attr("dx", -10)
        .attr("dy", -10)
        .attr("font-family", "helvetica")
        .attr("fill", "#000")
        .attr("fill-opacity", 0)
      .transition()
        .duration(400)
        .ease(d3.easeCircle)
        .attr("fill-opacity", 1)
        .text(function(d, i) { return d3.format(",")(d.count); });

circle = chart.selectAll("circle")
      .data(results);

circle.enter().append("circle")
      .attr("cx", function(d) { return x(d.n); })
      .attr("cy", function(d) { return +y(d.count); })
      .attr("r", 5)
      .attr("fill", "#000");

elapsed = chart.selectAll(".elapsed")
      .data(results);

elapsedCircle = chart.selectAll(".elapsedCircle")
      .data(results);

elapsedCircle.enter().append("circle")
      .attr("cx", function(d) { return x(d.n); })
      .attr("cy", function(d) { return +y2(d.elapsed); })
      .attr("stroke-width", "1px")
      .attr("stroke", "#aaa")
      .attr("r", 3)
      .attr("fill", "#ffbf87");

path.attr("stroke-opacity", 1);
  } else { // Run the next test.
    worker.postMessage(tests.shift());
  }
}

</script>

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