Math factoids for programmers

One-pass computation of Variance

The defining formula for sample variance (and, hence, standard deviation) requires two passes over the data: one to compute the average and a second to sum residuals.

double x[ N];     // given data array, N ≥ 2
double mean = sum( x) / N;
double varn = sum( square( x - mean)) / (N - 1);

The second pass is often a nuisance, especially when the data comes from a file or some function. A bit of algebra obscures the meaning, but gives a one-pass formula:

double sumXi = sum( x);         // compute both sums in one loop
double sumSq = sum( square(x));
double varn = (sumSq - square( sumXi)/N) / (N - 1);

Of course, you recall that standard deviation is just the square root of the variance.

Meaning of integer division

In several programming languages, integer division truncates toward zero. To remember how the signs are determined, consider the following:
Let

N = numerator
D = denominator
Q = quotient
R = remainder

then the integer divide and modulus operations

Q = N / D
R = N % D

are defined as the unique values that satisfy

N = Q * D + R

where

D ≠ 0	// if D = 0, any value of Q can satisfy the definition
abs(R) < abs(D)	// R is smaller than D, in magnitude
N * R > 0	// R has same sign as N
Q * (N * D) ≥ 0	// Q has same sign as N * D

In other words, when negative values are involved this modulus is not the same as a mathematical modulus, which is never negative.

Fore-warned is fore-armed.

Integer division code

Here is a good, brief, and accessible reference on software division.
Compare it with Ford & Topp page 340ff.
Demonstration code
Proposal and rationale for completely decimal arithmetic.

Return to my home page
updated $Id: mathFrag.html,v 1.4 2004/12/15 18:56:44 paulmcq Exp $