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?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Is $p < d$ or vice versa, or are you looking for a solution in general? Also, are you assuming computations under fixed point arithmetic or floating point arithmetic? $\endgroup$– EmilyCommented Jul 18, 2012 at 17:06
-
$\begingroup$ I am looking for a general solution. What is the difference for this solution if using fixed point arithmetic or floating point arithmetic? $\endgroup$– Jernej JerinCommented Jul 18, 2012 at 17:21
-
$\begingroup$ by $d$ decimal digits, you mean, $d$ significant figures right? It would also probably help if you can specify the the smallest allowed exponent, because then we can implement the formula in some special way to make use of the higher exponent available while still requiring only d significant digits For example, I would like the value of $n$ in the following expression and I guess the $d$ which you mention is as I have described. number = $a.a_{1}a_{2}...a_{d} \ \times \ 10^{-n}$ $\endgroup$– user14082Commented Jul 25, 2012 at 12:15
-
$\begingroup$ @JernejJerin If you are satisfied with the answers, you might consider accepting them, else you might want to indicate what more information you want. $\endgroup$– user14082Commented Nov 3, 2012 at 3:18
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
2
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?
-
$\begingroup$ "what is the upper bound on $n$ such that $m_{n-1} + \frac{a_n-m_{n-1}}{n} \neq m_{n-1}$", did you mean here $m_{n-1} + \frac{a_n-m_{n-1}}{n} \neq m_{n}$? $\endgroup$ Commented Jul 18, 2012 at 22:23
-
$\begingroup$ 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. $\endgroup$– EmilyCommented Jul 18, 2012 at 22:33