# Division Algorithm

Printable View

Show 80 post(s) from this thread on one page
Page 2 of 2 First 12
• 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...
Show 80 post(s) from this thread on one page
Page 2 of 2 First 12