C program of Booth’s multiplication algorithm

# C program of Booth’s multiplication algorithm

13387
5
SHARE

C program of booth’s multiplication algorithm : Booth’s multiplication algorithmis a multiplication algorithm that multiplies two signed binary in two’s complement notation.

(source : Wikipedia)  Booth’s algorithm can be implemented by repeatedly adding (with ordinary unsigned binary addition) one of two predetermined values A and S to a product P, then performing a rightward arithmetic shift on P. Let m and r be the multiplicand and multiplier, respectively; and let x and y represent the number of bits in a and b.

For more clear picture, say we wish to multiply:

3 × (−4), with a = 3 and b = −4, and x = 4 and y= 4 then :

• a = 0011, -a = 1101, b = 1100
• A = 0011 0000 0
• S = 1101 0000 0
• P = 0000 1100 0

Now lets check Booth’s Standard Algorithm Implementation:

1. Determine the values of A and S, and the initial value of P. All of these numbers should have a length equal to (x + y + 1).
1. A: Fill the most significant (leftmost) bits with the value of a. Fill the remaining (y + 1) bits with zeros.
2. S: Fill the most significant bits with the value of (−a) in two’s complement notation. Fill the remaining (y + 1) bits with zeros.
3. P: Fill the most significant x bits with zeros. To the right of this, append the value of b. Fill the least significant (rightmost) bit with a zero.
2. Determine the two least significant (rightmost) bits of P.
1. If they are 01, find the value of P + A. Ignore any overflow.
2. If they are 10, find the value of P + S. Ignore any overflow.
3. If they are 00, do nothing. Use P directly in the next step.
4. If they are 11, do nothing. Use P directly in the next step.
3. Arithmetically shift the value obtained in the 2nd step by a single place to the right. Let P now equal this new value.
4. Repeat steps 2 and 3 until they have been done y times.
5. Drop the least significant (rightmost) bit from P. This is the product of a and b.

Now friends let us see how to implement Booth’s multiplication in C. I have written a sample code on Booth’s multiplication which accepts numbers from range -7 to 7 and displays the binary equivalents and complete booth operations in the tabular form and then the output of multiplication in both binary and decimal form.

### C program of Booth’s Multiplication Algorithm :

