Rosetta Code

Kahan summation: Difference between revisions

Page Discussion

Kahan summation (view source)

Revision as of 23:46, 6 March 2024

6,129 bytes added ,  2 months ago
Grouping BASIC dialects
No edit summary
(Grouping BASIC dialects)
 
(7 intermediate revisions by 5 users not shown)
Line 284:
{{out}}<pre>Simple: 1.00000E +4 + 3.14159E +0 + 2.71828E +0 = 1.00058E +4
Kahan : 1.00000E +4 + 3.14159E +0 + 2.71828E +0 = 1.00059E +4</pre>
 
=={{header|Arturo}}==
 
<syntaxhighlight lang="arturo">kahanSum: function [inp][
c: 0
result: 0
loop inp 'val [
y: val - c
t: result + y
c: (t-result) - y
result: t
]
return result
]
 
eps: 1.0
while [1 <> 1 + eps]->
eps: eps / 2
 
a: 1.0
b: eps
c: neg eps
 
print ["Sum of 1.0, epsilon and -epsilon for epsilon:" eps]
 
print ["Is result equal to 1.0?"]
print ["- simple addition:" 1 = (a + b) + c]
print ["- using Kahan sum:" one? kahanSum @[a b c]]</syntaxhighlight>
 
{{out}}
 
<pre>Sum of 1.0, epsilon and -epsilon for epsilon: 1.110223024625157e-16
Is result equal to 1.0?
- simple addition: false
- using Kahan sum: true</pre>
 
