On 12/01/2013, at 8:38 AM, srean wrote:
> Though operation on floats are not associative (neither distributive),
> pretending that asociativity holds
The laws that hold depend on context. Which why you need a numerical
analyst to check numerical algorithms.
Interesting the Kahan algorithm in pseudocode is:
function KahanSum(input)
var sum = 0.0
var c = 0.0 //A running compensation for lost low-order bits.
for i = 1 to input.length do
y = input[i] - c //So far, so good: c is zero.
t = sum + y //Alas, sum is big, y small, so low-order digits of
y are lost.
c = (t - sum) - y //(t - sum) recovers the high-order part of y;
subtracting y recovers -(low part of y)
sum = t //Algebraically, c should always be zero. Beware
eagerly optimising compilers!
//Next time around, the lost low part will be added to y in a fresh
attempt.
return sum
And the Felix code is:
fun KahanSum(input: 1 -> opt[double]) = {
var sum = 0.0;
var c = 0.0; //A running compensation for lost low-order bits.
for v in input do
var y = v - c; //So far, so good: c is zero.
var t = sum + y; //Alas, sum is big, y small, so low-order
digits of y are lost.
c = (t - sum) - y; //(t - sum) recovers the high-order part of y;
subtracting y recovers -(low part of y)
sum = t; //Algebraically, c should always be zero. Beware
eagerly optimising compilers!
//Next time around, the lost low part will be added to y in a fresh
attempt.
done
return sum;
}
var inp = 1.0, 2.0, 3.0;
println$ KahanSum inp.iterator;
~/felix>flx yy
6
The iterator version is more general than the array version in Wikipedia.
[Although undoubtedly much slower :]
Of course this algorithm is actually no good in general:
it only works if the values to be added are dense around
a point, spread out not much more than a float precision.
Otherwise, the error term c itself suffers the same fate as the sum.
--
john skaller
[email protected]
http://felix-lang.org
------------------------------------------------------------------------------
Master HTML5, CSS3, ASP.NET, MVC, AJAX, Knockout.js, Web API and
much more. Get web development skills now with LearnDevNow -
350+ hours of step-by-step video tutorials by Microsoft MVPs and experts.
SALE $99.99 this month only -- learn more at:
http://p.sf.net/sfu/learnmore_122812
_______________________________________________
Felix-language mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/felix-language
