6
$\begingroup$

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?

  • 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 2

3

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.

1

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?

  • 0
    No. 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