Advertisement

Dividing really HUGE numbers, what to do?

Started by September 30, 2002 07:59 AM
4 comments, last by Frankie68 22 years, 4 months ago
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...
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
"There will come a time when you believe everything is finished. That will be the beginning." -Louis L'Amour
Advertisement
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
"The finger of blame has turned upon itself"
I haven''t thought about htat one, maybe I can use it as something extra that the user can turn on or off, so the choice is to them, but thank you. And of course a lot of thanks to Alan for the help!
http://webster.cs.ucr.edu/Page_asm/ArtofAssembly/ch09/CH09-4.html

(?)
Take a look here:

http://www.swox.com/gmp/

This topic is closed to new replies.

Advertisement