1
$\begingroup$

In elementary school, we are taught how to add, subtract, multiply, and divide two terminating decimals. My question is, what are the corresponding algorithms in the case of non-terminating decimals, whether repeating or otherwise?

Clearly such algorithms exists. For each natural number $n$, you can truncate the two decimals after $n$ decimal places, then apply the usual algorithms for terminating decimals, then take the limit as $n$ goes to $\infty$. (This works because addition, subtraction, multiplication, and division are continuous functions, and the truncation of a decimal after $n$ decimal places converges to the original decimal as $n$ goes to $\infty$.) But without taking limits, is there an elementary way to do it?

It's fine if the algorithms run forever. After all, even the long division algorithm to divide two natural numbers can run forever.

$\endgroup$
  • 2
    $\begingroup$ Without some kind of limiting procedure, how do you even define a decimal expansion of "infinite" length? $\endgroup$ – Xander Henderson Dec 12 '18 at 16:18
  • $\begingroup$ @XanderHenderson Yes, formally infinite decimals are defined in terms of infinite series. But elementary school students are taught what infinite decimals mean intuitively without discussing what limits are. Similarly, I want algorithms that allow you to add, subtract, multiply, and divide decimals without having to know what limits are. $\endgroup$ – Keshav Srinivasan Dec 12 '18 at 16:21
2
$\begingroup$

To add two infinite decimals, I'd begin by setting aside an infinite amount of time, since I'd need that long just to read the input.

For a more reasonable algorithmic problem, suppose I just want to compute the first significant digit of the sum; maybe that won't require reading the whole input. Unfortunately, in some cases, it does. Suppose I want to add $0.9999\dots$ and $0.0000\dots$. If the "$\dots$" means all $9$'s in the first case and all $0$'s in the second, then the sum is $1$, and there are two correct ways to write the answer, $1.000\dots$ and $0.9999\dots$, so the digit just to the left of the decimal point could be $1$ or $0$. But suppose the $\dots$ in the input weren't so simple; maybe the first one has an $8$ after a few million $9$'s while the second is (for simplicity) still all $0$'s. Then the digit just to the left of the decimal point of the answer has to be $0$ not $1$. On the other hand, if the first input has all $9$'s but the second has a $1$ after a few million $0$'s, then the digit just to the left of the decimal point of the answer has to be $1$, not $0$. So, to figure out the digit just to the left of the decimal point in the answer, you might need to read millions of digits of the input.

Maybe you're patient enough to read millions of digits, but the situation can be even worse. If the inputs really are all $9$'s and all $0$'s after the decimal point, so either $1$ or $0$ could be digit just to the left of the decimal point, you can't actually give either of those (correct) answers after any finite amount of time. Even after reading millions of boring $9$'s and $0$'s, you'd still have the possibility that the first input could eventually have an $8$ or the second input could eventually have a $1$, making one of the two possible digits just to the left of the decimal point incorrect. So you could never confidently output the digit just to the left of the decimal point of the answer.

The moral of this story is that addition of infinite decimals is unpleasant in any situation where you want accurate algorithms.

$\endgroup$
  • $\begingroup$ This is the same idea as Federico's answer, but without the computer code. $\endgroup$ – Andreas Blass Dec 12 '18 at 17:14
4
$\begingroup$

In a comment to another answer you write:

"I want a general algorithm which given the decimal expansions of two numbers, finds the decimal expansion of their sum, difference, product, and quotient."

Your problem is right there: how exactly will you give the infinite decimal expansions? We cannot talk about any algorithm if you are not specific on how you provide the input. And you should also specify how you want your output.

You might say, well just assume that we are given two functions $f_1,f_2:\mathbb N\to\{0,1,2,3,4,5,6,7,8,9\}$ such that $x_i = \sum_{n=1}^\infty f_i(n)10^{-n}$.

In C parlance, letting aside the problem that int is a bounded type, we are given

int f_1(int n);
int f_2(int n);

which compute the $n$th digit of $x_i$. Let's also say that we want a function

int sum(int (*f_1)(int), int (*f_2)(int), int n);

that, given f_1, f_2 and $n\in\mathbb N$, produces the $n$th digit of the sum $x_1+x_2$. You very easily see that a generic function like this is not guaranteed to terminate at all. For instance, if you feed it with

int f_1(int n) { return 3; }
int f_2(int n) { return 6; }

then sum(&f_1, &f_2, 1) is never able to terminate because it cannot decide whether the output should be 9 or 0.

This is because you cannot determine if the first decimal digit of $0.\bar3+0.\bar6$ is $0$ or $9$ just by looking at a finite number of decimal digits of the two addend. In other words, this function sum should consume the entire infinite sequence of digits before spitting out even just the first digit.


Edit to clarify.

