Return to Answer

Warning: this answer is buggy. see comments below....

The way I count it, addition can be done in depth 3. Assume $a_i$ and $b_i$ are the $i$th bits of the two numbers, where $0$ is the index of the LSB and $n$ of the MSB. Let us compute the $i$th bit of the sum, $s_i$ in the standard way with carry look ahead:

$s_i = a_i \textrm{ xor } b_i \textrm{ xor } c_i$

where $c_i$ is the carry computed as:

$c_i = \textrm{OR}_{j\mid j < i} (g_j \textrm{ and } p_j)$

and $g_j$ means that the $j$th location "generated" the carry:

$g_j = (a_j \textrm{ and } b_j)$

and $p_j$ means that the carry gets propagated from $j$ to $i$:

$p_j = \textrm{AND}_{k\mid j < k < i} (a_j \textrm{ or } b_j)$

Counting the depth, $p_j$ is depth 2, and $c_i$ is depth 3. While it would seem that $s_i$ is depth 4 or 5, it really is also just depth 3 since it is a bounded fanin computation of depth 3 circuits so one may push the top two levels down using de-Morgan formulas, while blowing the circuit size by a polynomial amount.

Depth 2 circuits require exponential size to compute $c_n$ since depth two circuits must be DNF or CNF and it is easy to verify that there are exponentially many minterms and maxterms in the function $c_n$.

Depth 2 circuits require exponential size to compute addition since a depth 2 circuit must be either DNF or CNF and it is easy to verify that there are exponentially many minterms and maxterms.

Warning: the part below is buggy. See the comments under the answer.

The way I count it, addition can be done in depth 3. Assume $a_i$ and $b_i$ are the $i$th bits of the two numbers, where $0$ is the index of the LSB and $n$ of the MSB.

Let us compute the $i$th bit of the sum, $s_i$ in the standard way with carry look ahead:

$$s_i = a_i \oplus b_i \oplus c_i$$

where $\oplus$ is XOR and $c_i$ is the carry computed as:

$$c_i = \bigvee_{j\mid j < i} (g_j \wedge p_j)$$

and $g_j$ means that the $j$th location "generated" the carry:

$$g_j = (a_j \wedge b_j)$$

and $p_j$ means that the carry gets propagated from $j$ to $i$:

$$p_j = \bigwedge_{k\mid j < k < i} (a_j \vee b_j)$$

Counting the depth, $p_j$ is depth 2, and $c_i$ is depth 3. While it would seem that $s_i$ is depth 4 or 5, it really is also just depth 3 since it is a bounded fanin computation of depth 3 circuits so one may push the top two levels down using de-Morgan formulas, while blowing the circuit size by a polynomial amount.

The way I count it, addition can be done in depth 3. Assume $a_i$ and $b_i$ are the $i$th bits of the two numbers, where $0$ is the index of the LSB and $n$ of the MSB. Let us compute the $i$th bit of the sum, $s_i$ in the standard way with carry look ahead:

$s_i = a_i \textrm{ xor } b_i \textrm{ xor } c_i$

where $c_i$ is the carry computed as:

$c_i = \textrm{OR}_{j\mid j < i} (g_j \textrm{ and } p_j)$

and $g_j$ means that the $j$th location "generated" the carry:

$g_j = (a_j \textrm{ and } b_j)$

and $p_j$ means that the carry gets propagated from $j$ to $i$:

$p_j = \textrm{AND}_{k\mid j < k < i} (a_j \textrm{ or } b_j)$

Counting the depth, $p_j$ is depth 2, and $c_i$ is depth 3. While it would seem that $s_i$ is depth 4 or 5, it really is also just depth 3 since it is a bounded fanin computation of depth 3 circuits so one may push the top two levels down using de-Morgan formulas, while blowing the circuit size by a polynomial amount.

Depth 2 circuits require exponential size to compute $c_n$ since depth two circuits must be DNF or CNF and it is easy to verify that there are exponentially many minterms and maxterms in the function $c_n$.

Warning: this answer is buggy. see comments below....

The way I count it, addition can be done in depth 3. Assume $a_i$ and $b_i$ are the $i$th bits of the two numbers, where $0$ is the index of the LSB and $n$ of the MSB. Let us compute the $i$th bit of the sum, $s_i$ in the standard way with carry look ahead:

$s_i = a_i \textrm{ xor } b_i \textrm{ xor } c_i$

where $c_i$ is the carry computed as:

$c_i = \textrm{OR}_{j\mid j < i} (g_j \textrm{ and } p_j)$

and $g_j$ means that the $j$th location "generated" the carry:

$g_j = (a_j \textrm{ and } b_j)$

and $p_j$ means that the carry gets propagated from $j$ to $i$:

$p_j = \textrm{AND}_{k\mid j < k < i} (a_j \textrm{ or } b_j)$

Counting the depth, $p_j$ is depth 2, and $c_i$ is depth 3. While it would seem that $s_i$ is depth 4 or 5, it really is also just depth 3 since it is a bounded fanin computation of depth 3 circuits so one may push the top two levels down using de-Morgan formulas, while blowing the circuit size by a polynomial amount.

Depth 2 circuits require exponential size to compute $c_n$ since depth two circuits must be DNF or CNF and it is easy to verify that there are exponentially many minterms and maxterms in the function $c_n$.

The way I count it, addition can be done in depth 3. Assume a_i and b_i are the i'th bits of the two numbers, where 0 is the index of the LSB and n of the MSB. Let us compute the i'th bit of the sum, s_i in the standard way with carry look ahead:

s_i = a_i xor b_i xor c_i

where c_i is the carry computed as:

c_i = OR_[j|j less than i] (g_j and p_j)

and g_j means that the j'th location "generated" the carry:

g_j = (a_j and b_j)

and p_j means that the carry gets propagated from j to i:

p_j = AND_[k|k between j and i] (a_j or b_j)

Counting the depth, p_j is depth 2, and c_i is depth 3. While it would seem that s_i is depth 4 or 5, it really is also just depth 3 since it is a bounded fanin computation of depth 3 circuits so one may push the top two levels down using de-Morgan formulas, while blowing the circuit size by a polynomial amount.

Depth 2 circuits require exponential size to compute c_n since depth two circuits must be DNF or CNF and it is easy to verify that there are exponentially many minterms and maxterms in the function c_n.

The way I count it, addition can be done in depth 3. Assume $a_i$ and $b_i$ are the $i$th bits of the two numbers, where $0$ is the index of the LSB and $n$ of the MSB. Let us compute the $i$th bit of the sum, $s_i$ in the standard way with carry look ahead:

$s_i = a_i \textrm{ xor } b_i \textrm{ xor } c_i$

where $c_i$ is the carry computed as:

$c_i = \textrm{OR}_{j\mid j < i} (g_j \textrm{ and } p_j)$

and $g_j$ means that the $j$th location "generated" the carry:

$g_j = (a_j \textrm{ and } b_j)$

and $p_j$ means that the carry gets propagated from $j$ to $i$:

$p_j = \textrm{AND}_{k\mid j < k < i} (a_j \textrm{ or } b_j)$

Counting the depth, $p_j$ is depth 2, and $c_i$ is depth 3. While it would seem that $s_i$ is depth 4 or 5, it really is also just depth 3 since it is a bounded fanin computation of depth 3 circuits so one may push the top two levels down using de-Morgan formulas, while blowing the circuit size by a polynomial amount.

Depth 2 circuits require exponential size to compute $c_n$ since depth two circuits must be DNF or CNF and it is easy to verify that there are exponentially many minterms and maxterms in the function $c_n$.