Skip to main content
gamedev.net
🔒 Locked

Division Algorithm (BIGINT)

Started by lukar May 16, 2004 at 3:23 PM 0 replies 2.8k views
Original Post
lukar
lukar
Hi there, i''ve been working in my bigint and i''ve ran into a weird thing in my division operator I post the whole code so you guys have a better understanding of it. The problem is that the while that is pointed out in the code below in the operator/ section should not exit so soon and it does. I am very confused because my logic operators are working correctly. And i displayed the number in bits and the << and >> are correct(bit shifting). this class has an array of 4 ints where each one is in base 0x80000000. so its A*0x80000000^3 + B*0x80000000^2 + C*0x80000000^1 + D Please help 
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#define LIMIT 0x80000000
//nota no podemos tener numeros mayores al hexadecimal 0x80000000


class BigINT {
	private:
   	int dat[4];
      int carry;
   public:
   	void operator=(BigINT);
      BigINT operator+(BigINT);
      BigINT operator-();
      BigINT operator-(BigINT);
      bool operator==(BigINT);
      bool operator!=(BigINT);
   bool operator>(BigINT);
      bool operator<(BigINT);
      bool operator<=(BigINT);
      bool operator>=(BigINT);
      BigINT operator << (int);
      BigINT operator >> (int);
      BigINT operator*(BigINT);
      BigINT operator/(BigINT);
      BigINT sumaPositivos(BigINT);
      BigINT restaPositivos(BigINT);
      void Desplegar();
   	BigINT(int *);
      BigINT ();
      void displayBits();
};
 ostream& operator << (ostream &os, BigINT &me);
BigINT BigINT:: operator<<(int num)
{
	BigINT *temp = new BigINT();
   *temp = *this;
   int mask = 1 << 31;
   int d[3] = {0,0,0};
   for(int i = 1; i <=num; i++)
   {
		d[0] = (temp->dat[0] & mask) >> 31;
      d[1] = (temp->dat[1] & mask) >> 31;
      d[2] = (temp->dat[2] & mask) >> 31;

      temp->dat[0] = temp->dat[0] << 1;
      temp->dat[1] = (temp->dat[1] << 1) -  d[0];
      temp->dat[2] = (temp->dat[2] << 1) -  d[1];
      temp->dat[3] = (temp->dat[3] << 1) -  d[2];

   }
   return *temp;
}

BigINT BigINT::operator>>(int num)
{
	BigINT *temp = new BigINT();
   *temp = *this;
   int mask = 1;
   int d[4] = {0,0,0,0};
   for(int i = 0; i < num ; i++)
   {
   	d[0] = (temp->dat[1] & mask) << 31;
      d[1] = (temp->dat[2] & mask) << 31;
      d[2] = (temp->dat[3] & mask) << 31;

		temp->dat[0] = (temp->dat[0] >> 1) & 0x7FFFFFFF | d[0];
      temp->dat[1] = (temp->dat[1] >> 1) & 0x7FFFFFFF | d[1];
      temp->dat[2] = (temp->dat[2] >> 1) & 0x7FFFFFFF | d[2];
      temp->dat[3] = (temp->dat[3] >> 1) & 0x7FFFFFFF;
   }
   return *temp;
}

BigINT BigINT::operator*(BigINT op)
{

  	BigINT *temp = new BigINT();
   BigINT primero = *this;
	for(int i = 0; i < 128; i++)
   {
   	if(op.dat[0] & 1)
      {
      	*temp = *temp + primero;
      }
      primero = primero << 1;
      op = op >> 1;
   }
   return *temp;



}
BigINT BigINT::operator/(BigINT divisor)
{
  	// a/b = c  a = dividendo b = divisor  c= cociente

   BigINT *cociente = new BigINT();
   BigINT dividendo = *this;
   BigINT cero;
   int u[] = {1,0,0,0};
   int d[] = {2,0,0,0};
   BigINT uno(u); BigINT dos(d);
////////////////////////////////////////////////////////////


	while(dividendo >= divisor)  ///////THis is the LOOP

   {
		divisor = divisor * dos;
   }
//////////////////////////////////////////////////////////

   divisor = divisor >> 1;
   if(divisor >= dividendo)
   	cout <<  "true" << endl;
   while(dividendo >= cero)
   {
   *cociente = *cociente << 1;
   	if(divisor <= dividendo)
      {
      	dividendo = dividendo - divisor;
         *cociente = *cociente + uno;
      }
      divisor = divisor >> 1;
   }
   return *cociente;

}
bool BigINT::operator==(BigINT op)
{
	for(int i = 0; i < 4; i++)
  {
   	if(dat[i] != op.dat[i]) return false;
   }
    return true;
}
bool BigINT::operator!=(BigINT op)
{
	if(*this == op) return false;
   else return true;
}
bool BigINT::operator>(BigINT op)
{
	if(dat[3] < op.dat[3])
   	return false;
	if(dat[2] < op.dat[2])
   	return false;
	if(dat[1] < op.dat[1])
   	return false;
	if(dat[0] < op.dat[0])
   	return false;
   else return true;
}
bool BigINT::operator<(BigINT op)
{
	if(dat[3] > op.dat[3])
   	return false;
	if(dat[2] > op.dat[2])
   	return false;
	if(dat[1] > op.dat[1])
   	return false;
	if(dat[0] > op.dat[0])
   	return false;
   else return true;
}
bool BigINT::operator<=(BigINT op)
{
	if(*this < op || *this == op) return true;
   else return false;
}
bool BigINT::operator>=(BigINT op)
{
	if(*this > op || *this == op) return true;
   else return false;
}


