Your Ad Here

Tuesday, January 22, 2008

Non - Restoring Division

/* C Program For Implementation Of Non - Restoring Division */

#include< stdio.h>
#include< conio.h>

int a[5]={0,0,0,0,0},q[4],b[5],b2c[5];

comp()
{
int i=4;
do
{
b2c[i]=b[i];
i--;
}while(b[i+1]!=1);
while(i>=0)
{
b2c[i]=(b[i]+1)%2;
i--;
}
printf("\n\tB's complement:");
for(i=0;i< 5;i++)
printf("%d",b2c[i]);
printf("\n");
}


nonresdiv()
{
shiftleft();
if(a[0]==0)
a_minus_b();
else
a_plus_b();
q[3]=(a[0]+1)%2;
}

shiftleft()
{
int i;
for(i=0;i< 4;i++)
a[i]=a[i+1];
a[4]=q[0];
for(i=0;i< 3;i++)
q[i]=q[i+1];
}

a_minus_b()
{
int i,carry=0,sum=0;
for(i=4;i>=0;i--)
{
sum=(a[i]+b2c[i]+carry);
a[i]=sum%2;
carry=sum/2;
}
}

a_plus_b()
{
int i,carry=0,sum=0;
for(i=4;i>=0;i--)
{
sum=(a[i]+b[i]+carry);
a[i]=sum%2;
carry=sum/2;
}
}


void main()
{
int i,j,k;
clrscr();
printf("Enter dividend in binary form\t: ");
for(i=0;i< 4;i++)
scanf("%d",&q[i]);
printf("Enter divisor in binary form\t: ");
for(i=0;i< 5;i++)
scanf("%d",&b[i]);
comp();
printf("\n\t[A]\t[M]\n");
for(i=0;i< 4;i++)
{
nonresdiv();
printf("\t");
for(j=0;j< 5;j++)
printf("%d",a[j]);
printf("\t");
for(k=0;k< 4;k++)
printf("%d",q[k]);
printf("\n");
}
if(a[0]==1)
a_plus_b();printf("\t");
for(j=0;j< 5;j++)
printf("%d",a[j]);
printf("\t");
for(k=0;k< 4;k++)
printf("%d",q[k]);
printf("\n");
printf("\n\tThe Quotient Is\t: ");
for(k=0;k< 4;k++)
printf("%d",q[k]);
printf("\n\tThe Remainder Is\t: ");
for(j=0;j< 5;j++)
printf("%d",a[j]);
getch();
}

/********************** OUTPUT ****************
Enter dividend in binary form : 0 1 0 1
Enter divisor in binary form : 0 0 0 1 1

B's complement:11101

[A] [M]
11101 1010
11110 0100
11111 1000
00010 0001
00010 0001

The Quotient Is : 0001
The Remainder Is : 00010

Enter dividend in binary form : 1 1 1 1
Enter divisor in binary form : 0 0 1 1 1

B's complement:11001

[A] [M]
11010 1110
11100 1100
00000 1001
11010 0010
00001 0010

The Quotient Is : 0010
The Remainder Is : 00001


Enter dividend in binary form : 1 1 0 1
Enter divisor in binary form : 0 0 0 1 1

B's complement:11101

[A] [M]
11110 1010
00000 0101
11101 1010
11110 0100
00001 0100

The Quotient Is : 0100
The Remainder Is : 00001
*/

3 comments:

Anonymous said...

Terrible code at conveying what is going on, it may work but I have to wonder why.
In the world of work this sort of programming just gets binned.

Remy D said...

It is illustrative, if hopelessly inefficient. hits the division unit an awful lot for code purporting to show how a division is done. (between 21 and 25 times!)

Might make more sense to store the numbers in just one int rather than arrays of them.
Probably done to avoid the issues of selecting out individual bits with C - something it's not good at, it's "hands" can only grip numbers at least a byte or larger. It works, but it isn't all that clear.

Eg, complement is done with a tricky (efficient, which is counter to the purpose) sequential algorithm, when the standard "invert, then add one" would have been clearer.
Also, keeps using, "add one, then get the remainder of a division by 2" to invert bits.
something like b2c[i]=b[i]?0:1; is clearer, assuming you do know C.

Adding each bit also uses _2_ division operations.

Also, the code is very poorly commented.

Just implementing a non-restoring division on int's or char's using perhaps a union to combine two char's into a short for the left shift, then just adding or subtracting and looping to get the result, as chars would have been shorter and much more readable.

mumunicomengg said...

Program for Implementation of Non-Restoring dision

http://mumunicomenggprog.blogspot.com/p/programs-for-coa.html

Your Ad Here