Last time in this series we built a `Natural `

object that represented a number as a linked list of bits, with the least significant bit in the head and the most significant bits in the tail. We use the “null object pattern” where a `Zero`

tail represents that the remaining bits in the sequence are all zero, and the sequence of bits never ends in a zero bit followed by Zero.[1. If that sounds different than what I wrote the last time, reread last week’s post. I slightly changed the organization of the structure based on a reader suggestion.]

So let’s then divide our implementation into two parts, one which enforces the public part of the contract that `null`

is meaningless:

public static Natural operator +(Natural x, Natural y) { if (ReferenceEquals(x, null)) throw new ArgumentNullException("x"); else if (ReferenceEquals(y, null)) throw new ArgumentNullException("y"); else return Add(x, y); }

Note that now that we’re past the null checks we know that we will never dereference null so long as we don’t look at the tail of `Zero`

.

And again, recall that I am always going to spell out when I am doing reference equality on `Natural`

s, and I am going to mostly use a “by cases” approach to designing each method. This works well for recursive methods. Actually, now would be a good time for my standard refresher on how to write a recursive method:

- Are we in a trivial case? Then solve the problem and return the solution.
- Otherwise, split the problem into one or more strictly smaller problems.
- Solve the subproblems recursively.
- Combine their solutions to solve the larger problem.

So let’s think about addition of two sequences of bits with that in mind. What are the trivial cases? If either addend is `Zero`

then the result can be the other addend. The non-trivial case is then that we are adding a number `x`

with a tail and a least significant bit to a number `y`

with a tail and a least significant bit. I’ll use the notation ` { tail : head } `

to compactly characterize a `Natural`

object throughout this series.

x + y = { xtail : xhead } + { ytail : yhead } = ???

We know that numerically the number `{ xtail : xhead }`

has the numeric value of ` 2 * xtail + xhead `

. That is, if we have say `{ One : ZeroBit }`

, then the value of the tail is 1, twice that is 2, add the least significant bit — 0 — and the result is 2. So we can simplify as follows:

x + y = { xtail : xhead } + { ytail : yhead } = 2 * xtail + xhead + 2 * ytail + yhead = 2 * (xtail + ytail) + (xhead + yhead)

We have our recursive part; we can calculate `xtail + ytail`

recursively, and then double it by making a new `Natural`

with the sum as the tail and zero as the bit. But what about the other part?

There are three cases. If `xhead`

and `yhead`

are both zero then we are done; adding zero is a no-op that we can skip. If one of them is one and the other is zero then we can set the low bit of the sum to one instead of zero. But what if both of them are one? Now we’ve got to add two to the sum, and *we don’t know how to do that*. Perhaps there is another way we can break this down. Let’s divide that up into cases again.

Suppose `xhead`

is 0. Then:

2 * xtail + xhead + 2 * ytail + yhead = 2 * (xtail + ytail) + (0 + yhead) = { xtail + ytail : yhead }

Suppose `yhead`

is 0. Then:

2 * xtail + xhead + 2 * ytail + yhead = 2 * (xtail + ytail) + (xhead + 0) = { xtail + ytail : xhead }

Otherwise, both heads are 1:

2 * xtail + xhead + 2 * ytail + yhead = 2 * (xtail + ytail) + (1 + 1) = 2 * (xtail + ytail) + 2 = 2 * (xtail + ytail + 1) = { xtail + ytail + 1 : 0 }

Aha! We can turn that last case into *two *recursive additions.[1. The usual way to explain this is that the extra one is a “carry bit”, but I’ve always found that confusing and unnecessary. The need for the extra one follows directly from the algebra above; there’s no need to invoke the pencil-and-paper addition that we learned as children.] Now we can write the code very easily:

private static Natural Add(Natural x, Natural y) { if (ReferenceEquals(x, Zero)) return y; else if (ReferenceEquals(y, Zero)) return x; else if (x.head == ZeroBit) return Create(Add(x.tail, y.tail), y.head); else if (y.head == ZeroBit) return Create(Add(x.tail, y.tail), x.head); else return Create(Add(Add(x.tail, y.tail), One), ZeroBit); }

And finally, for debugging purposes it is nice to have an implementation of `ToString`

. It’s recursive and inefficient because hey, like I said, this is not pragmatic code here.

public override string ToString() { if (ReferenceEquals(this, Zero)) return "0"; else return tail.ToString() + head.ToString(); }

And now we can actually write some code:

var n0 = Natural.Zero; var n1 = Natural.One; var n2 = n1 + n1; var n3 = n2 + n1; var n4 = n2 + n2; var n5 = n2 + n3; var n6 = n3 + n3; Console.WriteLine(n0); Console.WriteLine(n1); Console.WriteLine(n2); Console.WriteLine(n3); Console.WriteLine(n4); Console.WriteLine(n5); Console.WriteLine(n6);

and get the expected output:

0 01 010 011 0100 0101 0110

OK, addition is done. **Next time on FAIC:** We’ll talk a bit about the increment operator in C# vs C and C++.

I think you’ve missed a special case in the ToString implementation. Another great article as always.

I think he defined ToString for individual bits last time and head is a bit

I had completely missed that Natural One is in fact a OneBit head, and a Zero as a tail. I believed it had been defined as a OneBit head with a null tail, and thus the ToString of a null tail in that case would throw.

Thanks!

That was my original concept, but a reader pointed out that using Zero as the “null object” would make the algorithms more elegant, so I switched it.

Why not make Zero its own tail as well?

if(tail == null) tail = this;

That would make e.g. shifting more elegant.

