C program of booth’s multiplication algorithm : **Booth’s multiplication algorithm**is a multiplication algorithm that multiplies two signed binary numbers 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**:

- 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).- A: Fill the most significant (leftmost) bits with the value of
**a**. Fill the remaining (*y*+ 1) bits with zeros. - S: Fill the most significant bits with the value of (−
**a**) in two’s complement notation. Fill the remaining (*y*+ 1) bits with zeros. - 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.

- A: Fill the most significant (leftmost) bits with the value of
- Determine the two least significant (rightmost) bits of
*P*.- If they are 01, find the value of
*P*+*A*. Ignore any overflow. - If they are 10, find the value of
*P*+*S*. Ignore any overflow. - If they are 00, do nothing. Use
*P*directly in the next step. - If they are 11, do nothing. Use
*P*directly in the next step.

- If they are 01, find the value of
- Arithmetically shift the value obtained in the 2nd step by a single place to the right. Let
*P*now equal this new value. - Repeat steps 2 and 3 until they have been done
*y*times. - 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 algorithms in C 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); } void add(int *a,int *b) { 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[4]={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]; add(arr,c); } 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[0] = x; } int main() { int q=0,i,j,a,b,A[4]={0,0,0,0},C[4]={0,0,0,1},C1[8]={0,0,0,0,0,0,0,1}; int s=0,z=0,Q[4],M[4],temp,temp1[4],ans[8],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[3]==0)&&(q==1)) { printf("\n A:=A+M \t\t"); add(A,M); 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[3]==1)&&(q==0)) { printf("\n A:=A-M \t\t"); for(i=0;i<4;i++) temp1[i] = 1-M[i]; add(temp1,C); add(A,temp1); 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[3]; q = Q[3]; rshift(A[0],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 C program of Booth’s multiplication algorithm. If you have any issues with code or its logic, feel free to contact us in form of comments.

MuscleGurlaaOctober 29, 2012 at 1:41 am -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]

vaibhavApril 7, 2014 at 10:31 am -Absolutely wrong code.Piece of crap.

hcg dropsJuly 8, 2014 at 4:45 pm -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!

pinterestOctober 12, 2014 at 9:43 am -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.