Skip to content

Instantly share code, notes, and snippets.

@majido
Created July 18, 2017 21:45
Show Gist options
  • Save majido/9b01aa248551072dc4c132930b245e9a to your computer and use it in GitHub Desktop.
Save majido/9b01aa248551072dc4c132930b245e9a to your computer and use it in GitHub Desktop.
Estimate minimum clock resolution
// Finds minimum resolution Δ given a set of samples which are known to be in the form of N*Δ.
function computeGCD(a, b) {
if (!Number.isInteger(a) || !Number.isInteger(b)) {
throw new Error('Parameters in function gcd must be integer numbers');
}
var r;
while (b != 0) {
r = a % b;
a = b;
b = r;
}
return (a < 0) ? -a : a;
}
function getSample() {
const t1 = new MouseEvent('test1').timeStamp;
const t2 = new MouseEvent('test2').timeStamp;
// Add 100 to below to emulate a sampler with minimum fixed cost.
return Math.round((t2 - t1) * 1000);
}
// Finds minimum resolution Δ given a set of samples which are known to be in the form of N*Δ.
function estimateMinimumResolution() {
var min, gcd;
for (var i = 0; i < 1e3; ++i) {
let sample = getSample();
if (sample == 0) continue; // ignore zero samples
// Assuming there is at least one sample with N=1, then taking minimum of our sample is a good
// estimate. This breaks if for any reason this assumption is incorrect for example if event
// construction cost is always larger than the minimum resolution Δ. In this case gcd is a
// better estimator.
min = min ? Math.min(min, sample) : sample;
// Compute gCD of our samples which can estimate Δ.
gcd = gcd ? computeGCD(gcd, sample) : sample;
}
console.log("Estimate using Min: ", min, " Estimate using GCD:", gcd);
return gcd;
}
estimateMinimumResolution();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment