2
$\begingroup$

I know that calculating the new average $a_{new}$ from the old average $a_{old}$ can be done in the following way (for uniform weights):

Suppose the old average is based on $n$ elements. The old total is then $t_{old}=a_{old}\cdot n$. The new total is $t_{new}=t_{old}+x$. The new average is $a_{new}=\frac{t_{new}}{n+1}=\frac{a_{old}\cdot n + x}{n+1}$. (4 flops)

However, I found another way of calculating the new average $a_{new}$ from the old average $a_{old}$. I tried it numerical for some example, which is correct, but how can I prove it for all cases? My method is the following (also suitable for weights that are not uniform):

  • Calculate the difference $d$ between the old average $a_{old}$ and the new element $x$ with $d=x-a_{old}$
  • Multiply it with the weight $w$ of the new element $x$, so $q=d\cdot w$
  • Add it to the old average $a_{old}$, so $a_{new}=a_{old}+q=a_{old}+(x-a_{old})\cdot w=x\cdot w + (1-w)\cdot a_{old}$.

The calculation $a_{new}=a_{old}+(x-a_{old})\cdot w$ has 3 flops

Which method is more efficient in terms of computing time? Or are they equally efficient?

$\endgroup$
  • $\begingroup$ What is the weight? If it is $w=\frac{1}{n+1}$, then both methods you explain are equivalent (and equally efficient computationally, as none of them contains any loop). If by "weight" you mean something else, then they are not equivalent. $\endgroup$ – Anna SdTC Dec 15 '17 at 18:35
  • $\begingroup$ $w$ is for example how much a certain item at school counts for the final mark, which is often known beforehand and not need to be calculated $\endgroup$ – Faceb Faceb Dec 15 '17 at 18:38
  • $\begingroup$ All flops are not equal. Division is often nastier than all the others. $\endgroup$ – mathreadler Dec 15 '17 at 19:21
  • $\begingroup$ If $w$ is some constant divided by an integer power of two you can make the second approach quite a bit faster. Yes 3 flops if we already know $w$, but are you sure $w$ will be constant? $\endgroup$ – mathreadler Dec 15 '17 at 19:30
1
$\begingroup$

\begin{align}a_{new}&=\frac{t_{new}}{n+1}\\&=\frac{a_{old}\cdot n + x}{n+1}\\ &= \frac{n}{n+1}a_{old}+\frac{1}{n+1}x\end{align}

The old formula requires one multiplication, two additions, and one division.

We have to set $w = \frac{1}{n+1}$ for the formula to be equal $a_{new}=a_{old}+q=a_{old}+(x-a_{old})\cdot w=x\cdot w + (1-w)\cdot a_{old}$

The new formula requires one subtraction, one division, one multiplication, and one addtion. The division is due to $\frac{1}{n+1}$.

Edit: consider data $x_1, \ldots, a_{n+1}$ with weight $w_1, \ldots, w_{n+1}$ \begin{align} a_{new} &= \frac{\sum_{i=1}^{n+1} w_ix_i}{\sum_{i=1}^{n+1} w_i} \\ &= \frac{\sum_{i=1}^{n} w_ix_i}{\sum_{i=1}^{n+1} w_i} + \frac{w_{n+1}x_{n+1}}{\sum_{i=1}^{n+1}w_i}\\ &= \frac{\sum_{i=1}^{n} w_ix_i}{\sum_{i=1}^{n} w_i} \left( \frac{\sum_{i=1}^{n} w_i}{\sum_{i=1}^{n+1} w_i}\right) + \frac{w_{n+1}x_{n+1}}{\sum_{i=1}^{n+1}w_i}\\ &= a_{old}\left( \frac{\sum_{i=1}^{n} w_i}{\sum_{i=1}^{n+1} w_i}\right) + \frac{w_{n+1}(x_{n+1}-a_{old}+a_{old)}}{\sum_{i=1}^{n+1}w_i} \\ &= a_{old} + \frac{w_{n+1}(x_{n+1}-a_{old})}{\sum_{i=1}^{n+1}w_i} \end{align}

$\endgroup$
  • $\begingroup$ But the formula $a_{new}=a_{old}+(x-a_{old})\cdot w$ requires 3 flops right? (one addition, one subtraction and one multiplication) $\endgroup$ – Faceb Faceb Dec 15 '17 at 18:36
  • $\begingroup$ what about computation of the weight? $\endgroup$ – Siong Thye Goh Dec 15 '17 at 18:38
  • $\begingroup$ the weight is known beforehand, for example how much certain item at school counts for the final mark and therefore does not need to be calculated $\endgroup$ – Faceb Faceb Dec 15 '17 at 18:39
  • $\begingroup$ $n+1$ is also known before hand for the first formula., you save one addition there. $\endgroup$ – Siong Thye Goh Dec 15 '17 at 18:40
  • 1
    $\begingroup$ the first formula assumes uniform weight, which is why you can just sum them up and then divide by total number. $\endgroup$ – Siong Thye Goh Dec 15 '17 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.