Math from scratch, part three: natural addition

Posted on by

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 Naturals, 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++.

23 thoughts on “Math from scratch, part three: natural addition”

      • 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!

        Reply ↓

          • 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 on bit 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.

  2. 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.

    Reply ↓

    • 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).

      Reply ↓

      • 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].

        Reply ↓

        • 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.

          Reply ↓

          • 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.

  3. 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.)

    private static Natural Add(Natural x, Natural y, Bit carry)
{
    if (ReferenceEquals(x, Zero) && ReferenceEquals(y, Zero))
        return carry == ZeroBit ? Zero : One;
    else if (x.head == y.head)
        return Create(Add(x.tail, y.tail, x.head), carry);
    else
        return Create(Add(x.tail, y.tail, carry), ~carry);
}
    Reply ↓

      • 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.

        Reply ↓

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

  6. 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.

    Reply ↓

  8. 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 🙂

    Reply ↓

  9. Pingback: Math from scratch in Haskell: addition | Loominate

  10. 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.

    Reply ↓

Leave a comment