Re: Really big math problem
- From: Jerry Coffin <jcoffin@xxxxxxxxx>
- Date: Sat, 14 May 2005 09:52:16 -0600
In article <OdWevJIWFHA.2472@xxxxxxxxxxxxxxxxxxxx>, "mike"
<nospamplease> says...
> Sorry for the post here. If someone can suggest another site or help, I
> would appreciate it. I need to perform modulo math on a number as large as
> 20 trillion; thats
> 20,000,000,000,000 on a 32 bit processor. I've found some articles that
> describe binary division but haven't quite grasped the process on such a
> large number.
If you're interested in getting the job done rather than learning
about the process, you might want to look up __int64.
If you want to know what's going on: the simplest form of binary
integer division is quite similar to doing long division the way they
(used to?) teach it in school. The big difference is that in school
we worked in decimal, which turns out to make life considerably more
difficult.
To do long division, we mentally shifted the divisor (the number we
were dividing BY) left as many digits as necessary to get its most
significant digit into the same position as the most significant
digit of the dividend (the number we were dividing it into). We'd
then guess/estimate/figure how many times the shifted divisor went
into the dividend. We'd multiply the shifted divisor by that number,
subtract that value from the dividend, and write down what we'd
multiplied by as a digit of the answer. We'd then do the same thing
with the divisor shifted one digit to the right, repeating until we'd
shifted it all the way back to where it started.
In binary, we can do the same thing, but it's somewhat simpler: in
decimal we had to figure out how many times (between 0 and 9) the
shifted divisor went into the (current) dividend for each digit. In
binary we don't have to do that -- as long as the other parts are
working right, there are only two choices at any given digit
position: either the shifted divisor is less than or equal to the
current dividend, in which case it goes in once (this digit of the
answer is a one) or else it's larger than the current dividend, in
which case it doesn't go into it at all (the current digit of the
answer is a zero).
Code for that algorithm can be written something like this:
struct result {
unsigned answer;
unsigned remainder;
result(unsigned a, unsigned r) : answer(a), remainder(r) {}
};
result divide(unsigned dividend, unsigned divisor) {
// Res is used to hold the answer as we build it up.
int res = 0;
// Current keeps track of what we have the divisor multiplied by
// at any given moment.
int current = 1;
// division by zero -- signal an error.
if ( dividend == 0)
return result(0, 0);
// Shift divisor left so its MSB will match up with the MSB of the
// dividend.
while (divisor < dividend) {
divisor <<= 1;
current <<= 1;
}
// The real heart of the division: subtracting the multiples of the
// divisor from the dividend, adding one bit to the answer at each
// iteration.
while (current >>= 1) {
divisor >>= 1;
if (divisor <= dividend) {
res |= current;
dividend -= divisor;
}
}
return result(res, dividend);
}
To make this work for a larger type, you need to implement left and
right shift, bitwise or, and subtraction for that type, then apply
the same algorithm as above.
There are quite a few other division algorithms around, and many (if
not most) have at least some advantages over this one. This requires
roughly 2N iterations to give its answer, where N is the difference
in magnitude between the dividend and the divisor. Less obvious
methods use N iterations, where N is the bit size of the type
involved. Still others use N/2, N/4, etc. -- though these are
substantially more difficult to implement or understand.
--
Later,
Jerry.
The universe is a figment of its own imagination.
.
- References:
- Really big math problem
- From: mike
- Really big math problem
- Prev by Date: Re: Initialize CDlg's position
- Next by Date: Problems saving HKLM
- Previous by thread: Really big math problem
- Next by thread: Problems saving HKLM
- Index(es):
Relevant Pages
|