=={{header|Asymptote}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="Asymptote">real a, b, c;
 
real KahanSum(real a, real b, real c) {
real sum = 0.0, y, t;
c = 0.0;
for (real i = 1; i <= a; ++i) {
y = i - c;
t = sum + y;
c = (t - sum) - y;
sum = t;
}
return sum;
}
 
real epsilon() {
real eps = 1;
while (1 + eps != 1) {
eps /= 2;
}
return eps;
}
 
a = 1.0;
b = epsilon();
c = -b;
 
real s = (a + b) + c;
real k = KahanSum(a, b, c);
real d = k - s;
write("Epsilon = " + string(b));
write("(a + b) + c = " + string(s));
write("Kahan sum = " + string(k));
write("Delta = " + string(d));</syntaxhighlight>
{{out}}
<pre>Epsilon = 1.11022302462516e-16
(a + b) + c = 1
Kahan sum = 1
Delta = 1.11022302462516e-16</pre>
 
=={{header|AWK}}==
Line 317 ⟶ 393:
(a+b)+c = 0.9999999999999999
Kahan sum = 1.0000000000000000
</pre>
 
=={{header|BASIC}}==
==={{header|FreeBASIC}}===
<syntaxhighlight lang="vbnet">Dim Shared As Double a, b, c
 
Function KahanSum (a As Double, b As Double, c As Double) As Double
Dim As Double sum = 0.0, i, y, t
c = 0.0
For i = 1 To a
y = i - c
t = sum + y
c = (t - sum) - y
sum = t
Next i
Return sum
End Function
 
Function epsilon() As Double
Dim As Double eps = 1
While (1 + eps <> 1)
eps /= 2
Wend
Return eps
End Function
 
a = 1.0
b = epsilon()
c = -b
 
Dim As Double s = (a + b) + c
Dim As Double k = KahanSum(a, b, c)
Dim As Double d = k - s
Print "Epsilon ="; b
Print "(a + b) + c ="; s
Print "Kahan sum ="; k
Print "Delta ="; d
Sleep</syntaxhighlight>
{{out}}
<pre>
Epsilon = 1.110223024625157e-016
(a + b) + c = 0.9999999999999999
Kahan sum = 1
Delta = 1.110223024625157e-016
</pre>
 
==={{header|FutureBasic}}===
FB has proper decimal numbers supporting mantissas and exponents. But conversion to and from floating point numbers (or strings) makes it easier and more readable for this task to be completed with doubles as are many other examples here.
<syntaxhighlight lang="futurebasic">
_elements = 3
 
local fn Epsilon as double
double eps = 1.0
while ( 1.0 + eps != 1.0 )
eps = eps / 2.0
wend
end fn = eps
 
 
local fn KahanSum( nums(_elements) as double, count as long ) as double
double sum = 0.0
double c = 0.0
double t, y
long i
for i = 0 to count - 1
y = nums(i) - c
t = sum + y
c = (t - sum) - y
sum = t
next
end fn = sum
 
 
local fn DoKahan
double a = 1.0
double b = fn Epsilon
double c = -b
double fa[_elements]
fa(0) = a : fa(1) = b : fa(2) = c
printf @"Epsilon = %.9e", b
printF @"(a + b) + c = %.9e", (a + b) + c
printf @"Kahan sum = %.9e", fn KahanSum( fa(0), 3 )
printf @"Delta = %.9e", fn KahanSum( fa(0), 3 ) - ((a + b) + c)
end fn
 
fn DoKahan
 
HandleEvents</syntaxhighlight>
{{output}}
<pre>
Epsilon = 1.110223025e-16
(a + b) + c = 1.000000000e+00
Kahan sum = 1.000000000e+00
Delta = 1.110223025e-16
</pre>
 
==={{header|Gambas}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="vbnet">Public a As Float
Public b As Float
Public c As Float
 
Function KahanSum(a As Float, b As Float, c As Float) As Float
 
Dim sum As Float = 0.0
Dim i As Float, y As Float, t As Float
 
c = 0.0
For i = 1 To a
y = i - c
t = sum + y
c = (t - sum) - y
sum = t
Next
Return sum
 
End Function
 
Function epsilon() As Float
 
Dim eps As Float = 1
While (1 + eps <> 1)
eps /= 2
Wend
Return eps
 
End Function
 
Public Sub Main()
a = 1.0
b = epsilon()
c = -b
Dim s As Float = (a + b) + c
Dim k As Float = KahanSum(a, b, c)
Dim d As Float = k - s
Print "Epsilon = "; b
Print "(a + b) + c = "; s
Print "Kahan sum = "; k
Print "Delta = "; d
End</syntaxhighlight>
{{out}}
<pre>Epsilon = 1,11022302462516E-16
(a + b) + c = 1
Kahan sum = 1
Delta = 1,11022302462516E-16</pre>
 
==={{header|True BASIC}}===
<syntaxhighlight lang="qbasic">
FUNCTION epsilon
LET eps = 1
DO while (1+eps <> 1)
LET eps = eps/2
LOOP
LET epsilon = eps
END FUNCTION
 
FUNCTION kahansum(a, b, c)
LET sum = 0
LET c = 0
FOR i = 1 to a
LET y = i-c
LET t = sum+y
LET c = (t-sum)-y
LET sum = t
NEXT i
LET kahansum = sum
END FUNCTION
 
LET a = 1
LET b = epsilon
LET c = -b
LET s = (a+b)+c
LET k = kahansum(a, b, c)
LET d = k-s
PRINT "Epsilon ="; b
PRINT "(a + b) + c ="; s
PRINT "Kahan sum ="; k
PRINT "Delta ="; d
END</syntaxhighlight>
{{out}}
<pre>Epsilon = 1.110223e-16
(a + b) + c = 1.
Kahan sum = 1
Delta = 1.110223e-16</pre>
 
==={{header|Visual Basic .NET}}===
{{trans|C#}}
<syntaxhighlight lang="vbnet">Module Module1
 
Function KahanSum(ParamArray fa As Single()) As Single
Dim sum = 0.0F
Dim c = 0.0F
For Each f In fa
Dim y = f - c
Dim t = sum + y
c = (t - sum) - y
sum = t
Next
Return sum
End Function
 
Function Epsilon() As Single
Dim eps = 1.0F
While 1.0F + eps <> 1.0F
eps /= 2.0F
End While
Return eps
End Function
 
Sub Main()
Dim a = 1.0F
Dim b = Epsilon()
Dim c = -b
Console.WriteLine("Epsilon = {0}", b)
Console.WriteLine("(a + b) + c = {0}", (a + b) + c)
Console.WriteLine("Kahan sum = {0}", KahanSum(a, b, c))
End Sub
 
End Module</syntaxhighlight>
{{out}}
<pre>Epsilon = 1.110223E-16
(a + b) + c = 1
Kahan sum = 1</pre>
 
==={{header|Yabasic}}===
{{trans|FreeBASIC}}
<syntaxhighlight lang="vbnet">a = 1.0
b = epsilon()
c = -b
 
s = (a + b) + c
k = KahanSum(a, b, c)
d = k - s
print "Epsilon = ", b
print "(a + b) + c = ", s
print "Kahan sum = ", k
print "Delta = ", d
end
 
sub KahanSum (a, b, c)
sum = 0.0
c = 0.0
for i = 1 to a
y = i - c
t = sum + y
c = (t - sum) - y
sum = t
next i
return sum
end sub
 
sub epsilon()
eps = 1
while (1 + eps <> 1)
eps = eps / 2.0
wend
return eps
end sub</syntaxhighlight>
{{out}}
<pre>
Epsilon = 1.11022e-16
(a + b) + c = 1
Kahan sum = 1
Delta = 1.11022e-16
</pre>
 
Line 510 ⟶ 856:
(a + b) + c = 1.00000000
Kahan sum = 1.00000000</pre>
 
=={{header|Dart}}==
{{trans|C++}}
<syntaxhighlight lang="dart">double epsilon() {
double eps = 1.0;
while (1.0 + eps != 1.0) {
eps /= 2.0;
}
return eps;
}
 
double kahanSum(List<double> nums) {
double sum = 0.0;
double c = 0.0;
for (var num in nums) {
double y = num - c;
double t = sum + y;
c = (t - sum) - y;
sum = t;
}
return sum;
}
 
void main() {
double a = 1.0;
double b = epsilon();
double c = -b;
 
print("Epsilon = $b");
print("(a + b) + c = ${(a + b) + c}");
print("Kahan sum = ${kahanSum([a, b, c])}");
print("Delta = ${kahanSum([a, b, c]) - (a + b) + c}");
}</syntaxhighlight>
{{out}}
<pre>Epsilon = 1.1102230246251565e-16
(a + b) + c = 0.9999999999999999
Kahan sum = 1
Delta = -1.1102230246251565e-16</pre>
 
=={{header|EchoLisp}}==
Line 1,111 ⟶ 1,495:
 
And this time, the compensated summation calculation comes out with one while the successive additions via a loop do not, as required.
 
 
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">Dim Shared As Double a, b, c
 
Function KahanSum (a As Double, b As Double, c As Double) As Double
Dim As Double sum = 0.0, i, y, t
c = 0.0
For i = 1 To a
y = i - c
t = sum + y
c = (t - sum) - y
sum = t
Next i
Return sum
End Function
 
Function epsilon() As Double
Dim As Double eps = 1
While (1 + eps <> 1)
eps /= 2
Wend
Return eps
End Function
 
a = 1.0
b = epsilon()
c = -b
 
Dim As Double s = (a + b) + c
Dim As Double k = KahanSum(a, b, c)
Dim As Double d = k - s
Print "Epsilon ="; b
Print "(a + b) + c ="; s
Print "Kahan sum ="; k
Print "Delta ="; d
Sleep</syntaxhighlight>
{{out}}
<pre>
Epsilon = 1.110223024625157e-016
(a + b) + c = 0.9999999999999999
Kahan sum = 1
Delta = 1.110223024625157e-016
</pre>
 
 
=={{header|FutureBasic}}==
FB has proper decimal numbers supporting mantissas and exponents. But conversion to and from floating point numbers (or strings) makes it easier and more readable for this task to be completed with doubles as are many other examples here.
<syntaxhighlight lang="futurebasic">
_elements = 3
 
local fn Epsilon as double
double eps = 1.0
while ( 1.0 + eps != 1.0 )
eps = eps / 2.0
wend
end fn = eps
 
 
local fn KahanSum( nums(_elements) as double, count as long ) as double
double sum = 0.0
double c = 0.0
double t, y
long i
for i = 0 to count - 1
y = nums(i) - c
t = sum + y
c = (t - sum) - y
sum = t
next
end fn = sum
 
 
local fn DoKahan
double a = 1.0
double b = fn Epsilon
double c = -b
double fa[_elements]
fa(0) = a : fa(1) = b : fa(2) = c
printf @"Epsilon = %.9e", b
printF @"(a + b) + c = %.9e", (a + b) + c
printf @"Kahan sum = %.9e", fn KahanSum( fa(0), 3 )
printf @"Delta = %.9e", fn KahanSum( fa(0), 3 ) - ((a + b) + c)
end fn
 
fn DoKahan
 
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
Epsilon = 1.110223025e-16
(a + b) + c = 1.000000000e+00
Kahan sum = 1.000000000e+00
Delta = 1.110223025e-16
</pre>
 
 
=={{header|Go}}==
Line 2,337 ⟶ 2,621:
simple summation of a,b,c = 1.0000000000000000000000000000001
Kahan summation of a,b,c = 1.0000000000000000000000000000000
</pre>
 
=={{header|RPL}}==
{| class="wikitable" ≪
! RPL code
! Comment
|-
|
≪ → input
≪ 0 0
1 input SIZE '''FOR''' j
input j GET SWAP -
DUP2 +
DUP 4 ROLL - ROT -
'''NEXT''' DROP
≫ ≫ '<span style="color:blue">∑KAHAN</span>' STO
≪ .1
'''WHILE''' 1 OVER + 1 ≠ '''REPEAT''' 10 / '''END'''
→ eps
≪ 1 eps + eps NEG +
1 eps eps NEG →LIST <span style="color:blue">∑KAHAN</span>
≫ ≫ '<span style="color:blue">TASK</span>' STO
|
<span style="color:blue">∑KAHAN</span> ''( { a b .. n } → a+b+..+n ) ''
var sum = 0.0, c = 0.0
for i = 1 to input.length do
var y = input[i] - c
var t = sum + y
c = (t - sum) - y
sum = t
next i ; return sum
Calculate epsilon
Display 1 + epsilon - epsilon
Display KAHAN( { 1 epsilon -epsilon })
|}
{{out}}
<pre>
2: 0.999999999999
1: 1
</pre>
 
Line 2,563 ⟶ 2,893:
With "down" and "floor" rounding, the Kahan sum is too low (10005.8), but any other rounding makes it correct (10005.9).
The Associative largest-to-smallest sum is never correct: "up" and "ceiling" rounding make it too high, while the rest make it low.
 
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<syntaxhighlight lang="vbnet">Module Module1
 
Function KahanSum(ParamArray fa As Single()) As Single
Dim sum = 0.0F
Dim c = 0.0F
For Each f In fa
Dim y = f - c
Dim t = sum + y
c = (t - sum) - y
sum = t
Next
Return sum
End Function
 
Function Epsilon() As Single
Dim eps = 1.0F
While 1.0F + eps <> 1.0F
eps /= 2.0F
End While
Return eps
End Function
 
Sub Main()
Dim a = 1.0F
Dim b = Epsilon()
Dim c = -b
Console.WriteLine("Epsilon = {0}", b)
Console.WriteLine("(a + b) + c = {0}", (a + b) + c)
Console.WriteLine("Kahan sum = {0}", KahanSum(a, b, c))
End Sub
 
End Module</syntaxhighlight>
{{out}}
<pre>Epsilon = 1.110223E-16
(a + b) + c = 1
Kahan sum = 1</pre>
 
=={{header|V (Vlang)}}==
Line 2,646 ⟶ 2,937:
=={{header|Wren}}==
Wren's only 'native' number type (Num) is double-precision floating point and so the alternative task is performed. Although it appears that there is no difference between the left associative sum and Kahan summation, there is in fact a difference of epsilon but the accuracy of System.print (14 significant figures) is insufficient to indicate this directly.
<syntaxhighlight lang="ecmascriptwren">var kahanSum = Fn.new { |a|
var sum = 0
var c = 0
Line 2,684 ⟶ 2,975:
</pre>
 
=={{header|XPL0}}==
{{trans|C}}
XPL0's only 'native' floating point type (real) is double-precision, so
the alternative task is performed. The normal output shows no difference
because of rounding, so the hex output is used to show it.
<syntaxhighlight lang "XPL0">include xpllib; \for Print
 
func real KahanSum(Nums, Count);
=={{header|Yabasic}}==
real Nums; int Count;
{{trans|FreeBASIC}}
real Sum, C, T, Y;
<syntaxhighlight lang="yabasic">sub KahanSum (a, b, c)
int I;
sum = 0.0
c [Sum:= 0.0;
C:= 0.0;
for i = 1 to a
for I:= 0 to Count-1 do
y = i - c
t [Y:= sumNums(I) +- yC;
c T:= (t - sum)Sum -+ yY;
C:= (T - Sum) sum =- tY;
nextSum:= iT;
return sum];
return Sum;
end sub
];
 
func real Epsilon;
sub epsilon()
real Eps;
eps = 1
[Eps:= 1.0;
while (1 + eps <> 1)
while 1.0 + Eps # 1.0 do
eps = eps / 2.0
wendEps:= Eps/2.0;
return epsEps;
];
end sub
 
real A, B, C, FA(3), D, K;
a = 1.0
[A:= 1.0; B:= Epsilon; C:= -B;
b = epsilon()
FA(0):= A; FA(1):= B; FA(2):= C;
c = -b
Print("Epsilon = %0.16f\n", B);
 
s D:= (aA + bB) + cC;
Print("(A + B) + C = %0.16f\n", D);
k = KahanSum(a, b, c)
K:= KahanSum(FA, 3);
d = k - s
print Print("Epsilon Kahan sum = %0.16f\n", bK);
print Print("(aA + bB) + cC = %x %x\n", sD);
print Print("Kahan sum = %x %x\n", kK);
]</syntaxhighlight>
print "Delta = ", d
end</syntaxhighlight>
{{out}}
<pre>
Epsilon = 1.11022e1102230246251600E-16016
(aA + bB) + cC = 1.0000000000000000E+000
Kahan sum = 1.0000000000000000E+000
Delta(A + B) + C = =FFFFFFFF 1.11022e-163FEFFFFF
Kahan sum = 00000000 3FF00000
</pre>
 
 
=={{header|zkl}}==
Jjuanhdez
2,122

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/333976...361311"