If using the following formula to incrementally calculate average value: $m_n = m_{n-1} + \frac{a_{n}-m_{n-1}}{n}$ And the number of decimal places to where you can save $m_n$ is limited to $d$ decimal digits, how many $n$ values can you use to incrementally calculate average before the rounding error becomes larger than $10^{-p}$, if the value of $a_n$ is always exactly $p$ decimal digit precise?
How many decimal places are needed for incremental average calculation?
-
0@JernejJerin If you are satisfied with the answers, you might consider accepting them, else you might want to indicate what more information you want. – 2012-11-03
2 Answers
You have used $base-10$ notation and hence, I am doing the analysis in the same, but to do the actual analysis for a computer, I believe, it would be best for you to do it using the $base-2$.
Since we can have only $d$ decimal places, in every division which is not done by $10$ and the odd case where the mantissa when represented without the point and hence as an integer is a multiple of the divisor, you introduce an error of $10^{-d}$ at every stage (for binary computers, you would lose $2^{-d}$). This is only for this particular formula, since here divisor is integer and hence, no error comes from the divisor.
Also, suppose at some stage $m_{k} = c_{k} \times 10^{q_{k}}$ and $a_{k} = d_{k} \times 10^{r_{k}}$, then adding or subtracting them introduces an error of $10^{q_{k}-r_{k}-d}$ assuming $q > r$. So, now we can add up these operations. So, now your total error accumulated would be
$\varepsilon = \sum_{k=0}^{k=n} 2 \times10^{\left(q_{k}-r_{k}-d\right)} + 10^{-d}$
So, then going by the rule-of-thumb in the best case where $q_{k} = r_{k}$, I guess, you will be done in at around 4 steps after which your error is of the order of $10^{-d+1}$
So, this is a rough hand calculation without assuming anything about the system and hence the maximum error I will say but you can get some detailed analysis at this document by Oracle on error calculation.
A way to rephrase the problem is to say "what is the upper bound on $n$ such that $m_{n-1} + \frac{a_n-m_{n-1}}{n} \neq m_{n-1}$ to $p$ digits of precision?" In other words, if $n$ is sufficiently large, then $\frac{a_n-m_{n-1}}{n} < 10^{-p}$. In this case, the value of the left hand side is preceded by a decimal place and $p$ zeros. Thus, adding this quantity to $m_{n-1}$ will result in the first $p-1$ decimal places being unchanged, and the $p^{th}$ decimal place possibly being changed (unless there are trailing 9s, but I will address that momentarily).
So, as a first glance, it is obvious that we want to solve $n\times 10^{-p} > a_n - m_{n-1}$ or $n = (a_n-m_{n-1})\times 10^p$.
Even in the case where $m_{n-1}$ has some trailing 9s in its decimal representation, the difference $m_n-m_{n-1}$ will still be on the order of $10^{-p}$. Now, if you want it strictly less than $10^{-p}$, what you really want is error on the order of $10^{-p-1}$, and so you can compute $n = (a_n-m_{n-1})\times 10^{p+1}$.
Now, if $p > d$, then I'm not sure any of this matters, since the best you can do is $d$ digits of precision in your computation. For instance, if $d = 2, p = 5$, then you might have
$m_n = 6.32 + \frac{1.02387-6.32}{7} = 5.56$
and you can't ever get to 5 digits of precision.
Is this what you're looking for?
-
0No. In floating point arithmetic, $a+\epsilon = a$ for sufficiently small values of $\epsilon$. Thus, to answer our precision question, we want to ensure that the term on the right hand side that we are adding is large enough such that $m_n$ is different than $m_{n+1}$. For instance, if we only store 2 decimal places, then 1.34 + 0.003754 = 1.34. – 2012-07-18