# C program to Implement Booth’s Algorithm-Booth’s Algorithm in C

Booth’s Algorithm is a multiplication algorithm that multiplies two signed binary numbers in two’s complement notation. The algorithm was invented by Andrew Donald Booth in 1950 while doing research on crystallography at Birkbeck College in Bloomsbury, London. Booth used desk calculators that were faster at shifting than adding and created the algorithm to increase their speed. Booth’s algorithm is of interest in the study of computer architecture(definition source).

In this tutorial we will learn how to make a C program to implement the Booth’s algoritm before going through the code we recommend you to learn the algorithm first(if you want us to explain the algorithm comment in the comments section of this article).

We are going to create four functions

• take_bin() : for taking binary input
• print_bin() : for printing the binary number
• arth_shift(): for performing the arithematic shift

Lets see the code for each of the function

take_bin()

``int take_bin(int x[]){ int i; for(i=0;i<COUNT;i++){ scanf("\%d",&x[i]); }  } ``

print_bin()

``int print_bin(int x[]){ int i; for(i=0;i<COUNT;i++){ printf("\%d",x[i]); } printf("");  }``

To learn binary addition you can refer our article : C program for adding two Binary Numbers

``int add_bin(int x[],int y[]){ int i,carry=0; for(i = COUNT-1;i>=0;i--){ if(x[i]==0 && y[i]==0 && carry==0){ a[i] = 0; carry = 0; } else if(x[i]==0 && y[i]==0 && carry==1){                       a[i] = 1;                       carry = 0;               } else if(((x[i]==1 && y[i]==0)||(x[i]==0 && y[i]==1)) && carry==0){ a[i] = 1; carry = 0; } else if(((x[i]==1 && y[i]==0)||(x[i]==0 && y[i]==1)) && carry==1){                       a[i] = 0;                       carry = 1;               } else if(x[i]==1 && y[i]==1 && carry==0){ a[i] = 0; carry = 1; } else if(x[i]==1 && y[i]==1 && carry==1){                       a[i] = 1;                       carry = 1;               } }  } ``

arth_shift()

``int arth_shift(int x[],int y[]){ int i,lastOfy; lastOfy = y[COUNT-1]; q0 = x[COUNT-1];    for(i=3;i>=1;i--){       x[i] = x[i-1];   } for(i=3;i>=1;i--){       y[i] = y[i-1];   } y = q0; q0 = lastOfy; }``

Now we have defined all our functions, now its time to put the things together so lets write the full code for the Booths algorithm

C program for Booth’s Algorithm

``#include<stdio.h> #define COUNT 4     // change the value to change the number of bits int q0=0; int a[COUNT] = {0,0,0,0}; int take_bin(int x[]); int print_bin(int x[]); int add_bin(int x[],int y[]); int arth_shift(int x[],int y[]); int compm[COUNT],m[COUNT],q[COUNT]; int main(){ int i; printf("Enter M (space between each bit): "); take_bin(m); printf("Enter -M (space between each bit): "); take_bin(compm); printf("Enter Q (space between each bit): "); take_bin(q); for(i=0;i<COUNT;i++){ if(q[COUNT-1]==0 && q0==1){ add_bin(a,compm); arth_shift(a,q); } else if(q[COUNT-1]==1 && q0==0){ add_bin(a,m); arth_shift(a,q); } else{ arth_shift(a,q); } printf("Round \%d ",i); printf("A------>"); print_bin(a); printf("Q------>"); print_bin(q); } return 0; } int take_bin(int x[]){ int i; for(i=0;i<COUNT;i++){ scanf("\%d",&x[i]); }  } int print_bin(int x[]){ int i; for(i=0;i<COUNT;i++){ printf("\%d",x[i]); } printf("");  } int add_bin(int x[],int y[]){ int i,carry=0; for(i = COUNT-1;i>=0;i--){ if(x[i]==0 && y[i]==0 && carry==0){ a[i] = 0; carry = 0; } else if(x[i]==0 && y[i]==0 && carry==1){                       a[i] = 1;                       carry = 0;               } else if(((x[i]==1 && y[i]==0)||(x[i]==0 && y[i]==1)) && carry==0){ a[i] = 1; carry = 0; } else if(((x[i]==1 && y[i]==0)||(x[i]==0 && y[i]==1)) && carry==1){                       a[i] = 0;                       carry = 1;               } else if(x[i]==1 && y[i]==1 && carry==0){ a[i] = 0; carry = 1; } else if(x[i]==1 && y[i]==1 && carry==1){                       a[i] = 1;                       carry = 1;               } }  } int arth_shift(int x[],int y[]){ int i,lastOfy; lastOfy = y[COUNT-1]; q0 = x[COUNT-1];    for(i=3;i>=1;i--){       x[i] = x[i-1];   } for(i=3;i>=1;i--){       y[i] = y[i-1];   } y = q0; q0 = lastOfy; }``

Output: Also, don’t forget to subscribe to our Newsletter.

Preorder and Postorder Traversal of binary tree in Python
02 September 2018

Binary Tree in Python
02 September 2018

Explaining Register variables in C with examples
17 August 2018

Data Autosave System using PHP, MySQL and AJAX
06 July 2018

Понравилась статья? Поделиться с друзьями: