4

I was just wondering which will the best BigInteger class in C++ for programming contests which do not allow external libraries?

Mainly I was looking for a class which could be used in my code( I will of course write it on my own, on similar grounds ).

The primary factors which I think are important are( according to their importance ):

  1. Arbitrary length numbers and their operations should be supported.

  2. Should be as small as possible, code-wise. Usually there's a limit on the size of the source code which can be submitted to ~50KB, so the code should be ( much )smaller than that.

  3. Should be as fast as possible. I read somewhere that bigInt classes take O( log( n ) ) time, so this should have a similiar complexity. What I mean is that it should be as fast as possible.

Kijewski
  • 25,517
  • 12
  • 101
  • 143
Khushman Patel
  • 1,066
  • 2
  • 13
  • 23
  • 7
    The one you write yourself. If it's a contest, you're supposed to be submitting your work, not someone else's. – Ben Voigt Dec 31 '11 at 06:21
  • I wrote a simple one in about 1000 lines, its not too hard. – Mooing Duck Dec 31 '11 at 06:25
  • 1
    @BenVoigt - True, but an already-made class will most probably have a good implementation, which I, not being that good of either a mathematician or a programmer, will not be able to achieve. So I could get ideas and hints from the class. I cannot exactly use that class since it would violate the rules, but I can implement one based on similar ideas. – Khushman Patel Dec 31 '11 at 06:33
  • @MooingDuck - Is the code open-licensed? I'd like to read it and the implement my own, if possible. – Khushman Patel Dec 31 '11 at 06:34
  • 3
    @Skkard: You didn't say you wanted something to learn from, you said you wanted to "cut+paste", and then you worry whether the existing code would fit within your 50kB limit. And you're concerned about the speed. That doesn't sound like a rewrite. I would suggest that you find an implementation in some other language to study and learn from, then you won't be tempted to directly reuse. – Ben Voigt Dec 31 '11 at 06:46
  • @BenVoigt - I got my mistake. Hadn't thought of the fact that it'd be cheating. I've edited the question details to reflect that. Thank you for correcting me. Do you have any suggestions about which implementation to study from? – Khushman Patel Dec 31 '11 at 06:50
  • 2
    Well, really I would suggest finding the solution that doesn't require arbitrary precision arithmetic. All the contest problems I've seen can be solved without biginteger math. – Ben Voigt Dec 31 '11 at 07:00
  • There's also good information at this question: http://stackoverflow.com/questions/3629165/how-do-bignums-implementations-work And http://stackoverflow.com/questions/6307458/is-there-a-generally-accepted-alternative-to-gmp-for-arbitrary-precision – Ben Voigt Dec 31 '11 at 07:01
  • @Ben Voigt: codechef has many questions that require arbitrary precision arithmetic. – Mooing Duck Dec 31 '11 at 17:15
  • @MooingDuck: Example link please. I'm pretty sure the point of those exercises is to find a smarter algorithm. – Ben Voigt Dec 31 '11 at 17:25
  • @BenVoigt: http://www.codechef.com/problems/FCTRL2/ requires you to calculate 100!, which is 158 decimal digits. – Mooing Duck Dec 31 '11 at 17:50
  • @MooingDuck: Ah ok. Most contests use a variation of that problem which just require printing the first and last 6 digits -- the last 6 you get via modulo arithmetic (plus they become zero very quickly), the first 6 can be handled by computing sum of logarithms. – Ben Voigt Dec 31 '11 at 19:04

1 Answers1

3

So far I've only needed unsigned integer big numbers for codechef, but codechef only gives 2KB, so I don't have the full implementation up there anywhere, just the members needed for that problem. My code also assumes that long long has at least twice as many bits as a unsigned, though that's pretty safe. The only real trick to it is that different biguint classes may have different data lengths. Here's summaries of the more interesting functions.

#define BIG_LEN()  (data.size()>rhs.data.size()?data.size():rhs.data.size())
    //the length of data or rhs.data, whichever is bigger
#define SML_LEN()  (data.size()<rhs.data.size()?data.size():rhs.data.size())
    //the length of data or rhs.data, whichever is smaller
