How do you add, subtract, multiply, and divide infinite decimals?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

Coinductively.

Represent each infinite number as a lazy "stream" of bits; for simplicity, you only need to consider the unit interval. For example, the corresponding ML type would be:

datatype interval = I of unit -> bool * interval

In Haskell, this would just be an infinite [Bool] instance.

As mentioned in other answers, it may take infinite time to compute details about the resulting decimal (in computer science terms, the resulting bit stream need not be "productive"). However, you can often make good progress! For example, consider $0.3333... + 0.3333...$ or $0.5000... + 0.2323...$; both can certainly be computed.

---

The algorithm for addition can be described as follows:

1. Lazily look at the first two bits of each number.
2. If the second bits are the same, you know definitively whether or not there will be a need to carry. Use this information to determine the first bit of the result based on the first bit of each input.
3. Otherwise, "recurse" and use the result to compute the first bit. (This is the part that need not terminate; if you get an "unlucky" digit pattern, you'll recurse infinitely to compute the first bit.)

I've put some Standard ML code for this algorithm on GitHub. Here's what running the given examples looks like:

(* demo.sml *)

local
  val ` = Natural.fromInt
  val oneHalf = Interval.scale (`2) (`1)
  val oneThird = Interval.scale (`3) (`1)
  val repeat23 = Interval.scale (`99) (`23)
  val op + = Interval.+
in
  (* although we have infinite-precision decimals, round to a floating-point approximation *)
  val a = Interval.toFloat (oneThird + oneThird)
  val b = Interval.toFloat (oneHalf + repeat23)
end

[opening demo.sml]
val a = 0.666666666667 : real
val b = 0.732323232323 : real