Most Significant Bit First Addition

math# Set-up

# The Process

algorithm
## An Example (in base 10)

# Discussion

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.

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.

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`
}

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.

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.

Loading user comment form…

Looking for comments…