GATE CS 1996 Q1.23 — Computer Arithmetic

In Booth's multiplication algorithm, the number of arithmetic operations (additions and subtractions) depends on the transitions between adjacent bits in the multiplier (including an implicit $0$ appended to the right of the least significant bit):

• A transition from $0$ to $1$ requires a subtraction.
• A transition from $1$ to $0$ requires an addition.
• No transition ($0$ to $0$ or $1$ to $1$) requires only a shift operation (no addition/subtraction).

The performance of Booth's algorithm is worst when the number of additions and subtractions is maximized. This occurs when the multiplier has the maximum number of transitions.

Let's analyze the options:

• Option A ($101010 ext{…}1010$): The bits alternate between $1$ and $0$ throughout the entire sequence. This results in a transition at almost every bit position, maximizing the number of additions and subtractions (worst-case performance).
• Option B ($100000 ext{…}0001$): Contains long runs of $0$s, resulting in very few transitions.
• Option C ($111111 ext{…}1111$): A continuous run of $1$s. This requires only one subtraction at the beginning and one addition at the end, regardless of the length of the multiplier (best-case performance).
• Option D ($011111 ext{…}1110$): Contains a long run of $1$s, resulting in very few transitions.

Therefore, the pattern $101010 ext{…}1010$ gives the worst performance.