# What circuit depth is required to add?

If we suppose that we are given two numbers $a$ and $b$ to add, what circuit depth do we require to add them?

I'm wondering if $a$ and $b$ are $O(n)$, and thus the amount of bits required to store $a$ and $b$ are $O(\log_2(n))$, how much time and/or space we must require to add them.

I'm interested in the general case. However, I am wondering if there is anything else to be said about the case of adding $a+2a+1$. It would be spectacular if we could do this addition in constant circuit depth.

To add two $n$-bit numbers, you need a circuit of depth $\Omega(\lg n)$. Depth $O(\lg n)$ is also achievable, so the lower bound is tight.

There are many examples of such circuits; for instance, a carry lookahead adder has depth $O(\lg n)$ (and size $O(n)$). One can even achieve depth $\lg n + o(\lg n)$; for instance, a Krapchenko adder has depth $\lg n + O(\lg^{1/2} n)$ (and size $O(n)$).

This all assumes bounded fan-in gates, as usual. If you allow AND and OR gates with arbitrary fan-in, then you can achieve constant depth (depth 3, I think). See, e.g., https://en.wikipedia.org/wiki/AC0.

• You can do better than O(lg n) if you use representations other than 2s complement. For example if you put an O(lg n) length nail every lg n bits then you can do piecewise addition with depth lg lg n. You still need lg n depth to remove the nails, so this is only worth it if you can do many additions before removing them. – Craig Gidney May 15 '19 at 21:55

If unbounded fan-in is allowed, depth $1$ is sufficient.

See Page $11$ (Theorem $1.15$) and Page $12$ (Corollary $1.18$) of Herbert Vollmer's book on Circuit Complexity.

• With unbounded fan-in, constant depth suffices (not depth 1: Vollmer's notation has an implicit big-Oh). – András Salamon May 18 '17 at 15:15