Re: bigint queston C++ classes
- From: John Slimick <slimick@xxxxxxxxxxxxxxxxxxxx>
- Date: Thu, 25 Oct 2007 00:34:39 +0000 (UTC)
On 2007-10-25, Richard Heathfield <rjh@xxxxxxxxxxxxxxx> wrote:
isaac2004 said:
hello i am posting this in this group because i would like tips on how
to deal with a problem i was given in an OO class that i am in. the
question is to derive a class in C++ to deal with numbers that that
are larger than 2^32. the class needs to have overload operators for
= +, -, * and <<. The whole purpose is to calculate factorials and
powers of large numbers. We cant use STL so all the functions are made
by us. I was just wondering about some pointers to get this started. I
am thinking about putting the numbers into a linked list or some sort
of dynamic array to get around the maximum capacity of int. anyway, i
would really appreciate any insight on this problem. thank you for the
help
Another way would be to have a very long string capability
(with imbedded decimals) and convert all values to
long strings. Of course the arithmetic operations would
be exceptionally poor in performance, but then there's
requirement on efficiency, is there?
(This worked like a very slow charm on the IBM 1401)
john slimick
slimick@xxxxxxxx
.
If you can't use STL, you can't use vectors, so you're stuck with realloc
to grow your arrays.
I suggest an array of unsigned char, or unsigned short, or perhaps unsigned
long. I use unsigned char not because it is the most efficient but because
it is the easiest to keep straight in my head-thing.
Consider a class like this:
{
int sign; /* -1, 0, or 1 */
unsigned char *n; /* or unsigned long or whatever */
size_t magnitude; /* number of n-elements currently storing data */
size_t capacity; /* current size of n-buffer */
/* add other members as you see fit */
};
Give some thought to the number base you plan to use. Base ten makes life
easier in some ways, but base two-five-six has its advantages, as does
base six-five-five-three-six.
Personally, I use base two-five-six, which means I need a conversion
routine for turning the end result into base ten for display, but it makes
the intermediate calculations faster. To keep this article simple to read,
however, I'll stick to base ten.
For bignum algorithms, see Knuth's "The Art of Computer Programming",
Volume 2 ("Seminumerical algorithms").
Remembering that I'm using base ten purely to keep your life simple as I
explain the basic idea, consider the problem of adding the numbers x =
31415926853 and y = 5897932384. (Both these numbers exceed 2 to the 32.)
First, storage. You'll need ceil(log(x)/log(b)) base-b digits to store x,
and ceil(log(y)/log(b)) base-b digits to store y. To store their sum,
you'll need the longer of these two, possibly with one extra digit. (In
this example, that extra digit won't be necessary.)
Since we're using base ten in this example, we need eleven digits to store
x and ten to store y. We don't need a null terminator character because
these are not strings, just a bunch of bytes. We will need to supply a
routine for converting them to displayable strings.
So we'll start off by allocating enough space for the data. I won't show
you how to do this because it isn't part of your question. Suffice to say
that you can get the memory via malloc, but remember to check that malloc
returns a non-NULL pointer before proceeding. And don't forget to pass the
pointer to free when you're done. Set capacity to the amount you allocate,
and magnitude to the number of digits in your integer. If that's the same
as capacity, fine, but be ready to realloc when needed.
Once you have your eleven digits for x, let x->n[0] be the least
significant digit of x. This might seem non-intuitive, but it don't half
make life simpler.
So x's digits are { 3, 5, 8, 6, 2, 9, 5, 1, 4, 1, 3 }
y's digits are { 4, 8, 3, 2, 3, 9, 7, 9, 8, 5 }
You will recognise the original numbers of the problem if you just read
backwards.
Okay, how do we add these?
Let carry = 0.
Start at the left. x->n[0] is 3, and y->n[0] is 4. So z[0] is (x->n[0] +
y->n[0] + carry) % 10 (which comes to 7), and we carry (x->n[0] + y->n[0]
+ carry) / 10 (which comes to 0, so there is no carry).
x->n is { 3, 5, 8, 6, 2, 9, 5, 1, 4, 1, 3 }
y->n is { 4, 8, 3, 2, 3, 9, 7, 9, 8, 5 }
z->n is { 7... }
x->n[1] is 5, and y->n[1] is 8. So z[1] is (x->n[1] + y->n[1] + carry) % 10
(which comes to 3), and we carry (x->n[1] + y->n[1] + carry) / 10 (which
comes to 1, so there is a carry).
x->n is { 3, 5, 8, 6, 2, 9, 5, 1, 4, 1, 3 }
y->n is { 4, 8, 3, 2, 3, 9, 7, 9, 8, 5 }
z->n is { 7, 3... } and we're carrying.
x->n[2] is 8, and y->n[2] is 3. So z[2] is (x->n[2] + y->n[2] + carry) % 10
(which comes to 2), and we carry (x->n[2] + y->n[2] + carry) / 10 (which
comes to 1, so there is a carry).
x->n is { 3, 5, 8, 6, 2, 9, 5, 1, 4, 1, 3 }
y->n is { 4, 8, 3, 2, 3, 9, 7, 9, 8, 5 }
z->n is { 7, 3, 2... } and we're carrying.
Continuing round the loop, we eventually arrive at:
x->n is { 3, 5, 8, 6, 2, 9, 5, 1, 4, 1, 3 }
y->n is { 4, 8, 3, 2, 3, 9, 7, 9, 8, 5 }
z->n is { 7, 3, 2, 9, 5, 8, 3, 1, 3, 7... } and we're not carrying.
We have now exhausted y, so we can just adjust for carry for as long as
necessary (it is not necessary in this case, but if it were, we'd have to
keep carrying for as long as x->n[i] were 9, i.e. the maximum digit value
for the base), as we copy x down into z:
x->n is { 3, 5, 8, 6, 2, 9, 5, 1, 4, 1, 3 }
y->n is { 4, 8, 3, 2, 3, 9, 7, 9, 8, 5 }
z->n is { 7, 3, 2, 9, 5, 8, 3, 1, 3, 7, 3 }
z now contains the result, admittedly the wrong way round. We can display
it as follows:
for(size_t i = z->magnitude; i > 0; i--)
{
putchar('0' + z->n[i - 1]);
}
In other words, we do it just as we would with pencil and paper, albeit
backwards.
Write a function to do this, and call it operator+ :-)
Subtraction is similar.
Think about how best to handle negative numbers. Simplify as much as you
can. For example, remember that -a + b is equal to b - a. So if x is
negative and y is positive, operator+ can simply return y - x, passing the
actual work onto operator-.
Multiplication is done, again, just like you would do it on paper. Multiply
by each digit in turn, keeping a running total and not forgetting to
multiply each result by the appropriate base power (by adding 0s!).
Division is a fair bit trickier. See Knuth for details. Alternatively, look
up this Usenet article by Dann Corbit:
<1191363190.986800.205000@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>
(The nice thing about division is that it gives you the modulo - % - result
as a freebie; it's the remainder at the end of the process.)
Once you have these functions, factorials are easy - multiplication in a
loop.
For powers, the simplest way is divide-and-conquer:
0
x = 1
1
x = x
2k k k
x = x * x
k
so just calculate t = x and then calculate t * t
2k + 1 k k
x = x * x * x
k
so just calculate t = x and then calculate t * t * x
This lends itself to a simple recursive approach, with 0 and 1 as base
conditions.
k
Powmod (x mod m) is similar, except that you use % m at every conceivable
opportunity, to keep the numbers manageable, and don't forget to % m at
the end.
Just to demonstrate that this is in fact possible(!), here is 99!,
calculated using my own routines, written in C:
933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000
And here is 475472895345 ^ 234101934858 (mod 123456654321):
66805749906
You can check these in whatever way seems fit to you. I just tried to check
the result myself using bc, which reported: "Runtime error (func=(main),
adr=29): exponent too large in raise" so I'm feeling moderately smug, as
it appears that I can out-bc bc. :-)
- References:
- bigint queston C++ classes
- From: isaac2004
- bigint queston C++ classes
- Prev by Date: Re: bigint queston C++ classes
- Next by Date: Re: bigint queston C++ classes
- Previous by thread: Re: bigint queston C++ classes
- Next by thread: Re: bigint queston C++ classes
- Index(es):
Relevant Pages
|
