6
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Craig Gidney May 15 at 21:55
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.