Then good luck!!Originally Posted by LuckY
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
This is a discussion on Division Algorithm within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by LuckY All I need to define is HugeFloat/HugeFloat. Then good luck!! But, does your HugeFloat class preserves ...
Then good luck!!Originally Posted by LuckY
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
Last edited by xErath; 11-13-2004 at 11:17 PM.
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.
Last edited by LuckY; 11-14-2004 at 12:01 AM.
Just visiting from:
Big Numbers (Base 256)
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]
Last edited by Epo; 11-14-2004 at 11:55 AM.
Hahaha. That's a good one... You're on.
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.
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; }
Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling
You placed two points in the 1st number!! bah So with the point in the other place:Code:1354879979882938794537374983792137123384983795173 98448357497343.23512626549871545564165544165544465 475263446544562345646 /9879879734452452435132465526759867232165839586598 7123411644545246241423465234152323315221332452364 5545324579823475829785293452.130165409874 = 1.371352704991228E-64
Me wins!Code:1354879979882938794537374983792137123384983795173 984835749734323512626549871545564165544165544.4654 75263446544562345646 /9879879734452452435132465526759867232165839586598 71234116445452462414234652341523233152213324523645 545324579823475829785293452.130165409874 = 1.371352704991228E-32
Wow, you didn't even give me time to wake up! Hehe
Alright....so....that contest's over rather quickly.
Good job though!
It cant provide infinite precision, since no computer has enough memory to store the floating point result of 1/3 to an infinite precision.does your HugeFloat class preserves infinite or even extreme precision??
You'll only need may be two decimal places more than the given precision, I think.But for the 1/denom division (before the *numerator) I will extend it out very far.
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.
C + C++ Compiler: MinGW port of GCC
Version Control System: Bazaar
Look up a C++ Reference and learn How To Ask Questions The Smart Way
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...Originally Posted by laserlight
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.
Surprisingly easy (at least without much optimisation), actually.It's amazing how hard it can be to take a simple operation like long division and put it into code.
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 ...It does depend on divRS(), which in turn depends on cmp(), sub() and increment() (which depends in part on add() ), so yeah.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; }
The good part is that once I had div() done, getting mod() done for modulo was easy.
C + C++ Compiler: MinGW port of GCC
Version Control System: Bazaar
Look up a C++ Reference and learn How To Ask Questions The Smart Way
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...