Recurrence relation of averaging

Let's form a such problem - Can averaging be done without storing an intermediate total value ?

YES. One just needs to re-write averaging formula as a recurrence relation :

avg_rec.png

PHP implementation of averaging 1 000 000 random numbers in [0..1] interval:

function average_standard($arr) {
    return array_sum($arr)/count($arr);
} 

function average_recursive($arr) {
    $avg = 0;
    $n = 0;
    foreach ($arr as $val) {
        $n++;
        $avg = ($avg*($n-1)+$val)/$n;
    }
    return $avg;
}

function random_array($elements) {
    $arr = [];
    for ($i=0; $i < $elements ; $i++) { 
        $arr[] = mt_rand() / mt_getrandmax();
    }
    return $arr;
}

// TEST
$rnd_arr = random_array(1000000);
$std = average_standard($rnd_arr);
$rec = average_recursive($rnd_arr);
$err = abs($std - $rec);
printf("avg :<br>&emsp;std %.20f<br>&emsp;rec %.20f<br>&emsp;err %.20f", $std, $rec,$err);

Running this you'll get something like this on screen :

avg :

std 0.50024052683893582838

rec 0.50024052683895403604 

err 0.00000000000001820766

As you see there is a small difference between standard approach and a recursive one. It's probably because in recursive version here goes conversion between small and big numbers (totals must be deduced from average) so some sort of rounding takes place. But if you don't need high accuracy and your goal is just to save stack / ram space skipping totals variable storage / calculation - it's the way to go.

Just keep in mind that recurrence relations are a powerful tool.

No Comments Yet