这是一个好的C + + BigInteger类的编程比赛？ [英] Which is a good C++ BigInteger class for programming contests?

问题描述

我只是想知道在C ++中最好的BigInteger类是不允许外部库的编程比赛。

主要是我在寻找一个类，在我的代码中使用（我当然会基于类似的理由自己写它）。

我认为重要的主要因素是（根据它们的重要性）

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

   应该尽可能小，代码方面。通常对源代码的大小有一个限制，可以提交到〜50KB，所以代码应该比那个小很多。




2. 尽可能快。我读某处bigInt类需要 O（log（n））时间，所以这应该有一个类似的复杂性。

解决方案

到目前为止，我只需要无符号整数大数字codechef，但codechef只提供2KB，所以我没有完全实现上面有任何地方，只是那个问题所需的成员。我的代码还假设 long long 的位数至少是无符号的两倍，但这是相当安全的。唯一真正的窍门是不同的 biguint 类可能有不同的数据长度。

  #define BIG_LEN（）（data.size（）> rhs.data.size （）？data.size（）：rhs.data.size（））
 //数据长度或rhs.data，取大者
 #define SML_LEN（）（data.size < rhs.data.size（）？data.size（）：rhs.data.size（））
 //数据长度或rhs.data，取小者
 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,0,0,0,0，
 0，1，2，3，4，5，6，7，8，9，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，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 
 }; 
 //用于从字符串创建的查找表
 
 void add（unsigned int amount，unsigned int index）
在带有进位的索引处添加量，简化其他成员
 void sub（unsigned int amount，unsigned int index）
在借用索引减去金额，简化其他成员
 biguint&运算符+ =（const biguint& rhs）
将数据重新调整大小到BIG_LEN（）
 int carry = 0 
对于数据中的每个元素i到SML_LEN（）
 data [i] + = rhs.data [i] + carry 
 carry =（（data [i]  if data.length> rhs.length 
 add（carry，SML_LEN（））
 biguint& operator * =（const biguint& rhs）
 biguint lhs = * this; 
将数据大小调整为data.length + rhs.length 
清零数据
对于lhs 
中的每个元素j long long t = lhs [j] 
每个元素i在rhs（和j + i t * = rhs [i]; 
 add（t& UINT_MAX，k）; 
 if（k + 1  add（t>> uint_bits，k + 1）; 
 //注意这是公开的，所以我可以在需要的同时做两个
 // operator / =和％=两者都只是调用这个
 //我从来没有需要划分通过一个biguint。 
 biguint&对于每个元素i，从数据长度到零，
进位=（进位<< uint_bits）|对于每个元素i，从数据长度到零的div（unsigned int rhs，unsigned int& mod） data [i] 
 data [i] = carry / rhs; 
 carry％= rhs 
 mod = carry 
 //我从来不需要换一个biguint但
 biguint&运算符< <=（unsigned int rhs）
 resize有足够的空间，总是至少有一个更大的
 const unsigned int bigshift = rhs / uint_bits; 
 const unsigned int lilshift = rhs％uint_bits; 
 const unsigned int carry_shift =（uint_bits-lilshift）％32; 
每个元素i从bigshift到零
 t = data [i-bigshift]< ; 
 t | = data [i-bigshift-1]> carry_shift; 
 data [i] = t; 
 if bigshift< data.size 
 data [bigshift] = data [0]<< lilshift 
每个元素i从0到bigshift都为零
 std :: ofstream&运算符<<<（std :: ofstream& out，biguint num）
 unsigned int mod 
 vector reverse 
 do 
 num.div（10，mod） 
将mod推回到
，num大于0 
打印出反向的元素
 std :: ifstream&运算符>>>（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），next是数字
 //这些对于初始化为已知值非常方便。 
 //我也有构造函数，简单地调用这些
 biguint&赋值（const char * rhs，unsigned int base）
为每个字符c在rhs 
 data * = base 
 add（baselut [c]，0）
 biguint&对于rhs中的每个char c，赋值（const char * rhs，std :: integral_constant< unsigned int，64> base）* = base 
 add（base64lut [c]，0） 
 //尽管是3倍的代码，十六进制版本是_way_更快。 
 biguint&如果前两个字符为0x，则跳过它们
 unsigned int len = strlen（rhs）;如果前两个字符为0x 
 grow（len / 4 + 1）; 
 zero out data 
 const unsigned int hex_per_int = uint_bits / 4; 
 if（len> hex_per_int * data.size（））{//计算第一个数字的位置
 rhs + = len-hex_per_int * data.size（）; 
 len = hex_per_int * data.size（）; 
} 
 for（unsigned int i = len; i  - > 0;）{//将每个数字直接放在它的位置
 unsigned int t =（unsigned int）（baselut [ *（rhs ++）]）< （i％hex_per_int）* 4u; 
 data [i / hex_per_int] | = t; 
} 
  

我还对乘法，除法，模， code> std :: integral_constant< unsigned int，Value> ，这对我的序列化和反序列化功能做了大量的改进。

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.

解决方案

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.

这篇关于这是一个好的C + + BigInteger类的编程比赛？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！