[Solved]: What circuit depth is required to add?

Problem Detail: 

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.

Asked By : Matt Groff

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19468

3.2K people like this

 Download Related Notes/Documents