C++

Forum

 
Bignum Challange

Pages: 1234
Duthomhas (13206)
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 32-bit integer in two's-complement representation has the range 2147483647 to -2147483648, or about ±2×109 (plus or minus two billion in the short-scale, or between 9 and 10 digits).

Likewise, a 64-bit integer has the range 9223372036854775807 to -9223372036854775808, or ±9×1018 (plus or minus nine billion billion, or between 17 and 18 digits).

Floating-point 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×101 + 6×100. I can store that in memory as an array:

1
2
3
 
unsigned char base = 10;
unsigned char digits[ 2 ] = { 6, 3 };
// Here the least-significant 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 0x24, which is 2×161 + 4×160.

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×101  +  6×100  +  7×100   First rewrite our equation
    -->  3×101  + (6×100  +  7×100)  Sum the ones (powers of 100)
    -->  3×101  +  1×101  +  3×100   ...which produces a carry
    --> (3×101  +  1×101) +  3×100   Now sum the tens (powers of 101)
    -->  4×101  +  3×100             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 "sign-magnitude" number representation.)

Alternately, you can use a two's-complement 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 variable-length. Obviously I prefer a variable-length representation, but fixed-length 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 grade-school 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!
Last edited on
Browni3141 (578)
Can we use any base, or only base ten? Maybe base conversion can also be bonus points.
Duthomhas (13206)
Use whatever radix you desire - the choice is yours. :-)

The to/from string counts towards base conversion. (Unless you use base ten, where to/from string is a simple addition transform.)
closed account (z05DSL3A)
That sounds like a good excuse to hit the books...now where is my copy of Art of Computer Programming: Volume two.

Edit:
...anything other than pure ISO/IEC standard C++ will be considered invalid.

