Consider a carry lookahead adder for adding two \(n\)-bit integers, built…
2016
Consider a carry lookahead adder for adding two \(n\)-bit integers, built using gates of fan-in at most two. The time to perform addition using this adder is
- A.
\(\Theta (1)\) - B.
\(\Theta (\log(n))\) - C.
\(\Theta (\sqrt{n})\) - D.
\(\Theta (n)\)
Attempted by 272 students.
Show answer & explanation
Correct answer: B
Answer: Θ(log n)
Key idea: compute carry bits using generate and propagate signals and a parallel-prefix (carry-computation) tree built from binary (fan-in two) gates.
Define for each bit i: generate g_i = a_i AND b_i, and propagate p_i = a_i XOR b_i.
Carries obey c_{i+1} = g_i OR (p_i AND c_i). Pack pairs (g,p) so that combining two pairs is associative. One convenient composition is: combining (g_left, p_left) with (g_right, p_right) yields (g_combined, p_combined) where g_combined = g_right OR (p_right AND g_left) and p_combined = p_right AND p_left.
Use a parallel-prefix algorithm (a binary tree of these pair-combine operations) to compute all prefix results that give the carries. With fan-in-two gates, such a tree has depth Theta(log n).
Finally compute each sum bit s_i = p_i XOR c_i, which adds only a constant extra depth.
Therefore the overall depth (time) of the carry lookahead adder built from gates of fan-in at most two is Theta(log n).
A video solution is available for this question — log in and enroll to watch it.