Archived

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

Ajsoftware

Long division with infinitely large numbers

Recommended Posts

Is it possible to do long division with infinitely large numbers? Right now I pass the function two foats a and b and it run a simple long division algorithm and put the answer into an array (one digit in each elemt of the array). Now instead of using floats I want to be able to divide 2 different arrays of any size any pointer''s about how I sould go about doing this? Is it even possible?
void Long_Divide ( float a, float b )
{
	int counter = 0;
	int z = 0;
	int dec = 0; //decimal position
	
	if (a < 0 && b > 0) 
	{
		Super_Quotient[1] = 11; // 11 is the flag for a
		a = a * -1;             // negative sign 10 is
		counter++;              // for a decimal point
	}
	
	if (a > 0 && b < 0) 
	{
		Super_Quotient[1] = 11;
		b = b * - 1;
		counter++;
	}

	while(counter < accuracy) // This is how far out you want
	{                         // the long division to go
		z = a / b;
		if (z < 10)
		{										
			counter++;
			if (counter == dec + 2)
			{
				Super_Quotient[counter] = 10;
				counter++;
			}
			Super_Quotient[counter] = z ;
			a = (a - (b * z)) * 10;		
		}
		if (z >= 10) 
		{
			a = a / 10;
			dec = dec + 1;
		}
		
	}
}
sorry for the AI post

Share this post


Link to post
Share on other sites
I want to do it too. I thought about it, and I found some solutions:

If you want a number of 1024 bits (example), take a pointer of 128 bytes (128 * 8 = 1024), Then make your operators funtions(+,-,*,/) with some logical operators (and,or,xor,not,xnor).

Sorry, I dont have all the source code, or the algorithm for operators.

Fantasio


Share this post


Link to post
Share on other sites
Just a comment, you know arrays start at index 0 right?
>>Super_Quotient[1] = 11;

don''t u want that to be:
Super_Quotient[0] = 11;
?

But back to the original problem, what exactly is that you are having a problem with? i don''t understand?

If the problem is that you don''t know what the array size will be before you declare it, then you can use linked lists! It is pretty much the same as an array except that you create a new space in memory only when u want to add something new to the list.

Share this post


Link to post
Share on other sites
You see, the whole program I''m trying to accomplish will take a decimal number such as PI you place the digits into an array:

decimal[1] = 3;
decimal[2] = 10;
decimal[3] = 1;
decimal[4] = 4;
decimal[5] = 1;

Then my long divide will will divide the numerator and denominator divide them. I then have another routine to evaluate which array is bigger decimal or Super_Quotient. Then according to which one is bigger incriment the numerator or denominator accrodingly. So far this program works great except as the fraction gets more and more accurate then numerator and denominator numbers get bigger then the float is accurate to. So I''m going instead of dividing floats i''m going to have to divide array''s with the digits in side them. Here is my output for calculating a fraction for PI.
1/1 , 2/1 , 3/1 , 13/4 , 16/5 , 19/6 , 22/7 , 355/113
Then finally,
104348/33215
That''s all until the floats are too large.

Share this post


Link to post
Share on other sites
If you want to work with arbitrarily large numbers, you could use the BCD (Binary coded decimal) format for storing them. You should be able to find source or at least algorithms for manipulating such numbers with google.com.

Share this post


Link to post
Share on other sites
You will find it easier if you store a bytes worth of data in each array cell, it makes it easier for conversion from floats. Also do not use this "special flag" method. You should store the exponent (look up how floats work to undstand this) and the sign in a seperate struct.
I don''t know the clever, efficient way, if there is one, but the method for actually doing it I would suggest be the same as normal long division:
For A/B
Start with the highest value of 256^n which B*256^nFind out how many multiples of that can still fit under A (you could do this by repeated subtraction but there are quicker ways involving trying 128 then 64 then 32 ...). Once you have the largest number B*m*256^n where m<256 subtract it from A and start again with n one lower, storing the m as the first digit in your answer.

NB: On hind site it may be easier to split numbers up into bits of data.

Reading your post, if this is meant to use only naturaly numbers, it makes it slightly easier, as there is no need to store an exponent, and the starting n can be calculated even easier.

Share this post


Link to post
Share on other sites
Division is pretty simple if you just do it as binary. Each digit is either zero or one. A simple compare will tell you if a given digit is zero or one. The only multiplication is by zero or one. There are a lot of short cuts you can take, but ignoring those. If you want A/B then shift B to the left until B > A. Keep track of the shifts. Add one when you shift left, subtract one when you shift right. Now shift B to the right once. Add one to your result and subtract B from A. Shift B right and your result left until B < A is true again. Add one to your result and subtract B from A. Keep going until your shift count is back to zero. Your done. That's all there is to it. There are faster ways, but for dinking around it should do fine.

[edited by - LilBudyWizer on November 19, 2003 8:48:13 AM]

Share this post


Link to post
Share on other sites