**Booth’s Multiplication Algorithm **is used to multiplication of two signed binary numbers. This algorithm was invented by Andrew Donald Booth in 1950. All it includes are addition of binary numbers and right shift operation.

Let us discuss a C program that calculates and displays multiplication of two signed binary numbers using Booth’s Algorithm in tabular form.

In the discussion let us first know Booth’s Algorithm.

For a given two numbers ‘q’ and ‘m’. Convert them to binary ‘Q’ and ‘M’. Also find 2’s compliment of ‘M’ as we need to use the value of -M.(Note that in signed binary -M is 2’s compliment of M).

Draw a table with 4 columns. First step no., second P(the value in accumulator), third multiplicand(Q), and fourth is previous state(Q-1).

Booth’s Algorithm has ‘N’ number of steps where ‘N’ is size of binary numbers that are being multiplied.(Remember that we need to take them in same size. If they are not same, make them zero by adding leading zeros or ones according to the number).

Set step no. to 0. Set P initially to zero. Fill in the Q register value equal to multiplicand. And Q-1 column as zero.

Now follow the following steps on comparing values of LSB of Q an Q-1.

Q – Q-1 Action

0 – 0 Right Shift.

0 – 1 Add M to P and Right Shift.

1 – 0 Add -M to P and Right Shift.

1 – 1 Right Shift.

