Skip to content

Instantly share code, notes, and snippets.

@bmershon
Last active February 19, 2017 13:24
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save bmershon/e15a65d5599870a860de734f2ef09cde to your computer and use it in GitHub Desktop.
Number of Primes
license: MIT
border: no
height: 550

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>
// Note, the elapsed time attempts to avoid counting time spent allocating
// memory for the sieve.
var startTime,
endTime;
onmessage = function(event) {
var n = event.data.n,
computedPrimes = primes(n);
postMessage({
"type": "end",
"n": n,
"count": computedPrimes.length,
"elapsed": endTime - startTime
});
}
// Returns an array containing the primes less than or equal to n.
function primes(n) {
var sieve = new Array(Math.ceil(index(n))),
reduced;
sieve.fill(true);
sift(sieve);
reduced = sieve.reduce(function(accumulator, current, i, array) {
if (current) accumulator.push(value(i));
return accumulator;
}, [2]);
endTime = Date.now();
return reduced;
}
function sift(sieve) {
var i = 0,
squaredIndex = 3,
factor = 3;
// Begin timing after the sieve has been allocated.
startTime = Date.now();
while (squaredIndex < sieve.length) {
if (sieve[i]) {
markSieve(sieve, squaredIndex, value(i));
} // else all multiples of this factor have been crossed out
i++;
squaredIndex += factor;
factor += 2; // e.g., 3 -> 5 -> 7 -> 9
squaredIndex += factor; // squredIndex += factor(i) + factor(i + 1)
}
return sieve;
}
// Mark boolean sieve false for all multiples of the
// given factor.
function markSieve(sieve, begin, factor) {
var i, n;
for (i = begin, n = sieve.length; i < n - factor; i += factor) {
sieve[i] = false;
}
}
// Returns the value of a number in the sieve containing only
// odd numbers and starting at 3.
function value(i) {
return i + i + 3;
}
// Returns the index for a value in the sieve containing only
// odd numbers and starting at 3.
function index(v) {
return (v - 3) / 2;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment