Booth’s Algorithm

#include<stdio.h>

int no_dig;

void dectobin(int a,int aa[])
{
    int i=0;
    no_dig=0;
    while(a!=0)
    {
        aa[i]=a%2;
        i++;
        no_dig++;
        a=a/2;
    }
}

void comp_2(int aa[],int m[])
{
    int i,flag=0;
    for(i=0;i<no_dig;i++)
    {
	if(flag==1)
	{
	    if(aa[i]==0)
		m[i]=1;
	    else
		m[i]=0;
	}
	else if(flag==0&&aa[i]==1)
	{
	    flag=1;
	    m[i]=aa[i];
	}
	else
	    m[i]=0;
    }
}

void add(int acc[],int m[])
{
    int carry=0,i;
    for(i=0;i<no_dig;i++)
    {
        acc[i]=acc[i]+m[i]+carry;
        carry=0;
        if(acc[i]==2)
        {
            acc[i]=0;
            carry=1;
        }
        if(acc[i]==3)
        {
            acc[i]=1;
            carry=1;
        }
    }
}

void shift(int acc[],int q[],int *q1)
{
    int t1,t2,i;
    t1=acc[0];
    t2=q[0];
    for(i=0;i<no_dig-1;i++)
    {
        acc[i]=acc[i+1];
    }
    for(i=0;i<no_dig-1;i++)
    {
        q[i]=q[i+1];
    }
    q[no_dig-1]=t1;
    *q1=t2;
}

void main()
{
    int a,b,acc[10],aa[10],bb[10],m1[10],m2[10],q1=0,q[10],i=0,j;
    for(i=0;i<10;i++)
    {
        aa[i]=0;
        acc[i]=0;
        bb[i]=0;
        m1[i]=0;
        m2[i]=0;
        q[i]=0;
    }
    printf("Enter 2 numbers ");
    scanf("%d%d",&a,&b);
    if(a<b)
    {
        dectobin(a,aa);
        dectobin(b,bb);
    }
    else
    {
        dectobin(b,bb);
        dectobin(a,aa);
    }
    no_dig++;
    for(i=0;i<no_dig;i++)
    {
        m1[i]=aa[i];
    }
    comp_2(aa,m2);
    for(i=0;i<no_dig;i++)
    {
        q[i]=bb[i];
    }
    printf("\nBooth's Steps :\n");
    for(i=0;i<no_dig;i++)
    {
        if(q[0]==0&&q1==1)
        {
            add(acc,m1);
        }
        else if(q[0]==1&&q1==0)
        {
            add(acc,m2);
        }
        shift(acc,q,&q1);
        for(j=no_dig-1;j>=0;j--)
            printf("%d",acc[j]);
        printf(" ");
        for(j=no_dig-1;j>=0;j--)
            printf("%d",q[j]);
        printf(" ");
        printf("%d",q1);
        printf("\n");
    }
    printf("\nMultiplication is\n");
    for(i=no_dig-1;i>=0;i--)
        printf("%d",acc[i]);
    for(i=no_dig-1;i>=0;i--)
        printf("%d",q[i]);
}

/*Output
Enter 2 numbers 26 6

Booth’s Steps :
000000 000011 0
110011 000001 1
111001 100000 1
001001 110000 0
000100 111000 0
000010 011100 0

Multiplication is
000010011100
*/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s