The final product is combination of P-Q in signed binary number.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
void rightShift();
int main()
{
printf("\n");
printf(" BOOTH's Algorithm\n"); //Printing out Booth's Algorithm for multiplication of signed binary numbers
printf("0-0 Right Shift.\n");
printf("0-1 Add M to P. Right Shift.\n");
printf("1-0 Add -M to P. Right Shift.\n");
printf("1-1 Right Shift.\n");
printf("\n");
printf("Enter two numbers that are to be multiplied : ");//taking two numbers as inputs
int a,b;
scanf("%d %d",&a,&b);
int ap=a,bp=b;
if(ap<0) //checking if any of the inputs are -ve
ap*=-1;
if(bp<0) bp*=-1; if(bp>ap) //taking greater VALUE as multiplicand
{
ap=bp+ap-(bp=ap);
a=b+a-(b=a);
}
int t1=ap,t2=bp;
int ab[35]={};
int bb[35]={};
int i=0;
while(t1>0)
{
ab[i]=t1%2;
i++;
t1/=2;
}
ab[i]=0;
int j=0;
while(t2>0)
{
bb[j]=t2%2;
j++;
t2/=2;
}
while(j<=i) //equating bits to previous(ab) binary number(ab will either be larger or equal to bb).
bb[j++]=0;
int nb=i+1; //nb is number of bits
i=0;j=0;
while(i<nb/2) //converting VALUES to binary
{
ab[i]=ab[nb-i-1]+ab[i]-(ab[nb-i-1]=ab[i]);
i++;
}
i=0;
while(i<nb/2) { bb[i]=bb[nb-i-1]+bb[i]-(bb[nb-i-1]=bb[i]); i++; } int x[35]={0}; int y[35]={0}; i=0; if(a>=0) //taking actual binary numbers
{ //x is multiplicand and y is multiplier
while(i<nb)
x[i]=ab[i+++1];
}
else //2's complimant conversion
{
while(i<nb) { if(ab[i]==0) x[i]=1; else x[i]=0; i++; } i=1; x[nb-i]++; while(x[nb-i]==2) { x[nb-i]=0; i++; x[nb-i]++; } } i=0; if(b>=0)
{
while(i<nb)
y[i]=bb[i+++1];
}
else //2's complimant conversion
{
while(i<nb) { if(bb[i]==0) y[i]=1; else y[i]=0; i++; } i=1; y[nb-i]++; while(y[nb-i]==2) { y[nb-i]=0; i++; y[nb-i]++; } } printf("\n"); //output starts here printf("Multiplicand (Q) %d -> ",a);
i=0;
while(i<nb) printf("%d",x[i++]); printf(" and Multiplier (M) %d -> ",b);
i=0;
while(i<nb)
printf("%d",y[i++]);
printf("\n");
i=0;
int ym[35]={0}; //calculating -ve of multiplier. we use that in Booth's algorithm. ym=-y .
if(b<0)
{
while(i<nb)
ym[i]=bb[i+++1];
}
else
{
while(i<nb) { if(bb[i]==0) ym[i]=1; else ym[i]=0; i++; } i=1; ym[nb-i]++; while(ym[nb-i]==2) { ym[nb-i]=0; i++; ym[nb-i]++; } } printf("we use -(M) i.e. %d -> ",-b);
i=0;
while(i<nb)
printf("%d",ym[i++]);
printf("\n");
int q0=0;
int p[35]={0}; //p here is value that is stored in accumulator. initially set to zero.
int steps=nb;
printf("\n");
printf("Step No. "); //title of columns.
i=0;
while(i<nb)
{
if(i*2==nb || i*2==nb-1)
printf("P");
else
printf(" ");
i++;
}
printf(" ");
i=0;
while(i<nb)
{
if(i*2==nb || i*2==nb-1)
printf("Q");
else
printf(" ");
i++;
}
printf(" Q-1");
printf("\n");
j=0;
while(steps--) //counting down steps.
{ // Booth's algorithm has steps that is equal to no. of bits in multiplier or multiplicand
printf("%d ",j++);
i=0;
while(i<nb)
printf("%d",p[i++]);
printf(" ");
i=0;
while(i<nb)
printf("%d",x[i++]);
printf(" ");
printf("%d\n",q0);
if(x[nb-1]==0 && q0==0) //0-0 condition
{
q0=x[nb-1];
rightShift(p,x,nb);
}
else if(x[nb-1]==0 && q0==1) //0-1 condition
{
printf(" + ");
i=0;
while(i<nb)
printf("%d",y[i++]);
i=0;
while(i<nb)
{
p[nb-i-1]+=y[nb-i-1];
if(p[nb-i-1]==2)
{
p[nb-i-1]=0;
if(nb-i-1!=0)
p[nb-i-2]++;
}
if(p[nb-i-1]==3)
{
p[nb-i-1]=1;
if(nb-i-1!=0)
p[nb-i-2]++;
}
i++;
}
printf("\n ");
i=0;
while(i<nb)
printf("%d",p[i++]);
printf("\n");
q0=x[nb-1];
rightShift(p,x,nb);
}
else if(x[nb-1]==1 && q0==0) //1-0 condition
{
printf(" + ");
i=0;
while(i<nb)
printf("%d",ym[i++]);
i=0;
while(i<nb)
{
p[nb-i-1]+=ym[nb-i-1];
if(p[nb-i-1]==2)
{
p[nb-i-1]=0;
if(nb-i-1!=0)
p[nb-i-2]++;
}
if(p[nb-i-1]==3)
{
p[nb-i-1]=1;
if(nb-i-1!=0)
p[nb-i-2]++;
}
i++;
}
printf("\n ");
i=0;
while(i<nb)
printf("%d",p[i++]);
printf("\n");
q0=x[nb-1];
rightShift(p,x,nb);
}
else if(x[nb-1]==1 && q0==1) //1-1 condition
{
q0=x[nb-1];
rightShift(p,x,nb);
}
}
printf("%d ",j);
i=0;
while(i<nb)
printf("%d",p[i++]);
printf(" ");
i=0;
while(i<nb)
printf("%d",x[i++]);
printf(" ");
printf("%d\n",q0);
printf("\n");
printf("Product in signed binary number is : "); //printing out the product. it will be in signed binary representation
i=0;
while(i<nb)
printf("%d",p[i++]);
i=0;
printf(" ");
while(i<nb)
printf("%d",x[i++]);
printf("\n\n");
return 0;
}
void rightShift(int p[],int x[],int nb)
{
int i=0;
while(nb-i-1)
{
x[nb-i-1]=x[nb-i-2];
i++;
}
x[0]=p[nb-1];
i=0;
while(nb-i-1)
{
p[nb-i-1]=p[nb-i-2];
i++;
}
}

The result thus is combination of binary numbers in P and Q.

A brief explanation of what is done in the program:

Taken two decimal numbers, converted them to binary numbers, also found out 2’s compliment of multiplier(M). On each step comparing the values of LSB of Q and Q-1 on following steps as in Booth’s Algorithm completed all N steps. Note, after N steps, the value of Q will be same as when started. Right Shifts are to be done in such a way that MSB of P remains same as previous, LSB of P is MSB of Q, LSB of Q is Q-1 for new state.

Thus on completion of N steps, we get the product.

Example: for multiplying -5 and 10, above code gives following output

BOOTH's Algorithm
0-0 Right Shift.
0-1 Add M to P. Right Shift.
1-0 Add -M to P. Right Shift.
1-1 Right Shift.
Enter two numbers that are to be multiplied : -5 10
Multiplicand (Q) 10 -> 01010 and Multiplier (M) -5 -> 11011
we use -(M) i.e. 5 -> 00101
Step No. P Q Q-1
0 00000 01010 0
1 00000 00101 0
+ 00101
00101
2 00010 10010 1
+ 11011
11101
3 11110 11001 0
+ 00101
00011
4 00001 11100 1
+ 11011
11100
5 11110 01110 0
Product in signed binary number is : 11110 01110