A technique for adding infinite binary sequences.

Real numbers can be represented as infinite sequences of digits in some particular base; for example, π is 3.141592653… in base 10, 10.0102110122… in base 3, or 11.001001000011… in base 2; etc.

Traditional approaches to addition work with the least significant digit first and cannot work on infinite digit strings because there is no least significant digit. Hence, I present a form of addition that works from the most significant digit instead.

Set-up

I’ll assume some bookkeeping is already done. The numbers to add will be interfaced by two functions, x and y, which return the digits of the two inputs in decreasing order, beginning with most significant digit of the two numbers. I’ll also assume they are both represented in base b and that all that is needed is to output the digits in order.

The process will keep track of two numbers; nines, which starts at 0 and might grow arbitrarily large, and top, which starts at 0 and is never larger than b – 1.

I will assume the ability to add two single-digit numbers and receive back the digit and carry; for example, “‍add( 6, 7 )‍” would return “‍1, 3‍” in base 10. Note that the carry will always be either 0 or 1.

The Process

algorithm

Repeatedly perform the following:

I am pretty proud of my code environment for this blog. I have a javascript function that reads near-C syntax and re-formats it as nested boxes with labels.

Let c, d = add( x(), y() ); If d = b – 1 { Increase nines by 1 } Otherwise, if c = 0 { Output top; Repeat nines times: { Output b – 1 }; Set nines to 0; Set top to d } Otherwise { Output top + 1; Repeat nines times { Output 0 }; Set nines to 0; Set top to d }

An Example (in base 10)

Let’s work through this by hand for 3.16452819 and 2.77542189 These numbers were contrived to demonstrate all cases. .

At every point you need to remember two things: the digit you think you’ll output next and the number of nines that will follow that digit. We’ll start them both off at zero.

We ask for a digit from each number, getting a 3 and a 2. Adding them together we get 5, carry 0. Since there’s no carry, we don’t have any run of nines right now, and the new digit is not 9, we output our old guess (0) and remember the new digit as our best guess (5).

Next we get 1 and 7, which give us 8 carry 0. Still no carry, no nines remembered, and the new number’s not a nine so we output our old guess (5)5 and remember the 8.

Next we get 6 and 7, which give us 3 carry 1. We add the carry to our guess to output 99 and remember the 3.

Next we get 4 and 5, which give us 9 carry 0. Since we have a nine we we simple remember we have one 9 after our 8 and continue without outputting anything.

Next we get 5 and 4, which give us 9 carry 0. We remember we have seen two nines now and continue.

I used to have a mistake in this step. Thanks to Markham for correcting it! Next we get 2 and 2, which give us 4 carry 0. Since this isn’t a nine and there’s no carry we output our 33 and the two nines we’ve seen 9 9, reset the number of unresolved nines to 0, and then remember the 4.

Next we get 8 and 1, which give us 9 carry 0. We remember we have seen one nine now and continue.

Next we get 1 and 8, which give us 9 carry 0. We remember we have seen two nines now and continue.

Next we get 9 and 9, which give us 8 carry 1. Since this isn’t a nine but we do have a carry we output the carry plus our remembered 45; we then output two zeros for our 9s0 0, reseting the number of nines to 0. We remember the 8 and continue.

Since this is the end, we output our guess 8 and finish. End result: 5.93995008.

Discussion

This algorithm has many of the same characteristics I noted about Gosper arithmetic for continued fractions. In particular, for certain classes of infinite inputs (e.g., 0.3333… + 0.6666… in base 10) the algorithm runs forever without ever outputing a single digit.

As written, the algorithm is missing one feature required to produce, on demand, an interval guaranteed to contain the answer. Dumping the existing guess and string of nines gives a lower bound as that is what would happen if all subsequent digits were zero, but the upper bound is what we’d have if our next digit gave 0 carry 2, the limit sum of an endless stream of 9s. If our current top is 8, that would change digits we’ve already output. This difficulty can be overcome by adding one more level of delay.

Before this number representation is useful we’d need to have other operators available. Subtraction is essentially the same as addition, +, –, exp, and ln would be enough to provide everything else… but multiplication, division, exponentiation, logarithms, and the like will require a bit more thought.