Theory of Computation/

...

/

Computer Arithmetic

Computer Arithmetic

Learn how to use Mealy machines to perform arithmetic operations like addition, subtraction, and rounding.

We'll cover the following...

Mealy machines naturally model low-level computer arithmetic algorithms. A one’s-complement machine, for example, is modeled by the following trivial machine.

A one's-complement machine
A one's-complement machine

Adding two binary numbers

Adding two binary numbers is also “Mealy-able,” but requires reading corresponding bits simultaneously, right-to-left. The machine will therefore take pairs of bits as input, in reverse order. Recall how to add binary numbers by hand:

The Mealy machine below considers each vertical bit-pair from right-to-left, mimicking what we do manually. We assume it emits the result in right-to-left order.

Adding two binary numbers
Adding two binary numbers

Implementation of the carry

The one thing missing is the leftmost carry bit (only 00110011 is printed for the sum above instead of 1001110011). To solve this problem, we assume that each state emits the bit in its label, which is the carry, when the machine halts there. The code below implements the carry.

Python
def binadd(x,y):
    assert len(x) == len(y)
    state = "0"
    pairs = zip(x,y)            # Combine strings pairwise
    result = ""
    for b1,b2 in reversed(pairs):
        if state == "0":
            if b1=="1" and b2=="0" or b1=="0" and b2=="1":
                result += "1"
            elif b1=="0" and b2=="0":
                result += "0"
            elif b1=="1" and b2== "1":
                result += "0"
                state = "1"
            else:
                assert False, "invalid input"
        else:   # state == "1"
            if b1=="1" and b2=="0" or b1=="0" and b2=="1":
                result += "0"
            elif b1=="1" and b2=="1":
                result += "1"
            elif b1=="0" and b2== "0":
                result += "1"
                state = "0"
            else:
                assert False, "invalid input"
    if state == "1":
        result += "1"           # Append carry
    return result[::-1]         # Reverse result
print(binadd("1101","0110"))    # 10011

Code explanation

This code defines a function called binadd, which takes in two strings, x and y, and performs a binary addition operation on them:

  • In line 2, the assert command checks that the two input strings x and y have the same length. If not, the program will raise an AssertionError.
  • In line 3, the state variable is initialized to "0". It will be used to keep track of any carry-over during the addition process.
  • In line 4, using zip command, we combine the two input strings pairwise, so that pairs is now a list of tuples containing corresponding characters from x and y.
  • In line 5, we initialize an empty string, result, that will be used to store the result
...