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).

Recommended Read : C program for adding two Binary Numbers

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
  • add_bin(): Addition of two signed binary numbers

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("");  }

add_bin()

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[0] = 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[0] = q0; q0 = lastOfy; }

Output:

C program to implement booth's algorithm

Thank you for reading.

Tweet your queries and feedback to @PsychoCodes or leave a message on our Facebook page. You can also comment your questions below.

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

If you like this article, then please share it and help us grow.


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

Binary Tree in Python
02 September 2018

Image Sharpening by High Pass Filter using Python and OpenCV
17 August 2018

Explaining Register variables in C with examples
17 August 2018

C program to generate all combinations of N-Bit Binary String
10 July 2018

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

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