hmm...So no C with a C++ wrapper?
Last edited on
chrisname (7395)
Isn't all C valid C++ except where you use C++ keywords for e.g. variable names?
filipe (1165)
Well, mostly. f() has a quite different meaning, for instance.
hamsterman (4538)
well. this is something.. http://pastebin.com/MgUrZEmu
didn't do division. (I should probably read up on that..)
input / output is only in hex (which makes sense if there's no division, I guess)
chrisname (7395)
I tried writing an ArbitraryPrecisionInteger class, but I got bored about halfway through.
hamsterman (4538)
bigfloat? if you have unlimited resources, why would you make it arbitrary precision? for irrational numbers?
Bazzy (6281)
I've written my Bignum.
It's a very simple sign-magnitude stored as decimal digits ( digits are reversed than usual notation )
All the operations are mostly implemented like I'd do on paper.
Division is implemented by a series of subtractions.
Quite simple ( and likely very buggy ) but it did evaluate 100! correctly

Maybe I'll write a binary one as well

Header:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
 
#ifndef SIMPLE_DECIMAL_BIGNUM_H
#define SIMPLE_DECIMAL_BIGNUM_H
#include <string>
#include <iosfwd>

class simple_decimal_bignum
{
    private:

        typedef signed char                     digit_type;
        typedef std::basic_string<digit_type>   buffer_type;
        typedef simple_decimal_bignum           value;
        typedef simple_decimal_bignum&          reference;
        typedef const simple_decimal_bignum&    const_reference;
        typedef std::string                     string;

        static simple_decimal_bignum zero;

        static buffer_type& remove_zero ( buffer_type& );

        bool sign_;
        buffer_type buffer;

        static buffer_type conv_ulong ( unsigned long );
        static buffer_type conv_float ( double );
        static buffer_type conv_string ( const string& );

        void overflow ( unsigned begin = 0 );
        void underflow ( unsigned begin = 0 );
        reference normalize();
        reference multiply_by_digit ( digit_type );


    public:

        // constructors
        simple_decimal_bignum ( unsigned long = 0ul );
        simple_decimal_bignum ( signed long );
        simple_decimal_bignum ( int );
        simple_decimal_bignum ( double );
        simple_decimal_bignum ( const string& );
        simple_decimal_bignum ( const char* );

        // assignment
        reference   operator= ( unsigned long );
        reference   operator= ( signed long );
        reference   operator= ( int );
        reference   operator= ( string );
        reference   operator= ( const char* );
        reference   operator= ( double );

        // conversion
        signed long slong() const;
        unsigned long ulong() const;
        string      str() const;

        // sign
        signed      sign() const;
        reference   abs()           { return sign_ = false, *this; }
        friend value abs( value n ) { return n.abs(); }
        reference   neg();
        value       operator-() const;

        // arithmetic
        reference   operator+= ( const_reference );
        reference   operator-= ( const_reference );
        reference   operator*= ( const_reference );
        reference   operator/= ( value );

        reference operator++ ();
        reference operator-- ();

        value       operator+ ( const_reference );
        value       operator- ( const_reference );
        value       operator* ( const_reference );
        value       operator/ ( const_reference );

        // comparison
        bool        operator<  ( const_reference ) const;
        bool        operator<= ( const_reference ) const;
        bool        operator== ( const_reference ) const;
        bool        operator!= ( const_reference ) const;
        bool        operator>= ( const_reference ) const;
        bool        operator>  ( const_reference ) const;

};

// stream
std::ostream& operator<< ( std::ostream& os, const simple_decimal_bignum& sdbn );
std::istream& operator>> ( std::istream& is, const simple_decimal_bignum& sdbn );

#endif // SIMPLE_DECIMAL_BIGNUM_H


Source:
http://codepad.org/eYmEppxF
blackcoder41 (1426)
Wow this seems really challenging. Never did something like this before so I'll try if I can make it on December considering my busy schedule. Btw what do you recommend on reading? or am I allowed to read books?
Duthomhas (13206)
Remember, the goal is not perfection, but just some fun playing around with it. The thing I'm going to post works much like Bazzy's -- just a string of values in 0..9 (base 10) and a separate sign bit.

The more experienced coders will of course be able to churn this stuff out quite rapidly, but I want the challenge to be accessible to those who are relatively new to C++ as well.

The hardest part of the challenge is actually converting to/from string, since that would normally require multiplications and divisions. Both Bazzy and I chose to simply use a radix of 10 and just convert '0'..'9' to 0..9. hamsterman went with base 16, which means you can store your numbers in any binary base you want, since conversion becomes a trivial play with the CPU integer types.

You can read anything you like. Googling around "bignum" is a good start.
Disch (13742)
I never actually looked into it, but how handle division that produces an irrational number?

Like the simplest case of 1/3. How many '3's do you make before you call it quits?
m4ster r0shi (2201)
I had to implement a fast multiplication algorithm of my choice
(I chose this -> http://en.wikipedia.org/wiki/Karatsuba_algorithm )
as a homework assignment a while ago. The keen eye will notice that it's quite slow.
I'm making many unnecessary copies that could be avoided if I implemented operators +=, *= etc
and then had operators +, * etc implemented in terms of the first ones. But all I wanted was just to get the job done, so I didn't bother...

Here's what I did:

http://codepad.org/FiO3pWqK (original version)
http://codepad.org/cIqbzvRl (improved version)

Note that I do not wish to enter the competition (after all, I don't fulfill the requirements).
I just thought I should post this so that other people can modify/expand it to build their own classes.

EDIT: Don't mind me fixing this every once in a while...
Last edited on
Bazzy (6281)
I've just noticed that my code is missing const for some operators
( I'm not going to fix that )
hamsterman (4538)
http://pastebin.com/k6sWj4jd
Changed it to work with decimal digits. When I wrote the original version, I thought base 232 would be much faster and I wouldn't have to deal with 9+2=1 (0xfa+0x07 = 0x01 happens automatically). But apparently using base 10 saved me a lot of code (mostly with input/output). I wonder if I could combine the two advantages and use base 104 or something..
If I'm bored enough, I may do division tomorrow, though I'd like to do something smarter than "while a > b do a -= b".
afdave14 (14)
Wow, it looks like we have some pretty experienced programmers here ;) Hopefully I can actually get mine done :) Good luck everybody!
closed account (D80DSL3A)
@Disch. re: division. I wondered about this too. I'm going to try making it like regular integer division with / and % operators returning the quotient and the remainder separately. I can't think of any other sensible way to return the result of int/int with complete precision.
PiMaster (359)
Gosh, I wish I could do this, but I've been getting a little, erm... obsessive about programming, to the point where it's started to affect my grades. Because of this, I'm not touching a compiler, doodle paper (for pencil programming :D ), or even THINKING about it until I've boosted my grades. Maybe next year?
Bazzy (6281)
how handle division that produces an irrational number?

Division only produces rational numbers
To keep infinite precision with rational numbers you can simply store them as fractions.
If you already have an integer class, writing a rational class on top of it is really easy.
Pages: 1234