PDA

View Full Version : Binary Division:

DaNYer
Dec 9, 2003, 17:56
Binary Division Restoring Algorithm

// Division is the process of repeated subtraction.
// Binary division algorithm works from the high order digits
// to the low order digits and generates a quotient (division result)
// with each step. The division algorithm is divided into two steps:
//
// 1. Shift the upper bits of the dividend (the number we are dividing into)
// into the remainder.
//
// 2.Subtract the divisor from the value in the remainder. The high order bit
// of the result become a bit of the quotient (division result).



#include <stdio.h>
#include <stdlib.h>

void load(int*, int*, int*);
void display(int*, int*, int*);
void compute(int*, int*, int*);
void adder(int*, int*);
void negate(int*);

void main()
{
int i;
int DIVISOR [5];
int REMAINDER [5];
int DIV_QUOT [4]; // DIVIDEND - QUOTIENT

//initialising registers with data
load(DIVISOR, REMAINDER, DIV_QUOT);

//Decorations.
printf(" DIVISOR |\t REMAINDER\t DIVIDEND/QUOTIENT");
printf("\n --------|----------------");
printf("---------------------------\n");

display(DIVISOR, REMAINDER, DIV_QUOT); //general display
printf("\n --------|----------------");
printf("---------------------------\n");
//Done with decorations.

//computation
for (i=0; i<4; i++)
{
compute(DIVISOR, REMAINDER, DIV_QUOT); //compute 1st bit
printf("\n --------|----------------");
printf("---------------------------\n");
}
}





///////////////////////////////////////////////////////
// Computation
void compute(int DIVISOR[], int REMAINDER[], int DIV_QUOT[])
{
int DIVISOR_Copy [5];
bool neg;

REMAINDER[1] = REMAINDER[2];
REMAINDER[2] = REMAINDER[3];
REMAINDER[3] = REMAINDER[4];
REMAINDER[4] = DIV_QUOT[0];
DIV_QUOT[0] = DIV_QUOT[1];
DIV_QUOT[1] = DIV_QUOT[2];
DIV_QUOT[2] = DIV_QUOT[3];
DIV_QUOT[3] = 888; //flag to put "?" sign

display(DIVISOR, REMAINDER, DIV_QUOT); //display
printf(" | <--- Shifting left...\n");


// NOW LETS DETERMINE THE STATUS OF DIV_QUOT[3]
// TO DO SO.... SUBSTRACT. (REMAINDER - DIVISOR) AND SEE
// IF NEGATIVE, IT IS 0; AND RESTORE REMAINDER
// IF POSITIVE IT IS 1 AND DO NOT RESTORE REMAINDER.

/////////////////////////
// SUBSTRACT operation HERE.
// REMAINDER - DIVISOR = ?
//
// first lets create and negate DIVISOR_Copy
// an image of DIVISOR

DIVISOR_Copy[0] = DIVISOR[0];
DIVISOR_Copy[1] = DIVISOR[1];
DIVISOR_Copy[2] = DIVISOR[2];
DIVISOR_Copy[3] = DIVISOR[3];
DIVISOR_Copy[4] = DIVISOR[4];

negate(DIVISOR_Copy);

adder(REMAINDER, DIVISOR_Copy); // Addition (actually substraction)

if (REMAINDER[0] == 1) // Checking control bit.
// (overflow or neg)
neg = 1; /// Negative
else
neg = 0; /// Positive

display(DIVISOR, REMAINDER, DIV_QUOT); //display

if (neg) // if the number was negative,
// restore REMAINDER and assign 0 to D[3]
{
adder(REMAINDER, DIVISOR); //Restoration
DIV_QUOT[3] = 0;
printf(" | NEGATIVE. ? = 0\n");
}
else
{
DIV_QUOT[3] = 1;
printf(" | POSITIVE. ? = 1\n");
}
display(DIVISOR, REMAINDER, DIV_QUOT); //display
}


///////////////////////////////////////////////////////
// Two's compliment.
void negate(int A[])
{
int i;
int ONE[5];
ONE[0] = 0;
ONE[1] = 0;
ONE[2] = 0;
ONE[3] = 0;
ONE[4] = 1;

for (i=0; i<=4; i++)
{
if(A[i] == 1)
A[i] = 0;
else
A[i] = 1;
}
//ADD 1
adder(A, ONE);
}


