Kahan Summation Algorithm implementation with python

In numerical analysis, Kahan's algorithm is used to find the sum of all the items in a given list without compromising on the precision. I will first explain the basics of why this algorithm has importance even if you are using python.


To get a hands-on experience, you can open your python interpreter and type the commands along the way.

>>> alist = [0.1]*10
>>> alist
[0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1]
>>> 

As you can see we have created a list with 10 items. For your proof, I have also printed the list alist. There are only 10 0.1's and nothing else. Now see the magic

>>> sum(alist)
0.9999999999999999
>>> 

I have used the inbuilt sum function to find the sum of all the elements in the given list. The expected value is 1.0, but we get 0.9999999999999999, which is approximately equal to 1.0 but not exactly equal to 1.0. Okay if you are not convinced with the above, I sum each and every element separately. Here it goes:

>>> 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1
0.9999999999999999

But why is this happening? This is because of the round off errors that computers make. To eliminate these kinds of rounding off errors that computers make we can use the Kahan's Algorithm. But remember that if precision is not of utmost importance for you then I suggest you use direct summation because Kahan's algorithm will considerably add some time in your performance.

Kahan's Algorithm implementation can be seen below

Program

The program is very small and I think you should plug in some numbers to understand.
Now let us check how correct this program is. We will use the above function and check if we are getting the correct answer.

>>> KahanSum([0.1]*10)
1.0
>>> sum([0.1]*10) == 1.0
False
>>> KahanSum([0.1]*10) == 1.0
True
>>> 

And of course, we are getting the correct answer. I think you are convinced about the use of Kahan's algorithm in programming.

If you want to have accurate summation for a given lists, then don't worry you don't have to write this function. You can import the inbuilt fsum function and this will calculate the summation accurately.

>>> from math import fsum
>>> fsum([0.1]*10)
1.0
>>> fsum([0.1]*10) == 1.0
True
>>> 

To know about the Kahan's algorithm you can see the Wikipedia Kahan Summation algorithm.

As always you can download the files from Github Gist kahan_algorithm.py

If you have any doubt or haven't understood anything then comment in the comment box below and I will be glad to help you.

If you have found any typo please let me know so that I can correct it as soon as possible,

If you have any suggestions or if you have any feedback then please do comment in the comment box below. I will be very happy to see your message.

You can also contact me.

Thank you. Have a nice day😃.