I've been playing around with
bignums lately, and it seems a couple of other people have too. I thought it would be nice to formulate a programming challenge for some extra fun. :)
────────── Big Integer ──────────
A
bignum or
bigint is a number that exceeds the computers native integer magnitude.
For example, a 32bit integer in two'scomplement representation has the range 2147483647 to 2147483648, or about ±2×10
^{9} (plus or minus two billion in the shortscale, or between 9 and 10 digits).
Likewise, a 64bit integer has the range 9223372036854775807 to 9223372036854775808, or ±9×10
^{18} (plus or minus nine billion billion, or between 17 and 18 digits).
Floatingpoint numbers give you a greater range of values at the cost of a decreased precision (that is, at the cost of exactness  floating point numbers
approximate a value), but ultimately you are still limited to about 18 billion billion distinct values.
While this is pretty impressive, it is sometimes nice to have a greater range of
exact values, say a number containing 100 digits. This is what a
bignum does for us: it allows the user to deal with astronomical values directly.
This comes at a cost though: since the computer can't handle this type of value directly it must be handled in software  making it slower. (Well, there
do exist some computers that can do it in hardware, but they are ancient dinosaurs, alas.)
────────── Math 101 ──────────
The trick, of course, is to remember that every number is a sequence of
digits in a specific
base (or
radix). Humans use base ten, with the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.
Hence, I can represent my age by the combination of
36, which is to say,
3×10
^{1} +
6×10
^{0}. I can store that in memory as an array:
1 2 3

unsigned char base = 10;
unsigned char digits[ 2 ] = { 6, 3 };
// Here the leastsignificant digit comes first.
 
If I use a greater base, I can represent it differently. In base 16, there are 16 digits to choose from, making my age representable as 0x
24, which is
2×16
^{1} +
4×16
^{0}.
1 2

unsigned char base = 16;
unsigned char digits[ 2 ] = { 4, 2 };
 
Once I have chosen a radix and some way to store the list of digits, I can do things like add:
36 + 7
> 3×10^{1} + 6×10^{0} + 7×10^{0} First rewrite our equation
> 3×10^{1} + (6×10^{0} + 7×10^{0}) Sum the
ones (powers of 10
^{0})
> 3×10^{1} + 1×10^{1} + 3×10^{0} ...which produces a
carry
> (3×10^{1} + 1×10^{1}) + 3×10^{0} Now sum the
tens (powers of 10
^{1})
> 4×10^{1} + 3×10^{0} ^{ } We can no longer reduce it, so we're done.
> 43
────────── Representation ──────────
Again, all this can be implemented easily using arrays (or lists) of digits in a base you want to use. The sign of your number is most easily stored as a separte value. (This is called the "signmagnitude" number representation.)
Alternately, you can use a two'scomplement representation, which makes addition and subtraction the same thing, but makes multiplication and division take an extra step to negate numbers of unlike signs.
Some bignum representations have a fixed size, where others have a variablelength. Obviously I prefer a variablelength representation, but fixedlength bignums have some conveniences when dealing with things like multiplication and division.
────────── The Challenge ──────────
Your challenge, should you choose to accept it, is to write a bigint class that implements the following:
1. Positive and negative numbers
2. Copy construction and assignment to/from normal integers and other bignums
3. Conversion to/from textual representation
4. Addition and subtraction
Bonus points for:
5. Multiplication.
There are a number of ways to implement it, but the naïve gradeschool method
suffices. Of course, you can always make a more advanced method...
6. Any other cool thing you can think of, like division.
7. Error handling.
Entries that use assembly or embedded languages or libraries or anything other than pure ISO/IEC standard C++ will be considered invalid. (Use of the STL is fine. Use of
Boost algorithms will be acceptable if they don't relieve you of having done your own work.)
────────── The Proof ──────────
Your test program should be able to properly compute the factorial of 100, which is
100! = 9332621544394415268169923885626670049071596826438162146859296389521759999322991
5608941463976156518286253697920827223758251185210916864000000000000000000000000
While you are at it, you might as well post the factorial of a number of your own choosing (just the factorial, not the argument number) and see if anyone else can use their bignum library to decode your number.
There is plenty of information online to help with. Remember, there's no point if you cheat. Do your own work and have your own fun. I'll recognize obvious cheats so please don't embarrass yourself.
By the second week of December I'll profile the various bignums you guys create and post the results here to see who's algorithms work most quickly.
────────── How To Respond ──────────
If you choose to participate, post back here with any information you like. If your code is small enough to fit in a couple of posts, feel free to do that. Otherwise, please link to something like
pastebin or an online storage service with a
zip or
tar.gz file that people can download and compile.
Oh yeah, I'll be posting my results also. Good luck!