Archived

This topic is now archived and is closed to further replies.

Frankie68

Dividing really HUGE numbers, what to do?

Recommended Posts

Hello everyone, how was your weekend? I have a small question and I guess that it has been asked a lot more times, but (as you may know) the search-option is down, so please be gentle. I am working on some sort of QBasic Compiler (interpreterer in fact) and I don''t want to restrict the size of integers. Therefor I made a class called HugeNumber and I use it to store integers when the user wants this. See this example:
  

struct PartofNumber
{
	int value;
	PartOfNumber *prev, *next;
	PartOfNumber( ) { prev = next = NULL; value = NULL; }
	~PartOfNumber( ) { }
} // PartOfNumber


///////////////////////////////////////////////////////////////


HugeNumber &HugeNumber::operator+=(const HugeNumber &rhs)
{
	int carry;
	PartOfNumber *left = this->value,	// value points to first PartOfNumber-struct.

		*right = rhs.value;
	if(rhs.numberofparts > this->numberofparts)
	{
		this->ExtentTo(rhs.numberofparts);		// Make sure number fits

	} // if

	while(right != NULL)
	{
		left->value += right->value + carry;
		carry = left->value / 1000;				// one part contains max 1000

		left = left->next;
		right = right->next;
	} // while

	if(carry)
	{
		this->ExtentOne();
		this->last->value = carry;				// last is the last part

	} // if

	return *this
} // operator+=


  
But now I want to divide the HugeNumbers. I implemented the multiply-operation the same way as I learned way back at school (I don''t how it is called in English, but I think that you have learned it the same way ). But the way for dividing numbers at school was not really "aritmatic", it was more something I did out of knowledge. Just find the largest number that you could multiply the rhs with as it would just fit. Then substract the value and do it again. But this will take a lot of time when I use it wth my numbers. I think that there is a different way and I think that that one is used in FPU''s. I cannot find anything on google that really helps me. So... Maybe you can help? Thank you...

Share this post


Link to post
Share on other sites
This code only works when a and b are both positive and a is larger than b.


  
int Divide(int a, int b)
{
int d = 0;
int StartB = b;
int Factor = 1;

while (StartB < a)
{
StartB *= 10;
Factor *= 10;
}

while (a >= b)
{
while (StartB > a)
{
StartB /= 10;
Factor /= 10;
}

a -= StartB;
d += Factor;
}

return d;
}


I would suggest you look into using one of the many large number libraries available on the net, I use gmp (http://www.swox.com/gmp/) and find it to be fast and easy to use.

Alan

Share this post


Link to post
Share on other sites
Hello... this has nothing to do with the maths question... but if you are wiritng a new QBasic interpreter, do you not think it would be a good idea for it to be identical to the original? Supporting bigger integers and other new features is nice, but it would mean programs written for the old QB would not take advantage of it, and programs written for you''re new interpreter would not work on the old QB.

- Ashley Oliver
Lead Programmer, Interplanitary Productions

Share this post


Link to post
Share on other sites