# Write a C Program to Implement Booth’s Algorithm for Multiplication

#### Aim:

Write a C Program to Implement Booth’s Algorithm for Multiplication.

#### Theory:

• Booth’s multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in notation.
• Booth’s algorithm serves two purposes: Fast multiplication (when there are consecutive 0’s or 1’s in the multiplier). And Signed multiplication.
• Booth’s algorithm is a powerful direct algorithm to perform signed-number multiplication.
• The algorithm is based on the fact that any binary number can be represented by the sum and difference of other binary numbers.
• Booth’s algorithm examines adjacent pairs of bits of the N-bit multiplier Y in signed two’s complement representation, including an implicit bit below the least significant bit, y-1 = 0.
• For each bit yi, for I running from 0 to N-1, the bits yi and yi-1 are considered.
• Where these two bits are equal, the product accumulator P is left unchanged. Where yi = 0 and yi-1 = 1, the multiplicand times 2i is added toP; and where yi = 1 and yi-1 = 0, the multiplicand times 2i is subtracted from P. The final value of P is the signed product.
• The representation of the multiplicand and product is not specified; typically, these are both also in two’s complement representation, as the multiplier, but any number system that supports addition and subtraction will work as well.
• As stated here, the order of the steps is not determined.
• Typically, it proceeds from LSB to MSB, starting at i = 0; the multiplication by 2i is then typically replaced by an incremental shifting of the P accumulator to the right between steps; low bits can be shifted out, and subsequent additions and subtractions can then be done just on the highest N bits of P.
• There are many variations and optimizations on these details.
• The algorithm is often described as converting strings of 1’s in the multiplier to a high-order +1 and a low-order –1 at the ends of the string.
• When a string runs through the MSB, there is no high-order +1, and the net effect is interpreted as a negative of the appropriate value.

#### Algorithm:

1. Start
2. Product = 0
3. Ask user to enter two decimal numbers: n1, n2
4. Convert them into binary and store them in arrays num1 and num2
5. Two’s complement the numbers if they are negative
6. Two’s complement num2 and store as n com
7. Create a copy of num1 as n copy
8. Set q = 0
9. If num1[i] = = q, arithmetic shift product : ncopy
10. 1Else if num1[i] == 1 and q ==0, add ncom to product and arithmetic shift product : ncopy
11. 1Else add num2 to product and arithmetic shift product : ncopy
12. 1In each step set q = num1[i] after shift operation
13. Repeat steps 9,10,11 and 12 until all bits of num1 are shifted out
14. Display final result as product : ncopy
15. End

#### Program:

```#include <stdio.h>
#include <math.h>
int a=0,b=0,c=0,a1=0,b1=0,com={1,0,0,0,0};
int anum={0},anumcp ={0},bnum={0};
int acomp={0},bcomp={0},pro={0},res={0};
void binary(){
a1 = fabs(a);
b1 = fabs(b);
int r, r2, i, temp;
for(i = 0; i < 5; i++){
r = a1 % 2;
a1 = a1 / 2;
r2 = b1 % 2;
b1 = b1 / 2;
anum[i] = r;
anumcp[i] = r;
bnum[i] = r2;
if(r2 == 0){
bcomp[i] = 1;
}
if(r == 0){
acomp[i] =1;
}
}
c = 0;
for( i = 0; i < 5; i++){
res[i] = com[i]+ bcomp[i] + c;
if(res[i]>=2){
c = 1;
}
else
c = 0;
res[i] = res[i]%2;
}
for(i = 4; i>= 0; i--){
bcomp[i] = res[i];}
if(a<0){
c = 0;
for(i = 4; i>= 0; i--){
res[i] =0;
}
for( i = 0; i < 5; i++){
res[i] = com[i]+ acomp[i] + c;
if(res[i]>=2){
c = 1;
}
else
c = 0;
res[i] = res[i]%2;
}
for(i = 4; i>= 0; i--){
anum[i] = res[i];
anumcp[i] = res[i];
}
}
if(b<0){
for(i=0;i<5;i++){
temp = bnum[i];
bnum[i] = bcomp[i];
bcomp[i] = temp;
}
}
}
int i;
c = 0;
for( i = 0; i < 5; i++){
res[i] = pro[i]+ num[i] + c;
if(res[i]>=2){
c = 1;
}
else
c = 0;
res[i] = res[i]%2;
}
for(i = 4; i>= 0; i--){
pro[i] = res[i];
printf("%d",pro[i]);
}
printf(":");
for(i = 4; i>= 0; i--){
printf("%d",anumcp[i]);
}
}
void arshift(){
int temp = pro, temp2 = pro,i;
for(i = 1; i <5  ; i++){
pro[i-1] = pro[i];
}
pro = temp;
for(i = 1; i < 5  ; i++){
anumcp[i-1] = anumcp[i];
}
anumcp = temp2;
printf("\nAR-SHIFT: ");
for(i = 4; i>= 0; i--){
printf("%d",pro[i]);
}
printf(":");
for(i = 4; i>= 0; i--){
printf("%d",anumcp[i]);
}
}void main(){
int i, q=0;
printf("\t\tBOOTH'S MULTIPLICATION ALGORITHM");
printf("\nEnter two numbers to multiply: ");
printf("\nBoth must be less than 16");
do{
printf("\nEnter A: ");
scanf("%d",&a);
printf("Enter B: ");
scanf("%d",&b);
}while(a>=16 || b>=16);
printf("\nExpected product = %d", a*b);
binary();
printf("\n\nBinary Equivalents are: ");
printf("\nA = ");
for(i = 4; i>= 0; i--){
printf("%d",anum[i]);
}
printf("\nB = ");
for(i = 4; i>= 0; i--){
printf("%d",bnum[i]);
}
printf("\nB'+ 1 = ");
for(i = 4; i>= 0; i--){
printf("%d",bcomp[i]);
}
printf("\n\n");
for(i=0;i<5;i++){
if(anum[i] == q){
printf("\n-->");
arshift();
q = anum[i];
}
else if(anum[i] == 1 && q == 0){
printf("\n-->");
printf("\nSUB B: ");
arshift();
q = anum[i];
}
else{
printf("\n-->");
arshift();
q = anum[i];
}
}
printf("\nProduct is = ");
for(i = 4; i>= 0; i--){
printf("%d",pro[i]);
}
for(i = 4; i>= 0; i--){
printf("%d",anumcp[i]);
}
}
```

#### Execution:

```Input:
5 4

Output:
BOOTH'S MULTIPLICATION ALGORITHM:

Enter two numbers to multiply:
Both must be less than 16
Enter A: Enter B:
Expected product = 20

Binary Equivalents are:
A = 00101
B = 00100
B'+ 1 = 11100

-->
SUB B: 11100:00101
AR-SHIFT: 11110:00010
-->
AR-SHIFT: 00001:00001
-->
SUB B: 11101:00001
AR-SHIFT: 11110:10000
-->