In the process of computer summation, the addition of a large number and a decimal will lead to truncation error due to the limited accuracy of floating point numbers. Therefore, in the construction of computing grid, we should try our best to avoid such a situation, and unify the computation in a relatively close order of magnitude. So, when you need to add a series of numbers, a good technique is to arrange the numbers from the largest to the smallest, and then add them up.

But if you have to make a sum of a large number and a decimal like this, the intuitive idea is to add the large number and the high part of the decimal and add the remaining decimal part as a separate “completion” part. The official name for this intuitive idea is Kahan summation.

Assume that the current floating point variable can hold 6 bits of value. So the theoretical value of 12345 added to 1.234 should be 12346.234. But because only six digits are currently stored, the correct theoretical value is truncated to 12346.2, which is an error of 0.034. When many such large numbers and decimals are added, truncation errors accumulate, leading to large deviations in the final calculation.


Kahan algorithm:

def KahanSum(input):var sum = 0.0var c = 0.0for i = 1 to input.length dovar y = input[i] - c// Initially, c is zero; then it compensates previous accuracy.var t = sum + y// low-order digits of y are lostc = (t - sum) - y// recover the low-order digits of y, withnegativesymbolsum = tnext ireturn sumCopy the code

In the pseudocode above, the variable C represents the complete compensation of the decimal, or, more strictly, the negative complete. With the continuous accumulation of the completion part, when these truncation errors accumulate to a certain magnitude, they will not be truncated when summing, so that the accuracy of the whole summing process can be relatively well controlled.

Below, a specific theoretical example is used to illustrate. For example, using 10000.0 + PI + e, we still assume that floating point variables can only hold 6 digits. At this point, the specific written summation formula should be: 10000.0 + 3.14159 + 2.71828, their theoretical result should be 10005.85987, approximately equal to 10005.9.

But because of the truncation error, the first summation of 10000.0 + 3.14159 only yields 10003.1. This result is then added to 2.71828 to get 10005.81828, which is truncated to 10005.8. There is a difference of 0.1.

Using Kahan summation, we run (remember, our floating-point variable holds six digits),


First sum:

y = 3.14159 - 0.00000

t = 10000.0 + 3.14159= 10003.14159= 10003.1

// low-order digits have lostc = (10003.1 - 10000.0) - 3.14159= 3.10000 - 3.14159= - (0415900.)

// recover the negative parts of compensation errorssum = 1003.1Copy the code


Second sum:

y = 2.71828 - (- 0415900.) =2.75985

// Add previous compensated parts to current small numbert = 10003.1 + 2.75987= 10005.85987= 10005.9

// As the low-order digits have been accumulated large enought, it wonCanceled by big Numberc = (10005.9-10003.1) -2.75987 = 2.80000-2.75987 =.040130sum = 10005.9Copy the code


So that’s the theoretical analysis. Here is another example of Python code that can be run for those interested in doing research. This is an example from Google’s chief scientist Vincent Vanhoucke’s deep Learning course at Udacity. The sum is: 10 to the ninth, plus 10 to the minus 6, repeat 10 to the sixth times, minus 10 to the ninth, which is 10 to the ninth plus 10 to the sixth times 10 to the minus 6, minus 10 to the ninth, which should be 1.


Python Code:

summ = 1000000000for indx in xrange(1000000):summ += 0.000001summ -= 1000000000print summCopy the code

After running, the result is 0.953674316406. As you can see, after 10 to the sixth summation, the cumulative amount of truncation error is quite significant.

If we use Kahan summation method to improve, we can get:


Python Code with Kahan method:

summ = 1000000000c = 0.0for indx in xrange(1000000):y = 0.000001 - ct = summ + yc = (t - summ) - ysumm = tsumm -= 1000000000print summCopy the code

When it runs, we are happy to see the correct result: 1.0.





If you like my article or share, please long press the qr code below to follow my wechat official account, thank you!

VIP appreciation area