Implementing 8bit adder in python

Question

I've implemented an 8bit adder in python as follows:

from gates import AND, OR, XOR
from utils import number_to_binary, binary_to_number

def EightBitAdder(s1='110101', s2='00010', carry_in=0):
    # Limit to 8 bits
    s1 = s1[-8:].zfill(8)
    s2 = s2[-8:].zfill(8)
    s_out = ''
    carry_out = None
    for i in range(8):
        bit_1 = int(s1[8-1-i])
        bit_2 = int(s2[8-1-i])
        carry_in = carry_out if (carry_out is not None) else carry_in
        value_out = XOR(carry_in, XOR(bit_1, bit_2))
        carry_out = OR(AND(bit_1, bit_2), AND(bit_1, carry_in), AND(bit_2, carry_in))
        s_out = str(int(value_out)) + s_out
    print ("  %s (%s) \n+ %s (%s) \n= %s (%s)  -- Carry %s" % (s1, binary_to_number(s1), s2, binary_to_number(s2), s_out, binary_to_number(s_out), int(carry_in)))
    return (s_out, int(carry_out))

The striking thing for me is the "gates" will evaluate lazily, so it won't return a 1/0 unless I call int(), and it seems like there are a tremendous amount of gates in an 8-bit adder. For example:

Am I making a mistake somewhere (or redundancy) somewhere in the carry/value out evaluation, or does a basic 8bit ripple adder really have this many gates in it??

Answer 1

In a real adder, the gates are connected into a graph, where the output of a gate may be used as the input to several others.

You are writing the output as an expression, where the output of a gate can only be used in one place.

This is accomplished by copying the whole expression for each output into all the places it is used. You do this in each iteration -- carry_in is used once to produce the value and 3 times to produce the next carry.

The size of the carry expression is multiplied by 3 in every iteration leading to an exponential explosion in the number of operators you use.

You should probably be generating your output in a different form that can preserve the gate graph, like static single assignment: https://en.wikipedia.org/wiki/Static_single_assignment_form