c++ - 哪个是用于编程竞赛的优秀 C++ BigInteger 类？

Question

我只是想知道对于不允许外部库的编程竞赛，C++ 中哪个 BigInteger 类最好？

主要是我在寻找一个可以在我的代码中使用的类(我当然会基于类似的理由自己编写它)。

我认为重要的主要因素是(根据它们的重要性):

1. 应支持任意长度的数字及其操作。

2. 在代码方面应该尽可能小。通常可以提交的源代码大小有一个限制，大约 50KB，因此代码应该(远)小于这个大小。

3. 应该尽可能快。我在某处读到 bigInt 类需要 O( log( n ) ) 时间，所以这应该具有类似的复杂性。我的意思是它应该尽可能快。

Answer 1

到目前为止，我只需要 codechef 的无符号整数大数，但 codechef 只​​提供 2KB，所以我没有任何地方的完整实现，只有该问题所需的成员。我的代码还假定 long long位数至少是 unsigned 的两倍，虽然那很安全。唯一真正的诀窍是不同的 biguint类可能有不同的数据长度。以下是更有趣的函数的摘要。

#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;
    }

我还对 std::integral_constant<unsigned int, Value> 进行了乘法、除法、取模、移位等的特化处理，它对我的​​序列化和反序列化函数以及其他函数进行了大规模改进。