Then good luck!!Quote:

Originally Posted byLuckY

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

Printable View

- 11-13-2004xErathQuote:

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 - 11-13-2004LuckY
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-2004Epo
Just visiting from:

http://cboard.cprogramming.com/cplusplus-programming/58598-big-numbers-base-256-a.html

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-2004LuckY
Hahaha. That's a good one... You're on.

- 11-14-2004Epo
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-2004Sang-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-2004xErathCode:
`1354879979882938794537374983792137123384983795173`

98448357497343.23512626549871545564165544165544465

475263446544562345646

/9879879734452452435132465526759867232165839586598

7123411644545246241423465234152323315221332452364

5545324579823475829785293452.130165409874 =

1.371352704991228E-64

Code:`1354879979882938794537374983792137123384983795173`

984835749734323512626549871545564165544165544.4654

75263446544562345646

/9879879734452452435132465526759867232165839586598

71234116445452462414234652341523233152213324523645

545324579823475829785293452.130165409874 =

1.371352704991228E-32

- 11-14-2004Epo
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-2004laserlightQuote:

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

Quote:

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. - 11-14-2004xErathQuote:

Originally Posted by**laserlight**

- 11-15-2004Kybo_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-2004laserlightQuote:

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

...

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. - 11-15-2004LuckY
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...