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

by

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[5]={1,0,0,0,0};
int anum[5]={0},anumcp[5] ={0},bnum[5]={0};
int acomp[5]={0},bcomp[5]={0},pro[5]={0},res[5]={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;
}
}
}
void add(int num[]){
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[4], temp2 = pro[0],i;
for(i = 1; i <5  ; i++){
pro[i-1] = pro[i];
}
pro[4] = temp;
for(i = 1; i < 5  ; i++){
anumcp[i-1] = anumcp[i];
}
anumcp[4] = 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: ");
add(bcomp);
arshift();
q = anum[i];
}
else{
printf("\n-->");
printf("\nADD B: ");
add(bnum);
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
-->
ADD B: 00010:00010
AR-SHIFT: 00001:00001
-->
SUB B: 11101:00001
AR-SHIFT: 11110:10000
-->
ADD B: 00010:10000
AR-SHIFT: 00001:01000
-->
AR-SHIFT: 00000:10100
Product is = 0000010100

Result:

Thus the Program for Booth’s multiplication was executed Successfully.

Leave a Comment