///////////////////////////////////////////////////////
// 4 bit adder.
void adder(int A[], int B[])
{
int next, i, carry=0;

for (i=4; i>=0; i--) // 4, because we have sign control bit
{
next = 1;
if (A[i]==0 && B[i]==0) //00 case
{
A[i]= carry;
carry = 0;
next = 0;
} // good.

if (next)
if (A[i]==0 && B[i]==1) //01 case - transfer
{
if (carry == 0)
A[i] =1;
else
A[i]=0;
next = 0;
}

if(next)
if (A[i]==1 && B[i]==0) //10 case - transfer
{
if (carry == 0)
A[i] =1;
else
A[i]=0;
next = 0;
}

if(next)
if (A[i]==1 && B[i]==1) //11 case - generate
{
if (carry == 0)
{
A[i] =0;
carry = 1;
}
else
A[i]=1;
next = 0;
}
}
}



///////////////////////////////////////////////////////
//displaying {OK}
void display(int A[], int B[], int C[])
{
int i;
printf(" ");
for(i=1; i<=4; i++)
printf(" %d", A[i]);
printf(" | ");

for(i=1; i<=4; i++)
printf(" %d", B[i]);
printf(" ");

for(i=0; i<=3; i++)
if ((C[i] == 0) || (C[i] == 1))
printf(" %d", C[i]);
else
printf(" ?");
}

///////////////////////////////////////////////////////
//function to load registers with data. {OK}
void load(int A[], int B[], int C[])
{

A[0] = 0;
A[1] = 1; //DIVISOR
A[2] = 0;
A[3] = 0;
A[4] = 0;

B[0] = 0; // !!!!!!SIGN CONTROL BIT!!!!!!
B[1] = 0; // ALL ZEROS
B[2] = 0; // ALL ZEROS
B[3] = 0; // ALL ZEROS
B[4] = 0; // ALL ZEROS


C[0] = 1; //DIVIDEND / QUOT
C[1] = 0;
C[2] = 0;
C[3] = 0;
}







Outputs:



1) 8 / 8 = 1 (Remainder = 0)

DIVISOR | REMAINDER DIVIDEND/QUOTIENT
--------|-------------------------------------------
1 0 0 0 | 0 0 0 0 1 0 0 0
--------|-------------------------------------------
1 0 0 0 | 0 0 0 1 0 0 0 ? | <--- Shifting left...
1 0 0 0 | 1 0 0 1 0 0 0 ? | NEGATIVE. ? = 0
1 0 0 0 | 0 0 0 1 0 0 0 0
--------|-------------------------------------------
1 0 0 0 | 0 0 1 0 0 0 0 ? | <--- Shifting left...
1 0 0 0 | 1 0 1 0 0 0 0 ? | NEGATIVE. ? = 0
1 0 0 0 | 0 0 1 0 0 0 0 0
--------|-------------------------------------------
1 0 0 0 | 0 1 0 0 0 0 0 ? | <--- Shifting left...
1 0 0 0 | 1 1 0 0 0 0 0 ? | NEGATIVE. ? = 0
1 0 0 0 | 0 1 0 0 0 0 0 0
--------|-------------------------------------------
1 0 0 0 | 1 0 0 0 0 0 0 ? | <--- Shifting left...
1 0 0 0 | 0 0 0 0 0 0 0 ? | POSITIVE. ? = 1
1 0 0 0 | 0 0 0 0 0 0 0 1
--------|-------------------------------------------
Press any key to continue



2) 8 / 2 = 4 (Remainder = 0)

DIVISOR | REMAINDER DIVIDEND/QUOTIENT
--------|-------------------------------------------
0 0 1 0 | 0 0 0 0 1 0 0 0
--------|-------------------------------------------
0 0 1 0 | 0 0 0 1 0 0 0 ? | <--- Shifting left...
0 0 1 0 | 1 1 1 1 0 0 0 ? | NEGATIVE. ? = 0
0 0 1 0 | 0 0 0 1 0 0 0 0
--------|-------------------------------------------
0 0 1 0 | 0 0 1 0 0 0 0 ? | <--- Shifting left...
0 0 1 0 | 0 0 0 0 0 0 0 ? | POSITIVE. ? = 1
0 0 1 0 | 0 0 0 0 0 0 0 1
--------|-------------------------------------------
0 0 1 0 | 0 0 0 0 0 0 1 ? | <--- Shifting left...
0 0 1 0 | 1 1 1 0 0 0 1 ? | NEGATIVE. ? = 0
0 0 1 0 | 0 0 0 0 0 0 1 0
--------|-------------------------------------------
0 0 1 0 | 0 0 0 0 0 1 0 ? | <--- Shifting left...
0 0 1 0 | 1 1 1 0 0 1 0 ? | NEGATIVE. ? = 0
0 0 1 0 | 0 0 0 0 0 1 0 0
--------|-------------------------------------------
Press any key to continue













