編程競賽是一個很好的C++ BigInteger類嗎？

Question

我只是想知道哪個最好的BigInteger類在C + +編程比賽不允許外部庫？

主要是我正在尋找一個可以在我的代碼中使用的類（當然我會在類似的地方寫下它）。

，我認爲主要的因素（根據其重要性）是很重要的：

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>，這使得大量改善我的序列化和反序列化功能，其中包括人提出了乘法，除法，取模，班次專業化等。