BigINT::BigINT()
{
	carry = 0;
	for(int i = 0; i < 4; i++)
   	dat[i] = 0;
}

BigINT::BigINT(int arg[])
{
	carry = 0;
	for(int i = 0; i < 4; i++)
   	  dat[i] = arg[i];
}
ostream& operator << (ostream &os, BigINT &me)
{

    me.Desplegar();
   return os;
}
void BigINT::Desplegar(){
	for(int i = 3; i >= 0; i--)
   {
   	cout << hex << " " << dat[i];
   }
}
void BigINT::operator=(BigINT op)
{
	for(int i = 0; i < 4; i++)
   	dat[i] = op.dat[i];
}
BigINT BigINT::sumaPositivos(BigINT op)
{
	BigINT *temp = new BigINT();
   carry = 0;
   for(int i = 0; i < 4; i++)
   {


   	if(dat[i] + op.dat[i] >= LIMIT)
      {
      	temp->dat[i] = dat[i] + op.dat[i]+carry - LIMIT;
      	carry = 1;
      }
      else
      {
      	temp->dat[i] = dat[i] + op.dat[i]+carry;
      	carry = 0;
       }


   }
   return *temp;
}
BigINT BigINT::restaPositivos(BigINT op)
{
	BigINT *temp = new BigINT();
   *temp = *this;
   for(int i = 0; i < 4; i++)
   {
   	if(dat[i]<op.dat[i])
      {
         temp->dat[i+1]-=1;
         temp->dat[i] += LIMIT - op.dat[i];
      }
      else
      {
      	temp->dat[i]-= op.dat[i];
      }
   }
	return *temp;
}
BigINT BigINT::operator-(BigINT op)
{
	if(dat[3] < LIMIT && op.dat[3] < LIMIT)
   {
   	return restaPositivos(op);
   }
   if(dat[3] > LIMIT && op.dat[3] > LIMIT)
   {
      return *this + (-op);
   }
   if(dat[3] < LIMIT && op.dat[3] > LIMIT)
   {
   	return *this + (-op);
   }
   if(dat[3] > LIMIT && op.dat[3] < LIMIT)
   {
   	return *this + (-op);
   }
}
BigINT BigINT::operator+(BigINT op)
{
	if(dat[3] < LIMIT && op.dat[3] < LIMIT)
   {
   	return sumaPositivos(op);
   }
   if(dat[3] > LIMIT && op.dat[3] > LIMIT)
   {
   	return  -(*this + (op));
   }
   if(dat[3] < LIMIT && op.dat[3] > LIMIT)
   {
   	return *this - op;
   }
   if(dat[3] > LIMIT && op.dat[3] < LIMIT)
   {
      return op - *this;
   }
}
BigINT BigINT::operator-()
{
	BigINT *temp = new BigINT();
   carry=1;
	for (int i = 0; i < 4; i++) {
		temp->dat[i]=~dat[i]+carry;
		if (~dat[i]==0xFFFFFFFF && carry==1){
			carry=1;
		}
      else {
			carry=0;
		}
	}
	return *temp;
}
void BigINT::displayBits()
{
   int c, displayMask = 1 << 31;
   int value[4];
   value[0] = dat[0];
   value[1] = dat[1] ;
   value[2] = dat[2]  ;
   value[3] = dat[3]   ;
   for(int i = 3; i >= 0; i--)
   {
  	 	for (c = 0; c < 32; c++) {
      	putchar(value[i] & displayMask ? ''1'' : ''0'');
     	 	value[i] <<= 1;
   	}
      putchar('' '');
   }
   putchar(''\n'');
}

void main()
{
	int r[] = {0x4,0x2,0x0,0x0};
   int s[] = {0x3,0x1,0x0,0x0};
   BigINT d( r );
   BigINT b(s);
   BigINT a;
   BigINT cero;
	a = b*d;
   a = a / d;
   getch();
}
I have neurons in my butt!!!
Skizz
Skizz
Your division algorithm is flawed in that the value of the divisor is lost in the while loop - you don''t record how many times the loop is executed.

I''d change the system to use base 2 and store the numbers in byte arrays. Division then becomes a simple process of comparing and shifting binary numbers. You can also make the system handle numbers of any size by making the storage dynamic.

Skizz

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.