3) 9 / 2 = 4 (Remainder = 1)

DIVISOR | REMAINDER DIVIDEND/QUOTIENT
--------|-------------------------------------------
0 0 1 0 | 0 0 0 0 1 0 0 1
--------|-------------------------------------------
0 0 1 0 | 0 0 0 1 0 0 1 ? | <--- Shifting left...
0 0 1 0 | 1 1 1 1 0 0 1 ? | NEGATIVE. ? = 0
0 0 1 0 | 0 0 0 1 0 0 1 0
--------|-------------------------------------------
0 0 1 0 | 0 0 1 0 0 1 0 ? | <--- Shifting left...
0 0 1 0 | 0 0 0 0 0 1 0 ? | POSITIVE. ? = 1
0 0 1 0 | 0 0 0 0 0 1 0 1
--------|-------------------------------------------
0 0 1 0 | 0 0 0 0 1 0 1 ? | <--- Shifting left...
0 0 1 0 | 1 1 1 0 1 0 1 ? | NEGATIVE. ? = 0
0 0 1 0 | 0 0 0 0 1 0 1 0
--------|-------------------------------------------
0 0 1 0 | 0 0 0 1 0 1 0 ? | <--- Shifting left...
0 0 1 0 | 1 1 1 1 0 1 0 ? | NEGATIVE. ? = 0
0 0 1 0 | 0 0 0 1 0 1 0 0
--------|-------------------------------------------
Press any key to continue



4) 8 / 3 = 2 (Remainder = 2)

DIVISOR | REMAINDER DIVIDEND/QUOTIENT
--------|-------------------------------------------
0 0 1 1 | 0 0 0 0 1 0 0 0
--------|-------------------------------------------
0 0 1 1 | 0 0 0 1 0 0 0 ? | <--- Shifting left...
0 0 1 1 | 1 1 1 0 0 0 0 ? | NEGATIVE. ? = 0
0 0 1 1 | 0 0 0 1 0 0 0 0
--------|-------------------------------------------
0 0 1 1 | 0 0 1 0 0 0 0 ? | <--- Shifting left...
0 0 1 1 | 1 1 1 1 0 0 0 ? | NEGATIVE. ? = 0
0 0 1 1 | 0 0 1 0 0 0 0 0
--------|-------------------------------------------
0 0 1 1 | 0 1 0 0 0 0 0 ? | <--- Shifting left...
0 0 1 1 | 0 0 0 1 0 0 0 ? | POSITIVE. ? = 1
0 0 1 1 | 0 0 0 1 0 0 0 1
--------|-------------------------------------------
0 0 1 1 | 0 0 1 0 0 0 1 ? | <--- Shifting left...
0 0 1 1 | 1 1 1 1 0 0 1 ? | NEGATIVE. ? = 0
0 0 1 1 | 0 0 1 0 0 0 1 0
--------|-------------------------------------------
Press any key to continue
greka
Dec 10, 2003, 07:55
mojno neskromnyj vopros ?
Ty xot' odin sovet ispol'zoval, ktorye tebe v tvoix topiikax davali ?
DaNYer
Dec 10, 2003, 14:01
Originally posted by Greco El
mojno neskromnyj vopros ?
mojno


Ty xot' odin sovet ispol'zoval, ktorye tebe v tvoix topiikax davali ?

da
greka
Dec 10, 2003, 15:16
Originally posted by DaNYer
mojno



da

a mojno posmotret', gde imenno v privedennom kode ?
DaNYer
Dec 10, 2003, 15:39
void load(int*, int*, int*);


adder ya ispol'zoval svoi :) sorry.

shiftat' na moi vzglyad dlya takoi malen'koi cifri effektivnee ne v cikle a topornim metodom...

ostal'noe kajis' ne srabotalo.
DaNYer
Dec 10, 2003, 15:42
no ved' rabotaet je! i neploxo rabotaet skaju ya vam...

kstati Garik, ya podumivaiu web site sdelat' posvyashennii iskluchitel'no algoritmam... tam mojno budet naiti algoritmi, skachat' rabotayushie progi i t.p. takaya naivnaya zateya, ya uveren chto takie web sites uge est' i ix daje bol'she chem u menya volos na golove.. no zato svoi budet :) rodnoi tak skazat'. kak posmotrish na etu zateyu? podderjish?