[PD] variance from mapping library

[Mathieu Bouchard]

On Thu, 19 Mar 2009, Oded Ben-Tal wrote:

> I am getting a negative number occasionally.

Ok, i isolated an example:

[metro 100]
  |
[100000]
  |
[variance 10]
  |
converges to -281.6

and then changing 100000 to 0 makes the result converge to -691.2.

actually, afaik, [variance] doesn't have a bug by itself. The bug is in 
[mean_n], which displays similar behaviour in default mode.

The bug is because of algebraic assumptions that don't work with floats. 
With real numbers, a+b-a-b = 0, but with floats, a+b-a-b is only 
guaranteed to be a "small" number, that is, less than 2^24 times smaller 
than abs(a)+abs(b), or something like that. But 100000*100000 = 
10000000000, and if you divide that by 2^24 = 16777216, you get about 596, 
which is an upper bound for the amount of error: so, the error is surely 
between -596 and +596.

Then [mean_n] boosts this error to the max by adding it all together. 
Statistically, that error could diverge.

So, the shortcut of keeping a total of a list of length N and only add the 
new element to it and subtract the oldest element from it, is not 
something that works with all floats. It's a trick that works with an int 
type, but with floats, it only works sometimes.

  _ _ __ ___ _____ ________ _____________ _____________________ ...
| Mathieu Bouchard - tél:+1.514.383.3801, Montréal, Québec