#COMPUTER ALGORITHMS FOR STATISTICAL CALCULATIONS CODE#

The source code for the RunningStat class follows: class RunningStat To check on the mean, variance, or standard deviation at any time, call the corresponding methods. int main()Īs new values arrive, say from a simulation, they enter the RunningStat class via the Push method.

#COMPUTER ALGORITHMS FOR STATISTICAL CALCULATIONS HOW TO#

This code sample shows how to use the class. The C++ class RunningStat given below uses this method to compute the mean, sample variance, and standard deviation of a stream of data. S k = S k-1 + ( x k – M k-1)*( x k – M k).įor 2 ≤ k ≤ n, the k th estimate of the variance is s 2 = S k/( k – 1). The algorithm is as follows.įor subsequent x‘s, use the recurrence formulas It’s even less obvious that the method has superior numerical properties, but it does. It is not obvious that the method is correct even in exact arithmetic. Most people are probably unaware that computing sample variance can be difficult until the first time they compute a standard deviation and get an exception for taking the square root of a negative number. Although this solution has been known for decades, not enough people know about it. Welford and is presented in Donald Knuth’s Art of Computer Programming, Vol 2, page 232, 3rd edition. This better way of computing variance goes back to a 1962 paper by B. The data do not need to be saved for a second pass. That is, the method computes the variance as the x‘s arrive one at a time.

Furthermore, the method computes a running variance. There is a way to compute variance that is more accurate and is guaranteed to always give positive results. See Comparing three methods of computing standard deviation for examples of just how bad the above formula can be. The loss of precision can be so bad that the expression above evaluates to a negative number even though variance is always positive. If the x‘s are large and the differences between them small, direct evaluation of the equation above would require computing a small number as the difference of two large numbers, a red flag for numerical computing. The most obvious way to compute variance then would be to have two sums: one to accumulate the sum of the x‘s and another to accumulate the sums of the squares of the x‘s. Mathematically, sample variance can be computed as follows. The most direct way of computing sample variance or standard deviation can have severe numerical problems.

Computer algorithms for statistical calculations