Last active
May 11, 2016 00:58
-
-
Save tab58/d230a60a3da2f2ccff428579d28a42b9 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var Benchmark = require('benchmark'); | |
var ndarray = require('ndarray'); | |
var sums = require('./numeric-sums.js'); | |
// var mean = 2; | |
var k = 0.1; | |
var mag = 100000; | |
function randomVector (n) { | |
var v = new Float64Array(n); | |
var i = n; | |
while (i--) { | |
v[i] = k; | |
} | |
return ndarray(v, [n]); | |
} | |
var n = 1000000; | |
var A = randomVector(n); | |
var suite = new Benchmark.Suite('Vector Summation'); | |
suite.add('Pairwise summation', function () { | |
var sum = sums.asumPair(A); | |
}) | |
.add('Kahan summation', function () { | |
var sum = sums.asumKahan(A); | |
}) | |
.add('Naive summation', function () { | |
var sum = sums.asumSerial(A); | |
}) | |
.on('cycle', function (event) { | |
console.log(String(event.target)); | |
}) | |
.on('complete', function () { | |
console.log(' '); | |
console.log('Fastest function is ' + this.filter('fastest').map('name') + '.'); | |
console.log(' '); | |
var serialSum = sums.asumSerial(A); | |
var pairSum = sums.asumPair(A); | |
var kahanSum = sums.asumKahan(A); | |
var trueSum = n / 10; | |
console.log('True value: ' + trueSum); | |
console.log('Serial error: ' + Math.abs(trueSum - serialSum)); | |
console.log('Pairwise error: ' + Math.abs(trueSum - pairSum)); | |
console.log('Kahan error: ' + Math.abs(trueSum - kahanSum)); | |
}) | |
.run({ | |
'async': false | |
}); |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function recursiveSum (x, start, steps) { | |
if (steps === 1) { | |
return x.data[x.offset + start * x.stride[0]]; | |
} | |
var n = Math.floor(steps / 2); | |
var m = steps - n; | |
return recursiveSum(x, start, n) + recursiveSum(x, start + n, m); | |
} | |
module.exports.asumSerial = function (x) { | |
var sum = 0; | |
var dx = x.data; | |
var px = x.offset; | |
var ox = x.stride[0]; | |
var i = x.shape[0]; | |
while (i--) { | |
sum += dx[px]; | |
px += ox; | |
} | |
return sum; | |
}; | |
module.exports.asumPair = function (x) { | |
return recursiveSum(x, x.offset, x.shape[0]); | |
}; | |
module.exports.asumKahan = function (x) { | |
var sum = 0.0; | |
var c = 0.0; | |
var i = x.shape[0]; | |
var y = 0; | |
var t = 0; | |
while (i--) { | |
y = x.get(i) - c; | |
t = sum + y; | |
c = (t - sum) - y; | |
sum = t; | |
} | |
return sum; | |
}; |
I have yet to come up with a really good test to see if it finds error. Originally, I was trying to make it vary with large and small numbers both positive and negative. Later, I summed up 0.1 n times naively and with Kahan summation. The thinking was that the truncation error would reveal more about what's happening (still not sure if it's a good test though). For n > 100000, the Kahan result started to diverge away from the true value, but it was more accurate than pairwise summation and much more accurate than simple summation.
See: https://github.com/rreusser/summation-algorithms
There's more to untangle here, but seems like maybe the answer is just that function calls aren't that bad, but they're not that great either.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
They always make a note that you must ensure the compiler doesn't optimize away the kahan summation. Can't imagine that's an issue here. Is the accuracy actually what's expected for kahan?