It also suggests an implementation of twos complement once you decide to move from the naturals to the integers.

I did consider that. However, (1) since zero will be the base case of all my recursions, I’m not planning on ever looking at the tail of zero, so it doesn’t matter what it is, (2) I’d rather any bugs whereby I do look at the tail of a zero crash immediately rather than go into unbounded recursions, (3) the fact that I’m representing naturals as a sequence of bits is an implementation detail. Right and left shift are not operations on

naturals; they are operations onbit fields, and therefore I’m not planning on implementing either, and (4) I’m not going to use twos complement for negative integers. So yes, interesting idea, no, not going to do it.When I mentioned shifting, I was going on the assumption that they would be needed to implement multiplication and division efficiently.

But I don’t need to implement a shift operator to do that. Shifting right is the same as taking the tail, so I’ll just take the tail. Shifting left is the same as

`Create(tail, ZeroBit)`

, so I’ll just make that call.An alternative to using a “carry bit” would be to have a pair of mutually-recursive methods for “Sum(X,Y)” and “SumPlusOne(X,Y)”; that would allow for efficient tail recursion. I know you’re not trying to produce a high-performance numerics package, but the existence of multiple recursive calls in a method like this raises the specter of exponential run time [as happens in e.g. the naive fibon(n)=fibon(n-1)+fibon(n-2)]. In practice, a string of consecutive ones that makes adding one slow would yield a string of zeroes that would make adding the result fast, so there’s no real danger of exponential run-time, but that’s hardly visually obvious.

No need to have two functions there. Just have one that always takes a carry and allow that to be 0. That’s basically how naive hardware adders function – another advantage of that one is that it trivially allows you to implement subtraction for 2-complement (logical not of second input and set carry of first block to 1).

Since the function that took a Boolean carry input would then have to use an `if` to select one of two courses of action based upon it, I think it would be cleaner to simply use a different function for each course of action. Alternatively, if one had separate classes for Zero, One, ZeroPlusTail, and OnePlusTail (derived from an abstract Number), all conditional tests could be replaced with virtual method dispatch for operations “ConcatZero”, “PlusOne”, “AddX”, “AddXPlusOne”, “Add2x”, and “Add2xPlusOne” [ConcatOne need not be virtual, since every type would do it the same way].

Actually you can implement the adder without an if – the hardware full-adder gives us the intuition for that one:

Inputs: A B Cin

Output: S Cout

S = A ^ B ^ Cin

Cout = (A & B) | (Cin & (A ^ B))

(Not that anybody would implement adders like that in HW because a chain of full-adders has a rather bad critical path)

Compared to that if you actually go with the virtual dispatch logic I don’t see how you could avoid if branches to decide which function you want to call. Ok yes you could by basically using similar logic to above to decide on the function.

To avoid using conditional logic, each class includes virtual methods for “ThisPlusNumber”, “ThisPlusNumberPlusOne”, as well as “ThisPlusZeroPlus2xNumber”, “ThisPlusOnePlus2xNumber”, and “ThisPlusTwoPlus2xNumber”. If one adds two `OnePlusTail` objects, the `ThisPlusNumber` method of the first would call the `ThisPlusOnePlus2xNumber` method of the second, which would call `ThisPlusNumberPlusOne` on its tail and that of the other number, and then `PrependZero” to the result.

To avoid having two calls to Add in the final case, I came up with this alternate version of Add that has a “carry” argument. (This assumes that Bit defines operator

`~`

and that`Natural.Zero`

links to itself.)In a response to the start of this series I mentioned I share for those that are interested a matching F# implementation:

I try to model the F# code to after EL’s C# code

https://github.com/mrange/experiments/blob/master/fun/numerals/elnumerals/Program.fs

I don’t claim to be expert F# programmer, I just post it in case someone is interested.

Looks pretty straightforward so far. Thanks for doing this. I am curious to see how things go when we get to subtraction.

I considered adding OnePad (ie trailing ones instead of zeroes). That would enable implementing negative numbers as -x = (not x) + 1. With negative numbers a subscription becomes an addition.

Ofc, it’s not really natural numbers then.

Pingback: The Morning Brew - Chris Alcock » The Morning Brew #1448

When you said you were going for a simple approach, I had pictured a half adder implemented with boolean logic being called recursively for each bit. Interesting approach you came up with to avoid that.

Hi Eric, are you considering hosting the sample code on codeplex/github/etc? That would be great.

This series reminds me of Timwi’s esolangs, where due to how basic the languages are all arithmetic must be constructed from scratch in a convoluted fashion.

http://esolangs.org/wiki/Funciton/Basic_arithmetic shows some of the arithmetic operations. First the successor function is built out of the language’s NAND, shift-left and less-than operations, and the rest is built up from there.

To really appreciate the beauty of these, it helps to understand how Funciton operates. Despite its look, it is absolutely _not_ like electronic schematics but rather different. Timwi described it in full on http://esolangs.org/wiki/Funciton and even wrote an interpreter and a compiler to IL (.NET exes, yay!)

Sorry about the shameless plug but it seemed relevant, and I feel Timwi’s creations are totally under-appreciated :)

Pingback: Math from scratch in Haskell: addition | Loominate

I think it would be cleaner to simply use a different function for each course of action. Alternatively, if one had separate classes for Zero, One, Zero Plus Tail, and One Plus Tail (derived from an abstract Number), all conditional tests could be replaced with virtual method dispatch for operations “Concat Zero”, “Plus One”, “AddX”, “Add X Plus One”, “Add2x”, and “Add2xPlusOne” [ConcatOne need not be virtual, since every type would do it the same way. Thanks for sharing.