Kahan Summation Algorithm Implementation in Java

In this section, we are going to learn about Kahan Summation Algorithm and implement it in the Java program. This algorithm is also known as compensated summation, it is generally used to reduce the numerical error in the result that is obtained by summation of finite-precision floating-point numbers. To understand it better let’s take an example.

public class KahanSummationAlgo {

  public static void main(String[] args) {
    double arr[]=new double[10];
    for(int i=0;i<10;i++) {
      arr[i]=0.2;
    }
    System.out.println(sum(arr));
    
  }
  public static double sum(double...n) {
    double sum=0;
    for(int i=0;i<10;i++) {
      sum+=n[i];
    }
    return sum;
  }
}

Expected Output

2.0

Actual Output

1.9999999999999998

Reason for this Error

  • Java supports two floating data types i.e float and double, with a single-precision of 32-bit and a double-precision of 64-bit format values and they are represented by SIGN FRACTION * 2EXP.
  • There are many floating-point numbers that can not be represented as a fraction of power of 2. For example,0.2=(0.0011001100110011001100110011…..)2. In this (0011) is repeating to infinite, this means that 0.2 cannot be represented exactly in binary format and thus it will get rounded at some point of time.
  • Repeated summation of such numbers leads to an unexpected value causing a difference between the actual and expected output resulting in an error.

Steps for understanding the program

  • Firstly, we will take up an accumulator variable,i.e sum.
  • Then, we will prepare a compensation variable i.e. x, to store low order lost bits.
  • Then, we will be iterating over the array’s elements and inside that loop, we will be performing some function.
    • So, we have taken up a variable y, its value will be equal to the element of the array because the compensation variable is approximately equal to zero.
    • After that, we have taken variable z, for summation purpose.
    • Further, we have updated x to cancel the high order part of y.
    • Lastly, update a sum for the next iteration.
  • Finally, return the sum.

Java program to implement Kahan Summation Algorithm

public class KahanSummationAlgo {

  public static void main(String[] args) {
    double arr[]=new double[10];
    for(int i=0;i<10;i++) {
      arr[i]=0.2;
    }
    System.out.println(KahanSummation(arr));
    
  }
  
  public static double KahanSummation(double...n) {
    double sum = 0.0; 
      
        // Variable to store the error 
        double x = 0.0; 
  
        // Loop to iterate over the array 
        for (int i=0;i<n.length;i++) { 
  
            double y = n[i] - x; 
            double z = sum + y;
            x = (z - sum) - y;
            sum = z; 
        }
    return sum; 
  
  }
}

Output

2.0

Leave a Reply

Your email address will not be published. Required fields are marked *