Anonymous user
Talk:Kahan summation: Difference between revisions
no edit summary
(→Task 2: ULP) |
No edit summary |
||
Line 1:
==Task - The problem is badly formulated==
Rounding errors do not occur because we use a certain number of digits after the decimal point. The source of the errors is the floating point representation of decimal fractions. As you can see, when using fixed point representation, there are no rounding errors.
<lang C>
/*
* RosettaCode: Kahan summation, C89 (MS Visual Studio 2010)
*
* C language has no fixed decimal fraction type. Nevertheless to obtain
* "six-digits precision" we can use ordinary fractions with fixed denominator.
*/
#include <stdio.h>
#define DECIMAL_FRACTION long int
#define DENOMINATOR 1000000L
#define DECIMAL_TO_FIXED(WHOLE,FRACTIONAL) (WHOLE*DENOMINATOR+FRACTIONAL)
#define FIXED_TO_WHOLE(VALUE) (VALUE / DENOMINATOR)
#define FIXED_TO_FRACT(VALUE) (VALUE % DENOMINATOR)
int main(void)
{
DECIMAL_FRACTION a = DECIMAL_TO_FIXED(10000,0);
DECIMAL_FRACTION b = DECIMAL_TO_FIXED(3,14159);
DECIMAL_FRACTION c = DECIMAL_TO_FIXED(2,71828);
DECIMAL_FRACTION leftSum;
DECIMAL_FRACTION rightSum;
DECIMAL_FRACTION kahanSum;
leftSum = a;
leftSum += b;
leftSum += c;
rightSum = c;
rightSum += b;
rightSum += a;
{
/*
* Actually we sum only a+b+c with an un-rolled implementation
* of Kahan algorithm. KISS
*/
DECIMAL_FRACTION correction = 0;
DECIMAL_FRACTION inputMinusCorrection = 0;
DECIMAL_FRACTION updatedSum = 0;
kahanSum = a;
inputMinusCorrection = b - correction;
updatedSum = kahanSum + inputMinusCorrection;
correction = updatedSum - kahanSum;
correction -= inputMinusCorrection;
kahanSum = updatedSum;
inputMinusCorrection = c - correction;
updatedSum = kahanSum + inputMinusCorrection;
correction = updatedSum - kahanSum;
correction -= inputMinusCorrection;
kahanSum = updatedSum;
}
#define PRINT(S,V) printf(S##" = %d.%d\n", FIXED_TO_WHOLE(V), FIXED_TO_FRACT(V))
PRINT("a", a);
PRINT("b", b);
PRINT("c", c);
putchar('\n');
PRINT(" (a+b)+c", leftSum);
PRINT(" a+(b+c)", rightSum);
PRINT("Kahan sum", kahanSum);
if ( leftSum == kahanSum && rightSum == kahanSum )
puts("\nC can compute on fixed point numbers without round-off errors");
getchar();
return 0;
}
</lang>
{{Out}}
<pre>
a = 1410.65408
b = 3.14159
c = 2.71828
(a+b)+c = 1415.151395
a+(b+c) = 1415.151395
Kahan sum = 1415.151395
C can compute on fixed point numbers without round-off errors
</pre>
==Task==
The idea of showing the Kahan summation on Rosettacode is good, but the Task is not good yet. I suggest to remove the requirements of using a Decimal module and make it optional. So many languages can use normal floating point values. I also suggest to increase the number of input values and the number of their digits, to better show why the Kahan summation is useful.
| |||