Division Algorithm

Printable View

11-13-2004
LuckY

Division Algorithm

Okay, hopefully some of you can help with some fresh algorithm ideas. I've written (rather, I'm in the process of writing) a class called HugeFloat. It acts very much like a built-in type, but allows you to have floating point numbers of unlimited length and performs mathematic operations very rapidly (factorial 1200 takes under a second).

My problem: the last big operator I need to define is division. With the other three (+ - *) it is much simpler because I can break up the work into smaller pieces, multiplying or adding only small portions at a time. I can't seem to think of an algorithm that would allow me to perform division in a similar way. In case it isn't obvious, I need to do it this way because if, for example, you want to divide 39183791734971398713857183075182394723298739182375 9237829384792347923847.239879574758937845973457 by 98237443591875498179374583457980745089274598274509 8237459827458923745089273459873459.283759283759230 527385728375 it's clearly impossible to do it without somehow breaking up the job into manageable pieces.

Any ideas?
11-13-2004
laserlight

hehe, I'm on this same problem myself, though with integers, which is easier.
Still resisting the urge to look at the source of GMP :)

So far one idea I have (at least one that is applicable to floating point) is to observe that
c = a / b => a = b * c

Then test values of c that make the value of (b * c) approach the value of a, refining the value of c on each iteration, perhaps drawing on the same idea as linear interpolation (sign change on a - (b * c) indicates that we've crossed the actual value).
Unfortunately, multiplication is likely to be slow, so even with a "binary search" type of algorithm to test, you're still going to have a slow division.

The other idea is to observe that as multiplication is repeated addition, division can be seen as repeated subtraction (number of repetitions gives the answer).
I'm not too sure how to implement this for floating point division though.
11-13-2004
Thantos

Just a thought. Could you do division by subtraction for the integer portion and then do a final "normal" division for the non integer portion.

Edit: Actually I thought about it some more and you can do the entire division using the subtraction method. Once you are done with the whole number portion you simply "shift" the decimal and continue on.
11-13-2004
Kybo_Ren

I would do it like....
Keep subtracting the denominator from the numerator until the result is under 0. How many times you did is the first part [not including the time it was under 0]. Now, add the denominator to the result. I'll call this X. Now do the same as above, but now I want you to say the denominator is the numerator, and X is the denominator.

Keep repeating this until the result of the subtraction yields 0.

Here's an example: Let's say we want to calculate 72 / 32.
We will keep a running tally called R (for 'Result').

1. 72 - 32 = 40; R = 1
40 - 32 = 8; R = 2
8 - 32 = -24; No change.
So far, R == 2.

2. 32 - 8 = 24; R1 = 1
24 - 8 = 16; R1 = 2
16 - 8 = 8; R1 = 3
8 - 8 = 0; R1 = 4
So, 8 goes into 32 4 times. This means that we should add 1/4 to R.
R = 2.25
Now let's try 97 / 16.

1. 97 - 16 = 81; R = 1
.
.
.
1 - 16 = -15; R == 6
So far, R == 6.

2. 16 - 1 = 15; R1 = 1
.
.
.
1 - 1 = 0; R1=16
So, R1 is 16. That means we must add 1 / 16 to R. We end up with R = 6.0625

If you want a way to calculate the ending fraction (i.e. 1/16), then keep going.

What we just did in step one was modulus. This essentially simplifies the fraction down for us.

One method of doing this is brute force: start at one, and keep subtracting a set value until we get just past the correct answer when we multiply it with the divisor (in this case, 16). Then, add the step back, divide our step by 10 , and keep going. This would take quite some time, but it would work.

I'd perosnally choose this method. The pro's are that it can calculate infinitely long numbers (albeit slowly), and that you can set a limit to the precision and know how many digits are accurate.

The major con is that it can take quite some time.
I cannot think of another algorithm right now; I'm not in math mode. If anyone has a better algorithm, I would love to hear it.

EDIT: Yes, he could use normal division, but he wanted infinite precision. If you're calculating a division that won't fit into a double, then you're out of luck.
11-13-2004
laserlight

Quote:

Actually I thought about it some more and you can do the entire division using the subtraction method. Once you are done with the whole number portion you simply "shift" the decimal and continue on.

Yeah, I suppose that would be possible.
Should have thought about that, my seniors' 'A' level Computing paper did have a coursework problem involving representation of floating point bignum with the help of 2 integer bignum.
11-13-2004
LuckY

laserlight: thanks for the link. I've actually never heard of GMP. good luck on your project. I actually wrote a huge int class (HINT) a few years ago now (very poorly and slowly but it worked) and it served as a very good basis for what I'm doing now (although now I'm coming up with even better ideas and may have to start over again). With my HINT class the array was stored as an array of chars using one for each digit (very terrible I know but it was just for the learning experience and I wanted extending the base assignment). Now what I'm doing is using an array of unsigned chars but to represent the actual numeric value for up to two digits (and the leading 1 or 2 is used for flags and such). What I'm thinking now is that using base 256 numbers would be much faster and more efficient, but before I go back to the drawing board I want to think out all the details. How are you approaching it?

I have actually given mere moments of serious thought to doing anything but division (subtraction, guessing, etc) but it would be absolutely out of the question. To see what I mean think about a very "simple" worst case scenario of something huge like 13849849709135027935092509273509235297501973059720 5902937509235 divided by 3, for example. Division by subtraction would take a _very_ long time. I tried just decrementing a random ~18 digit number to zero earlier and I had to ctrl-C it because it took too long (it was going on an hour at the very least before I gave up). The same goes for the guessing. I want the division to go as rapidly as I've gotten the multiplication to go.

I appreciate the ideas very much, but unfortunately they won't do... Any other thoughts?
11-13-2004
Kybo_Ren

"To see what I mean think about a very "simple" worst case scenario of something huge like 13849849709135027935092509273509235297501973059720 5902937509235 divided by 3, for example. Division by subtraction would take a _very_ long time."

Well, I'd first check to see if the divisor * 100000 is less than the number being divided. If it is, then I'd multiply what I'm dividing by by 100000 and when I increment the current number of runs where the subtraction is greater than 0, increment it by 100000. Then, once it's below 0, divide by 10, increment by 10000, etc.
11-13-2004
LuckY

Quote:

Once you are done with the whole number portion you simply "shift" the decimal and continue on.

This is actually similar to my multiplication algorithm. I take the entire integer + decimal parts and essentially remove the decimal altogether, noting how many total decimal digits there were. Then I do the multiplication in small pieces and just split the result at the index equal to the total decimal digits value. (the same way one might normally calculate a multiplication of two floating point numbers)
11-13-2004
laserlight

Quote:

Division by subtraction would take a _very_ long time.

It depends on the relative size of the operands.
Dividing a large number by a small number using division by subtraction would take much longer than for large numbers of similiar magnitude.

The method that I am considering now is to check the magnitude.
If they are similiar, I apply division by subtraction.
Otherwise, I the divide and conquer guess and check algorithm, though its use is actually within a method taught to me in primary school.
11-13-2004
LuckY

Quote:

Well, I'd first check to see if the divisor * 100000 is less than the number being divided. If it is, then I'd multiply what I'm dividing by by 100000 and when I increment the current number of runs where the subtraction is greater than 0, increment it by 100000.

It's not that I think the idea is terrible. It's just that it is too unreliable and slow. I am hoping to come up with some solution that has a big-O of n or n*m instead of infinity. Looping possibly endlessly (absolute worst case) to keep multiplying (another big-O of n*m not to mention the resources it consumes) simply to compare is just feels too brute-force.

That said, it is definitely an idea I'll keep in mind. There may just be potential in some aspect of it. Thanks for the contribution.

Quote:

Then, once it's below 0, divide by 10, increment by 10000, etc.

You do see that this would cause my division to be recursive right? If I have a 20 digit denominator and I keep multiplying to get up to the numerator then divide my 20+ digits by 10, the 10 will be multiplied continuously until it reaches that 20+ digits at which point it will be divided by 10.
Just thought that was worth pointing out.
11-13-2004
Kybo_Ren

"If I have a 20 digit denominator and I keep multiplying to get up to the numerator then divide my 20+ digits by 10, the 10 will be multiplied continuously until it reaches that 20+ digits at which point it will be divided by 10."
But you will check to see if that multiplied by whatever is still less than the numerator.

Perhaps I wasn't clear enough or I am not understanding you.
11-13-2004
manofsteel972

I am not sure this will help or not but if you have a 20 digit denomintor divided by 3 couldn't you just move the pointer and add digits to the end of the three keeping track of how many digitis (each one is a power of 10 of course) and then just subtract?

2700000000/3

2700000000-300000000 9 times so the answer is 900000000
ignore the decmal point and just subract then put the answer that many places over?

if it were 2700000000/ .3 then get rid of the decimal by moving it over to the right on both digits.

27000000000/3; now count the places over to match up the 3 with the 27 and then

270000000000-30000000000 do this 9 times then adjust for the decimal point so the
answer woud be 9000000000 .

if you were going the other way say .3/27000000000 then you would just move the decimal for the 3 keeping track of how many you move it over.
30000000000-27000000000it goes 1 time with a remainder of =3000000000 it is repeating if you add a digit and subtract again it goes 1 time so your answer would be .0000000000011111...adjusting for the decimal again.
not sure if that would work in all cases haven't tried it yet.
[edit] never mind guess i should have refreshed the post same as already mentioned i guess.
11-13-2004
LuckY

manofsteel: thanks for the suggestion. This is exactly what I was contemplating originally and what I was going to do, however my problem is not really how to do the division with decimal digits, but how to do the division with numbers that cannot naturally be handled by a computer. Thus, the subtraction solution, which again I will keep in mind. I just wish there was a more direct way.

I actually did implement a huge integer division in my old HINT class and I think I better seriously look into how I did that because I have no idea any more.

One very interesting thing I discovered while experimenting with division that I didn't realize before (but is basic division) is that the sum of the quotient of the integer part and the decimal part over the same denominator yields the same answer. So 123.456/78 is equal to 123/78 + 456/78 (again a very simple, basic math identity). This is how I planned to handle the decimal division. Perhaps breaking up the numerator into even smaller pieces may be part of a good solution.
11-13-2004
xErath

Well, remeber that A/B Is A*(1/B).. So you only need to consider the numerator to be 1, then multiply. That should ease up a bit...
But are you asking for HugeFloat/HugeFloat or HugeFloat/(float,double,long double) algorithm ??
11-13-2004
LuckY

That is really a very a excellent point. Thanks xErath. All I need to define is HugeFloat/HugeFloat. Dividing by any built-in type is a simple task and really the only reason I have a problem is because you can't naturally perform a division for any non-built-in types.
11-13-2004
xErath

Quote:

Originally Posted by LuckY

All I need to define is HugeFloat/HugeFloat.

Then good luck!!
But, does your HugeFloat class preserves infinite or even extreme precision?? If not, mabe 1/B could result in extremely small numbers, that way losing precision
11-13-2004
LuckY

Thanks. I planned on defaulting division to a max of 40-50 decimal digits and providing an accessor for the user to change it if need be. But for the 1/denom division (before the *numerator) I will extend it out very far.

Again, thanks for that extremely obvious, yet severely overlooked point.
11-14-2004
Epo

Just visiting from:
http://cboard.cprogramming.com/showthread.php?t=58598

Thanks for the link Lucky, there're definitely things here that'll come in handy for me too.

Though, you DO have a slight edge on me, seeing as you've already done all the other algorithms, how about the first one to divide:
13548799798829387945373749837921371233849837951739 844835749734323512626549871545564165544165544.4654 75263446544562345646
by
98798797344524524351324655267598672321658395865987 12341164454524624142346523415232331522133245236455 45324579823475829785293452.130165409874

wins? ;)

(And if anybody wants to do it on paper, that's fair game too) :)

[EDIT]
I sure did place two points, my bad
[/EDIT]
11-14-2004
LuckY

Hahaha. That's a good one... You're on.
11-14-2004
Epo

I think it's Pi.... :)

Well then I best get cracking! Well...it's 3:00 in the morning, but when I wake up! Oh, you best watch out.

*Tips his hat* Until next time folks.
11-14-2004
Sang-drax

Here's what I use in my BigInt class. digits is a std::vector with digits 0-9.
I use base 10 for easy output.

Code:

BigInt& BigInt::operator/=(const BigInt& denominator) { using namespace std; //Single digit optimization if (denominator.digits.size() == 1) { int remainder; singleDivision( denominator.digits[0], remainder); return *this; } if (denominator.isZero()) { //Not correct, but we don't use exceptions here *this = 0; return *this; } //Is denominator larger? if (denominator > *this) { *this = 0; return *this; } //The result BigInt result; int rsize = digits.size()-denominator.digits.size()+1; result.digits.resize(rsize,0); for (int i=rsize-1;i>=0;--i) { //Guess the value for result[i] result[i] = 5; while (*this - result*denominator < 0) result[i]--; while (*this - result*denominator >= 0) result[i]++; result[i]--; } result.trim(); if (denominator.negative) result.negative = !result.negative; if (negative) result.negative = !result.negative; *this = result; return *this; }
11-14-2004
xErath

Code:

1354879979882938794537374983792137123384983795173 98448357497343.23512626549871545564165544165544465 475263446544562345646 /9879879734452452435132465526759867232165839586598 7123411644545246241423465234152323315221332452364 5545324579823475829785293452.130165409874 = 1.371352704991228E-64

You placed two points in the 1st number!! bah So with the point in the other place:

Code:

1354879979882938794537374983792137123384983795173 984835749734323512626549871545564165544165544.4654 75263446544562345646 /9879879734452452435132465526759867232165839586598 71234116445452462414234652341523233152213324523645 545324579823475829785293452.130165409874 = 1.371352704991228E-32

Me wins! :D :D
11-14-2004
Epo

Wow, you didn't even give me time to wake up! :) Hehe

Alright....so....that contest's over rather quickly.

Good job though! :)
11-14-2004
laserlight

Quote:

does your HugeFloat class preserves infinite or even extreme precision??

It cant provide infinite precision, since no computer has enough memory to store the floating point result of 1/3 to an infinite precision.

Quote:

But for the 1/denom division (before the *numerator) I will extend it out very far.

You'll only need may be two decimal places more than the given precision, I think.
But I think that you'll have to weight the costs of performing multiplication after division of unity, it may be more than immediately doing the division.

The current method that I'm implementing considers the fact that division by repeated subtraction of numbers which are comparable in size is relatively fast.
So I use long division to break up the numerator into smaller chunks by which division by repeated subtraction is performed.
In addition while using the c=a*b guess and check idea means that I'll have to make an additional subtraction to find the remainder of an intermediate step in the long division, with division by repeated subtraction I get this required remainder as a consequence, and so can use it immediately.
11-14-2004
xErath

Quote:

Originally Posted by laserlight

It cant provide infinite precision, since no computer has enough memory to store the floating point result of 1/3 to an infinite precision.

Of course, i had that memory limitation in mind.. i meant like keeping a max of about 30 or 40 decimal digits, or streching to what ever the number requires, being of course, limited by the available memory...
11-15-2004
Kybo_Ren

I love long division. It's amazing how hard it can be to take a simple operation like long division and put it into code.
11-15-2004
laserlight

Quote:

It's amazing how hard it can be to take a simple operation like long division and put it into code.

Surprisingly easy (at least without much optimisation), actually.
Then again I've already written a number of other functions that simplify the process.
Here's from
std::string BigInt::div(std::string a, std::string b)

Code:

... std::string ret; //return value std::string work_portion; //portion of a currently worked on for (int i = 0; i < a.length(); i++) { //add next digit of a to work portion work_portion.append(1, a[i]); //apply integer division by repeated subtraction ret += divRS(work_portion, b); //work_portion = remainder } return trim(ret); //intermediate quotient = 0 => leading 0s ...

Code:

std::string BigInt::divRS(std::string& a, std::string b) { std::string count("0"); while (cmp(a, b) >= 0) { a = sub(a, b); count = increment(count); } return count; }

It does depend on divRS(), which in turn depends on cmp(), sub() and increment() (which depends in part on add() ), so yeah.
The good part is that once I had div() done, getting mod() done for modulo was easy.
11-15-2004
LuckY

That is a nice, sturdy solution. The only problem (as you eluded to) is that you have to perform the division digit-by-digit and with a several thousand digit division that can be slow. Of course if there is no better a solution that would be a great algorithm to fall back on.

The solution I'm pondering is to multiply 1 by 10 until it is >= denominator then count the subtractions and include it in the quotient until we have achieved several digits (maybe 40) or there is nothing more to divide. Then we multiply that quotient with the true numerator and bam, there's your answer. A real problem that I foresee with doing this with floating point numbers is that it could leave endless trailing 9's instead of rounding up to 1 as it should...