const unsigned char baselut[256]={ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                                   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                                   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                                   0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 0, 0, 0,
                                   0,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,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
                                  };
const unsigned char base64lut[256]={ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                                     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
                                     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,62, 0, 0, 0,63,
                                    52,53,54,55,56,57,58,59,60,61, 0, 0, 0, 0, 0, 0,
                                     0, 0, 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, 0, 0, 0, 0, 0,
                                     0,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, 0, 0, 0, 0, 0
                                    };
    //lookup tables for creating from strings

void add(unsigned int amount, unsigned int index)
    adds amount at index with carry, simplifies other members
void sub(unsigned int amount, unsigned int index)
    subtracts amount at index with borrow, simplifies other members
biguint& operator+=(const biguint& rhs)
    resize data to BIG_LEN()
    int carry = 0
    for each element i in data up to SML_LEN()
        data[i] += rhs.data[i] + carry
        carry = ((data[i]<rhs[i]+carry || (carry && rhs[i]+carry==0)) ? 1u : 0u);
   if data.length > rhs.length
       add(carry, SML_LEN())
biguint& operator*=(const biguint& rhs) 
    biguint lhs = *this;
    resize data to data.length + rhs.length
    zero out data
    for each element j in lhs
        long long t = lhs[j]
        for each element i in rhs (and j+i<data.size)
            t*=rhs[i];
            add(t&UINT_MAX, k);
            if (k+1<data.size())
                add(t>>uint_bits, k+1);
//note this was public, so I could do both at the same time when needed
//operator /= and %= both just call this
//I have never needed to divide by a biguint yet.
biguint& div(unsigned int rhs, unsigned int & mod) 
    long long carry = 0
    for each element i from data length to zero
        carry = (carry << uint_bits) | data[i]
        data[i] = carry/rhs;
        carry %= rhs
    mod = carry
//I have never needed to shift by a biguint yet
biguint& operator<<=(unsigned int rhs) 
    resize to have enough room, always at least 1 bigger
    const unsigned int bigshift = rhs/uint_bits;
    const unsigned int lilshift = rhs%uint_bits;
    const unsigned int carry_shift = (uint_bits-lilshift)%32;
    for each element i from bigshift to zero
         t = data[i-bigshift] << lilshift;
         t |= data[i-bigshift-1] >> carry_shift;
         data[i] = t;
    if bigshift < data.size
        data[bigshift] = data[0] << lilshift
    zero each element i from 0 to bigshift
std::ofstream& operator<<(std::ofstream& out, biguint num)
    unsigned int mod
    vector reverse
    do 
        num.div(10,mod);
        push back mod onto reverse
    while num greater than 0
    print out elements of reverse in reverse
std::ifstream& operator>>(std::ifstream& in, biguint num)
    char next
    do
        in.get(next) 
    while next is whitespace
    num = 0
    do 
        num = num * 10 + next
    while in.get(next) and next is digit
//these are handy for initializing to known values.
//I also have constructors that simply call these
biguint& assign(const char* rhs, unsigned int base)
    for each char c in rhs
        data *= base
        add(baselut[c], 0)
biguint& assign(const char* rhs, std::integral_constant<unsigned int, 64> base)
    for each char c in rhs
        data *= base
        add(base64lut[c], 0)
//despite being 3 times as much, code, the hex version is _way_ faster.
biguint& assign(const char* rhs, std::integral_constant<unsigned int, 16>) 
    if first two characters are "0x" skip them
    unsigned int len = strlen(rhs);
    grow(len/4+1);
    zero out data
    const unsigned int hex_per_int = uint_bits/4;
    if (len > hex_per_int*data.size()) { //calculate where first digit goes
        rhs += len-hex_per_int*data.size();
        len = hex_per_int*data.size();
    }
    for(unsigned int i=len; i --> 0; ) { //place each digit directly in it's place
        unsigned int t = (unsigned int)(baselut[*(rhs++)]) << (i%hex_per_int)*4u;
        data[i/hex_per_int] |= t;
    }

I also made specializations for multiplication, divide, modulo, shifts and others for std::integral_constant<unsigned int, Value>, which made massive improvements to my serializing and deserializing functions amongst others.

Mooing Duck
  • 64,318
  • 19
  • 100
  • 158