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$

3 Answers 3

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$
1
  • $\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$ May 15, 2019 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$
1
  • $\begingroup$ With unbounded fan-in, constant depth suffices (not depth 1: Vollmer's notation has an implicit big-Oh). $\endgroup$ May 18, 2017 at 15:15
0
$\begingroup$

We assume that the logic gates are bounded to having two inputs (as opposed to unbounded fan-in gates, with which addition can be done in constant depth by implementing the Conjunctive Normal Form for each bit in the result of the addition). We also assume the standard binary encoding of numbers.

Note that the most significant bit of the result in addition depends on some computation involving at least $n-1$ bits (we need to check that all $n-1$ carries occur in this addition). Thus we need a circuit of depth $\Omega(\log n)$ just to compute some single bit valued function on these $n$ bits, since each time step or depth level in the circuit can only half the number of bits present in it compared to the level above it.

$\endgroup$
1
  • $\begingroup$ I didn't see a proof or citation to a proof in the other answers, so I've added an answer. $\endgroup$
    – shashvat
    Jul 6, 2023 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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