Discussion
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
Answer: B
The addition time is \(\Theta(\log(n))\).
A carry lookahead adder computes generate and propagate signals for every bit pair, then combines them to find all the carries at once instead of rippling. Each carry \(c_{i}\) is an AND-OR expression over up to \(i\) generate and propagate terms. With gates of fan-in at most two, an AND or OR of \(n\) inputs must be built as a balanced tree of depth \(\log_{2} n\), and the prefix structure of the carry computation also has logarithmic depth. So the delay grows as \(\Theta(\log n)\).
\(\Theta(1)\) would need unbounded fan-in. \(\Theta(n)\) is the ripple-carry adder, which carry lookahead is designed to beat, and \(\Theta(\sqrt{n})\) is typical of carry-skip or carry-select designs, not full lookahead.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development