C program of Booth’s multiplication algorithm

Mr Coder August 23, 2012 3




C program of booth’s multiplication algorithm : Booth’s multiplication algorithmis 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:

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

3 Comments »

  1. MuscleGurlaa October 29, 2012 at 1:41 am - Reply

    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. vaibhav April 7, 2014 at 10:31 am - Reply

    Absolutely wrong code.Piece of crap.

  3. hcg drops July 8, 2014 at 4:45 pm - Reply

    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!

Leave A Response »