7
$\begingroup$

Suppose we want to do one of the four basic arithmetic operations on two irrational numbers, and we want some confidence that our answer is correct to $n$ significant figures/decimal places. Doing this to $n$ siginificant figures seems much harder, since the two numbers may be of much different scales, and you might experience phenomena such as "catastrophic cancellation" for instance.

So suppose we try do $\pi + e$, correct to $5$ decimal places. If I take $\pi$ and $e$ both correct to $5$ decimal places, and try to add them with interval arithmetic, we see that $[3.14159, 3.14160] + [2.71828, 2.71829] = [5.85987, 5.85989]$; i.e. we only get an answer correct to $4$ decimal places. However, if we do the same calculation, using $\pi$ and $e$ with $6$ decimal places, we see that $[3.141592, 3.141593] + [2.718281, 2.718282] = [5.859873, 5.859875]$; i.e. we get an answer correct to $5$ decimal places.

As another example, take multiplication. If we take $\pi$ and $e$ correct to $6$ decimal places, and multiply them, we see that $[3.141592, 3.141593] * [2.718281, 2.718282] = [8.53972..., 8.53973...]$. So in this case, we only get something correct to $4$ decimal places. However, performing the calculation with $\pi, e$ correct to $7$ decimal places, we get the answer correct to $5$ decimal places: $[3.1415926, 3.1415927] * [2.7182818, 2.7182819] = [8.539733..., 8.539734...]$.

However, if one of our multiplicands is much larger than the other, we need more decimal places to get a similar level of precision. For instance, to get $50\pi * e$ correct to $5$ decimal places, we need $50\pi$ correct to $7$ decimal places and $e$ correct to $9$ decimal places.

From this, it is tempting to conjecture that if $a$ and $b$ are irrational numbers, and we want $a + b$ correct to $n$ decimal places, it suffices to use $a,b$ rounded to $n+1$ decimal places. Additionally, if we want $a*b$ correct to $n$ decimal places, it is also tempting to conjecture that it is sufficient to work with $a$ correct to $n+ 2 + \lfloor\log_{10}(b)\rfloor$ decimal places, and $b$ correct to $n + 2 + \lfloor\log_{10}(a)\rfloor$ decimal places.

Since subtraction and division can be rewritten as addition and multiplication respectively, it suffices to understand addition and multiplication. Does anyone have any insight into this? Can anyone see any way of proving the two conjectures above? That is, if they are indeed correct?

EDIT: As stewbasic has pointed out in the comments below, the above approach to addition does not work if the precision needed is less than the precision of one of the summands (in general terms). I have suggested a workaround in the comments below, but it seems to me that any proof of this suggested workaround would be quite involved.

$\endgroup$
7
  • $\begingroup$ Could you clarify what you mean by "correct to n decimal places"? If you want to guarantee the number is in $[k/10^n,(k+1)/10^n]$ for some integer $k$ then you need to distinguish between $1-0.1^m$ and $1+0.1^m$ for any $m$, which requires arbitrarily high precision. OTOH if you just want some rational number within $1/10^n$ of your target, your argument should work. $\endgroup$ – stewbasic Jul 4 '16 at 22:09
  • $\begingroup$ @stewbasic Ok, write your real number $x$ as $m + 0.d_1 d_2 d_3...$, where $m$ is some integer, and $d_i$ is the decimal digit in the ith position. Then say another real number $u$ is correct to $n$ decimal places (with respect to the original real number $x$) if $u = m + 0.e_1 e_2 e_3 ...$, where $e_i = d_i$ for all $i \in \{1, ..., n\}$. I guess that agrees to a certain extent with the first definition you give. $\endgroup$ – MadMonty Jul 4 '16 at 22:22
  • $\begingroup$ in that case your proposal doesn't work. Consider $a=1$ and $b=0.1^{100}$. To get $a-b$ correct to one decimal place ($0.9$) you need $b$ accurate to $100$ decimal places. Another alternative is the usual rounding rules (5 rounds up), but this has the same problem for $0.95-0.1^{100}$. $\endgroup$ – stewbasic Jul 4 '16 at 23:11
  • $\begingroup$ @stewbasic That's absolutely true. Maybe for addition, for $a+b$ to be correct to $n$ decimal places, we need to work with $a,b$ correct to $\max(n+1, \text{location of first significant figure of } a, \text{location of first significant figure of } b)$ decimal places? With something similar for multiplication? I need to think about this a bit harder. $\endgroup$ – MadMonty Jul 5 '16 at 11:21
  • 1
    $\begingroup$ @MadMonty What about (for example) $\pi$ and $10-\pi$ (in decimal form, $3.14159...$ and $6.85840...$)? I think requiring the first $n$ digits of the result to match the first $n$ digits of the actual result would require an $infinite$ number of digits in the worst case. $\endgroup$ – user351579 Jul 8 '16 at 3:39
1
$\begingroup$

HINT.-Let $x,y$ be irrational in $[0,1]$ with $$x=0.a_1a_2a_3.......a_na_{n+1}a_{n+2}.........\\y=0.b_1b_2b_3.......b_nb_{n+1}b_{n+2}.........$$ and consider the approximations $$x_n\approx 0.a_1a_2a_3.......a_n\\y_n\approx 0.b_1b_2b_3.......b_n$$ We can see that $x_n+y_n$ is correct to n decimal places if and only if $a_{n+1}+b_{n+1}\lt 10$ in which case the correct digit corresponding to the $n^{th}$ place is given by $a_n+b_n$ modulo $10$ but when $a_{n+1}+b_{n+1}\gt 10$ this correct digit would be $a_{n}+b_{n}+1$ modulo $10$.

$\endgroup$
3
  • $\begingroup$ This is a nice answer, but it should be noted that even if $a_{n+1}+b_{n+1}<10$, if $a_{n+1}+b_{n+1}=9$ and there is carry over from $a_{n+2}+b_{n+2}$, then the same thing happens. And so on and so forth. $\endgroup$ – Fimpellizieri Jan 30 '18 at 3:20
  • $\begingroup$ I thought it was considered. You are wright anyway. Thanks. $\endgroup$ – Piquito Jan 30 '18 at 19:13
  • $\begingroup$ It should be noted that as soon as $a_{n+k}+b_{n+k}\leq 8$, we can stop right there and the addition will be guaranteedly correct up to digit $n+k-1$, and digit $n+k$ will be either correct or $1$ short. $\endgroup$ – Fimpellizieri Jan 30 '18 at 20:05
0
$\begingroup$

For the theory of multiple-precision floating-point computations, see the book Modern Computer Arithmetic by Brent and Zimmermann, sections 3.2 and 3.3.

For an implementation, see The GNU MPFR Library, a C library for multiple-precision floating-point computations with correct rounding.

$\endgroup$
2
  • $\begingroup$ There are several other libraries. $\endgroup$ – lhf Jul 7 '16 at 0:49
  • $\begingroup$ I am reasonably familiar with MCA and MPFR. However, they both aim to give results correct to $n$ bits of precision. This means they're giving answers correct to $n$ (binary) significant figures, rather than $n$ binary places. Whilst it's straightforward to convert their ideas from binary to decimal, it's still subtly different from what I'm trying to do. I will reread chapter 3 however, and see if I can glean anything useful. $\endgroup$ – MadMonty Jul 7 '16 at 0:56

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.