```#include<stdio.h>
#include<conio.h>
#include<process.h>
#include<math.h>

int get(int a)
{
char ch='B';
int flag=0;
if(a==1)
ch='A';
do
{
printf("ENTER VALUE OF %c: ",ch);
scanf("%d",&a);
if(a< 0)
{
a = a * -1;
flag = 1;
}
if(8<=a)
printf("\n\t!INVALID NUMBER.ENTER VALUE (-8 < A < 8)!\n");
}while(8<=a);
if(flag)
a = a *-1;
return(a);
}

{
int x,i,c=0;
for(i=3;i>=0;i--)
{
x=a[i];
a[i]=c^x^b[i];
if(((c==1)&&(x==1))||((x==1)&&(b[i]==1))||((b[i]==1)&&(c==1)))
c = 1;
else
c = 0;
}
}

void binary(int x,int*arr)
{
int i,p=x,c={0,0,0,1};
for(i=0;i<4;i++)
arr[i] = 0;
if(x < 0)
x = x *-1;
i = 3;
do
{
arr[i]=x%2;
x = x/2;
i--;
}while(x!=0);
if(p<0)
{
for(i=0;i<4;i++)
arr[i]=1-arr[i];
}
printf("\n\nTHE BINARY EQUIVALENT OF %d IS : ",p);
for(i=0;i<4;i++)
printf("%d",arr[i]);
}

void rshift(int x,int *y)
{
int i;
for(i=3;i>0;i--)
y[i] = y[i-1];
y = x;
}

int main()
{
int q=0,i,j,a,b,A={0,0,0,0},C={0,0,0,1},C1={0,0,0,0,0,0,0,1};
int s=0,z=0,Q,M,temp,temp1,ans,y,x=0,c=0;
printf("----------------------------------------------------------------------\n");
printf("-------------------made by C code champ ------------------------------\n");
printf("----------------------------------------------------------------------\n");
printf("\n\n\t\tBOOTHS MULTIPLICATION ALGORITHM \n");
printf("\n----------------------------------------------------\n");
a = get(1);
b=get(0);
printf("\n---------------------------------------------------\n");
binary(a,M);
binary(b,Q);
printf("\n---------------------------------------------------\n");
printf("OPERATION\t\t A\t Q\tQ'\t M");
printf("\n\n INITIAL\t\t");
for(i=0;i<4;i++)
printf("%d",A[i]);
printf("\t");
for(i=0;i<4;i++)
printf("%d",Q[i]);
printf("\t");
printf("%d\t",q);
for(i=0;i<4;i++)
printf("%d",M[i]);
for(j=0;j<4;j++)
{
if((Q==0)&&(q==1))
{
printf("\n A:=A+M \t\t");
for(i=0;i< 4;i++)
printf("%d",A[i]);
printf("\t");
for(i=0;i< 4;i++)
printf("%d",Q[i]);
printf("\t%d\t",q);
for(i=0;i< 4;i++)
printf("%d",M[i]);
}
if((Q==1)&&(q==0))
{
printf("\n A:=A-M \t\t");
for(i=0;i<4;i++)
temp1[i] = 1-M[i];
for(i=0;i< 4;i++)
printf("%d",A[i]);
printf("\t");
for(i=0;i< 4;i++)
printf("%d",Q[i]);
printf("\t%d\t",q);
for(i=0;i< 4;i++)
printf("%d",M[i]);
}
printf("\n Shift \t\t\t");
y = A;
q = Q;
rshift(A,A);
rshift(y,Q);
for(i=0;i<4;i++)
printf("%d",A[i]);
printf("\t");
for(i=0;i<4;i++)
printf("%d",Q[i]);
printf("\t");
printf("%d\t",q);
for(i=0;i<4;i++)
printf("%d",M[i]);
}
printf("\n\n---------------------------------------------------\n");
printf("\nTHE ANSWER IN BINARY IS : ");
for(i=0;i<4;i++)
ans[i]=A[i];
for(i=0;i<4;i++)
ans[i+4]=Q[i];
if(((a< 0)&&(b>0))||((a>0)&&(b< 0)))
{
for(i=0;i<8;i++)
ans[i]=1-ans[i];
for(i=7;i>=0;i--)
{
x = ans[i];
ans[i]=c^x^C1[i];
if(((c==1)&&(x==1))||((x==1)&&(C1[i]==1))||((C1[i]==1)&&(c==1)))
c=1;
else
c=0;
}
}
for(i=0;i<8;i++)
printf("%d",ans[i]);
for(i=7;i>=0;i--)
{
s = s + (pow(2,z) * ans[i]);
z = z+1;
}
if(((a< 0)&&(b>0))||((a>0)&&(b< 0)))
printf("\nTHE ANSWER IN DECIMAL IS : -%d\n",s);
else
printf("\nTHE ANSWER IN DECIMAL IS : %d\n",s);
getch();
}```

We hope you all have enjoyed the of Booth’s multiplication algorithm. If you have any issues with code or its logic, feel free to contact us in form of comments.

SHARE
Previous articleC program of Bubble sort using linked list
Well, I am software programmer and love to code. My hobbies is to do Hacking, Coding, Blogging, Web Designing and playing online games. Feel free to contact me at shiviskingg@gmail.com or lokesh@hackingloops.com

1. Have you ever considered about including a little bit more than just your articles? I mean, what you say is fundamental and everything. But think of if you added some great visuals or videos to give your posts more, “pop”! Your content is excellent but with images and video clips, this website could undeniably be one of the best in its field. Fantastic blog! [url=http://www.youtube.com/watch?v=WwybpbJIDNg]muscle building workouts for men[/url]

2. Howdy! Quick question that’s entirely off topic.
Do you know how to make your site mobile friendly?
My web site looks weird when browsing from my iphone 4.
I’m trying to find a theme or plugin that might be able to resolve
this issue. If you have any recommendations, please share.
Cheers!

3. First, Pinterest users should have more creative options to customize the home page.

The following are four prime reasons why you should be using
Pinterest, including examples of practical applications:.
For example, if your food business is dedicated to gourmet party appetizers
your bio might be as simple as “Gourmet appetizers delivered right to your door.