The OP seems to be missing why sum cannot terminate. Let's say that there is a correct implementation that terminates. Well then calling sum(&f_1, &f_2, 1) terminates. This implementation must have called f_1 and f_2 a finite number of times. Let's call m the largest argument supplied to f_1 or f_2 during the execution. So sum knows at most f_1(1), ..., f_1(m) and f_2(1), ..., f_2(m). Given these values, it outputs either 0 or 9.

If it outputs 9 then

int f_1(int n) { return 3; }
int f_2(int n) {
  if (n <= m)
    return 6;
  else
    return 8;
}

will make it produce also 9, which is wrong.

If it outputs 0 then

int f_1(int n) { return 3; }
int f_2(int n) {
  if (n <= m)
    return 6;
  else
    return 0;
}

will make it produce also 0, which is wrong.

$\endgroup$
  • $\begingroup$ Well, I'm fine if the answer is left as $.9999...$. $\endgroup$ – Keshav Srinivasan Dec 12 '18 at 16:54
  • $\begingroup$ That's not the point. 0.3333 + 0.6667 = 1.0000. If you look only at a finite number of digits, you see 3's and 6's, but you never know if the next one is a 7. So you cannot write out a 9 because you might be wrong $\endgroup$ – Federico Dec 12 '18 at 16:56
  • $\begingroup$ Do you see the problem? Consider the two function f_1 and f_2 that I defined and consider a possible implementation of sum. When does it decide to print out a 9? After having seen how many digits of f_1 and f_2? 100? 1000? No matter how many, a finite number of digits is not sufficient to determine if the first decimal is 9 or 0 $\endgroup$ – Federico Dec 12 '18 at 16:59
0
$\begingroup$

In the case of a repeating decimal, like $.333333...$, they can be represented as fractions and then from there you can do operations like multiplication, addition...

In the other case, all non repeating decimals or irrational numbers like $\pi$ and $e$ can be expressed as infinite sums of rational numbers as explained here, and depending on the sum you may be able to use some algebra to find a single sum for both terms combined.

$\endgroup$
  • $\begingroup$ Yeah, like if you know the decimal expansions of $\pi$ and $e$, how do you find the decimal expansion of $\pi+e$, $\pi-e$, etc.? $\endgroup$ – Keshav Srinivasan Dec 12 '18 at 16:23
  • $\begingroup$ You can define both of those as an infinite series of terms, which doesn't use limits. From there you might be able to do some algebra and come up with a new infinite series. @KeshavSrinivasan $\endgroup$ – Ryan Shesler Dec 12 '18 at 16:27
  • $\begingroup$ But not just those two, I want a general algorithm which given the decimal expansions of two numbers, finds the decimal expansion of their sum, difference, product, and quotient. An algorithm which doesn't require knowledge of calculus to use. $\endgroup$ – Keshav Srinivasan Dec 12 '18 at 16:30
  • $\begingroup$ pdfs.semanticscholar.org/fc77/… - This paper explains how any irrational number can be written as an infinite series of rational numbers, which doesn't use calculus. At most this is algebra 2 $\endgroup$ – Ryan Shesler Dec 12 '18 at 16:34
  • $\begingroup$ @Federico I can't comment on an answer because I don't have a 50 reputation, but .99999... is equal to 1. Let x be .9999..., then 10x is 9.99999... That means 10x - x = 9x, and 9.9999... - .99999... = 9. Then 9x = 9 and x = 1, therefore .9999... = 1 $\endgroup$ – Ryan Shesler Dec 12 '18 at 17:11
0
$\begingroup$

If you want to find a decimal representation of $\pi + e$

Since this sum will be an irrational number, and you can't write out an infinite decimal, you are going to have to decide how many digits you care to represent.

Once you have made that determination, I see two options.

One s to round them both off, and add them together.

$3.1415 + 2.7183$

Add them together like you learned in elementary school. If you want to be safe, work with one more significant digit than you really care about to minimize the impact of rounding.

Another option is to work left to right. This is how I tend to add anyway. It more quickly gives calculates the "important parts" and if you make mistake, it pushes errors to the right where they get smaller, rather than to the left where they get bigger.

Add the digits. Look one more spot to the right. Look for the potential of a carry. Adjust for it if you do, and work as far down the chain of decimals as you care to go.

$\endgroup$
  • $\begingroup$ Minor nitpick : it's not yet known that $\pi+e$ is irrational. $\endgroup$ – Paramanand Singh Dec 13 '18 at 2:56
  • $\begingroup$ "Since this sum will be an irrational number, and you can't write out an infinite decimal, you are going to have to decide how many digits you care to represent." What I want to do is write out the infinite decimal over an infinite period of time. It's just like if you do long-division of two natural numbers, the process can continue for all eternity. $\endgroup$ – Keshav Srinivasan Dec 13 '18 at 3:53

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.