variance_average.c

/* Iterative average/Iterative centroid computation from:
https://blog.demofox.org/2016/08/23/incremental-averaging/ by Alan Wolfe and
http://realtimecollisiondetection.net/blog/?p=48 by Christer Ericson
Example:
    int n = 0;
    float avg = 0;
    avg = avg_add(avg, n++, rand());
    avg = avg_add(avg, n++, rand());
*/
static float
avg_add(float o, int cnt, float v)
{
    float n = (float)(cnt + 1);
    return o * ((float)cnt / n) + v / n;
}

/* On-line variance calculation algorithm (Knuth / Welford)
 * http://en.wikipedia.org/wiki/Algorithms_for_calculating_variance */
struct variance {
    int n;
    float mean;
    float M2;
};
static struct variance
variance_begin(void)
{
    struct variance v;
    v.n = 0; v.mean = v.M2 = 0;
    return v;
}
static void
variance_add(struct variance *v, float x)
{
    v->n++;
    {float delta = x - v->mean;
    v->mean = v->mean + delta / (float)v->n;
    v->M2 = v->M2 + delta * (x - v->mean);}
}
static float
variance_end(const struct variance *v)
{
    float variance;
    if (v->n < 2) return 0.0f;
    variance = v->M2 / (float)(v->n - 1);
    return variance;
}