Kahan summation

From Rosetta Code
Revision as of 01:36, 11 December 2014 by rosettacode>Paddy3118 (New draft task and Python solution.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Kahan summation is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

The Kahan summation algorithm is a method of summing a series of numbers represented in a limited precision in a way that minimises the loss of precision in the result.

The task is to follow the previously linked Wikipedia articles algorithm and its worked example by:

  1. Do all arithmetic in decimal to a precision of six digits.
  2. Write a function/method/procedure/subroutine/... to perform Kahan summation on an ordered collection of numbers, (such as a list of numbers).
  3. Create the three numbers a, b, c equal to 10000.0, 3.14159, 2.71828 respectively.
  4. Show that the simple left-to-right summation, equivalent to (a + b) + c gives an answer of 10005.8
  5. Show that the Kahan function applied to the sequence of values a, b, c results in the more precise answer of 10005.9

Show all output on this page.

Python

<lang python>>>> from decimal import * >>> >>> getcontext().prec = 6 >>> >>> def kahansum(input):

   summ = c = 0
   for num in input:
       y = num - c
       t = summ + y
       c = (t - summ) - y
       summ = t
   return summ

>>> a, b, c = [Decimal(n) for n in '10000.0 3.14159 2.71828'.split()] >>> a, b, c (Decimal('10000.0'), Decimal('3.14159'), Decimal('2.71828')) >>> >>> (a + b) + c Decimal('10005.8') >>> kahansum([a, b, c]) Decimal('10005.9') >>> >>> # Lets try the simple summation with more precision for comparison >>> getcontext().prec = 20 >>> (a + b) + c Decimal('10005.85987') >>> </lang>