The Booth algorithm is a method of computing the product of two signed binary values. It is especially helpful in situations where hardware capabilities or processing speed are constrained, like with early microprocessors and digital circuitry. The major goal of the method is to minimize the amount of additions and subtractions needed to complete the multiplication.

Work of Booth's Algorithm:

The "Multiplier" (M) and the "Multiplicand" (Q) are the two major elements that drive how the approach works. The Multiplicand is the number we want to multiply, and the Multiplier is a control variable that determines how the multiplication proceeds.
The Accumulator (AC) and Q register are initialized with the multiplier and multiplicand, respectively, at the start of the algorithm. A second version of the multiplier is also made and placed in the M register as a 2's complement (negation).
The Multiplier's bits are then sequentially processed by Booth's algorithm, working from right to left. The two rightmost bits of the multiplier, commonly referred to as Q0 and Q-1, are examined at each step.
If Q0Q-1 is '01', the last two bits of the multiplier indicate that a positive addition should be made, raising the Accumulator by the Multiplicand's value.
If the answer to Q0Q-1 is "10," the Accumulator should be decreased by the Multiplicand using a negative addition (subtraction).
The Accumulator and Q registers are shifted one bit to the right following each addition and subtraction. The bit that drops off the right end of the accumulator is relocated to the leftmost bit location in order to keep the sign bit intact.
Once all of the Multiplier's bits have been processed, the process is repeated, and the Accumulator is where the Multiplication's outcome is stored.
In particular, for big binary integers, Booth's algorithm is more effective than simple multiplication techniques since it minimizes the amount of required additions and subtractions. It is a useful tool for hardware multiplier optimization and played a crucial role in the development of the first resource-constrained computing machines.

Example:

Code:

#include <stdio.h>


int boothsMultiplication(int multiplier, int multiplicand) {


 int result = 0;


 int accumulator = 0;


 int Q = multiplier;


 int M = multiplicand;


 int bitCount = sizeof(int) * 8; // Number of bits in an integer


 for (int i = 0; i < bitCount; i++) {


 // Check the two rightmost bits of Q


 int low2Bits = Q & 0b11;


 if (low2Bits == 0b01) {


 accumulator += M;


 } else if (low2Bits == 0b10) {


 accumulator -= M;


 }


 // Arithmetic right shift Q and accumulator


 int leastSignificantBitQ = Q & 1;


 Q = (Q >> 1) | (leastSignificantBitQ << (bitCount - 1));


 int leastSignificantBitAcc = accumulator & 1;


 accumulator = (accumulator >> 1) | (leastSignificantBitAcc << (bitCount - 1));


 }


 return accumulator;


}


int main() {


 int multiplier = 12; // Example multiplier


 int multiplicand = 5; // Example multiplicand


 int result = boothsMultiplication(multiplier, multiplicand);


 printf("Result: %d\n", result);


 return 0;


}

Output:

Explanation:

Initialization:

The function boothsMultiplication, which requires the multiplier and multiplicand as two integer inputs, is where we begin. These represent the numbers we want to multiply.
We create variables inside the function to control the multiplication process: accumulator stands for the Accumulator and is initialized to 0.
The multiplier's value is stored in Q.
The multiplicand is kept in M.
In order to express the number of bits in an integer (often 32 or 64 bits), the bit count is calculated.

Multiplication Procedure:

We start a loop that iterates through the multiplier's bits. This typically involves 32 or 64 iterations (bits in an integer).
We evaluate Q's two rightmost bits (Q0 and Q-1) at each iteration.

Accumulator Checks and Updates:

We choose whether to add or subtract the multiplicand (M) from the accumulator based on the combination of these two bits (Q0Q-1).
In that case, we increase the accumulator with M.
We deduct M from the accumulator if Q0Q-1 is "10".

The right shift

We do an arithmetic right shift on Q and the accumulator after each operation. The sign bit is maintained while simulating shifting to the following bit.

Result:

The accumulator holds the ultimate result, which is the product of the multiplier and multiplicand after all the multiplier's bits have been processed.

Primary Purpose and Output:

We give sample numbers for the multiplier (12) and multiplicand (5) in the main function.
With these variables, we invoke the boothsMultiplication function, and the output is saved in the result variable.
We then print the outcome to the console.

This code shows Booth's algorithm, an effective method for binary multiplication that repeatedly checks and modifies the multiplier's bits while maintaining an accumulator to calculate the product.

C Tutorial