探索C/C++大数快(自然数)模板-白红宇

探索C/C++大数快(自然数)模板

阅读量：7123 次

发布时间：2019-06-28

本文共 6336 字，大约阅读时间需要 21 分钟。

本文个人原创整理。转载请注明出处，谢谢。

我们知道在C/C++中int型可处理-2^31~2^31-1(32位及以上编译器)，long long型可处理-2^63~2^63-1的数据,这实际上是非常有限的。在非常多情况下。我们往往会处理范围更大的数据。

Java中有BigInteger类，python中想要多大就有多大（取决于内存），可是C/C++就显得有些乏力，这时候我们会手写大数类。用一个数组记录一个数，来模拟竖式计算。

通常我们会一位一位地储存数据，这样易于实现，逻辑清晰，方便理解，可是一定程度上牺牲了效率，浪费了资源，那么是否能多位存储数据并操作呢。显然是能够的。

我们知道int类型能表示的最大数量级为10^9左右，为了避免乘法溢出，我们最好还是用一个int存储4位数字(10^4)，能够轻易写下例如以下代码（仅含加、减、乘和比較操作）：

/* * * Author : fcbruce 
     
       * * Time : Fri 24 Oct 2014 02:43:41 PM CST * */#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    #include 
                     
                      #define sqr(x) ((x)*(x))#define LL long long#define itn int#define INF 0x3f3f3f3f#define PI 3.1415926535897932384626#define eps 1e-10#ifdef _WIN32 #define lld "%I64d"#else #define lld "%lld"#endif#define maxm #define maxn using namespace std;const int maxl = 233;struct bign{ static int width; static int mod; int len,s[maxl]; bign() { memset(s,0,sizeof s); len=1; } bign(int num) { *this=num; } bign(long long num) { *this=num; } bign(const char *s) { *this=s; } bign operator = (int num) { char s[maxl]; sprintf(s,"%d",num); *this=s; return *this; } bign operator = (long long num) { char s[maxl]; sprintf(s,lld,num); *this=s; return *this; } bign operator = (const char *s) { int l=strlen(s); len=0; for (int i=l-1;i>=0;i-=width,len++) { (*this).s[len]=0; for (int j=max(0,i-width+1);j<=i;j++) (*this).s[len]=(*this).s[len]*10+s[j]-'0'; } return *this; } void str(char *s) { char format[5]; sprintf(format,"%%0%dd",width); for (int i=len-1,j=0;i>=0;i--,j++) sprintf(s+j*width,format,(*this).s[i]); int j=0; while (s[j]=='0' && s[j+1]!='\0') j++; strcpy(s,s+j); } bign operator + (const bign &b)const { bign c; c.len=0; for (int i=0,g=0;g || i
                      
                       1 && s[len-1]==0) len--; } bign operator * (const bign &b) { bign c;c.len=len+b.len; for (int i=0;i
                       
                        =0) g=0; else { g=1; x+=mod; } c.s[c.len++]=x; } c.clean(); return c; } bool operator < (const bign &b)const { if (len!=b.len) return len
                        
                         =0;i--) if (s[i]!=b.s[i]) return s[i]
                         
                           (const bign &b)const { return b<*this; } bool operator <= (const bign &b)const { return !(b>*this); } bool operator >= (const bign &b)const { return !(b<*this); } bool operator == (const bign &b)const { if (len!=b.len) return false; for (int i=0;i

当中void str(char *)函数为将该大数转换成字符串。

随机生成100000组10^82数量级下面的数据并进行对拍，没有发现错误。

long long能表示的数据范围更大，能压很多其它的位数。会不会更快呢？最好还是一次压8位。对以上代码稍加修改就可以

/* * * Author : fcbruce 
     
       * * Time : Fri 24 Oct 2014 02:43:41 PM CST * */#include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    #include 
                     
                      #define sqr(x) ((x)*(x))#define LL long long#define itn int#define INF 0x3f3f3f3f#define PI 3.1415926535897932384626#define eps 1e-10#ifdef _WIN32 #define lld "%I64d"#else #define lld "%lld"#endif#define maxm #define maxn using namespace std;const int maxl = 233;struct bign{ static int width; static long long mod; int len; long long s[maxl]; bign() { memset(s,0,sizeof s); len=1; } bign(int num) { *this=num; } bign(long long num) { *this=num; } bign(const char *s) { *this=s; } bign operator = (int num) { char s[maxl]; sprintf(s,"%d",num); *this=s; return *this; } bign operator = (long long num) { char s[maxl]; sprintf(s,lld,num); *this=s; return *this; } bign operator = (const char *s) { int l=strlen(s); len=0; for (int i=l-1;i>=0;i-=width,len++) { (*this).s[len]=0; for (int j=max(0,i-width+1);j<=i;j++) (*this).s[len]=(*this).s[len]*10+s[j]-'0'; } return *this; } void str(char *s) { char format[10]; sprintf(format,"%%0%d%s",width,lld+1); for (int i=len-1,j=0;i>=0;i--,j++) sprintf(s+j*width,format,(*this).s[i]); int j=0; while (s[j]=='0' && s[j+1]!='\0') j++; strcpy(s,s+j); } bign operator + (const bign &b)const { bign c; c.len=0; long long g=0ll; for (int i=0;g!=0ll || i
                      
                       1 && s[len-1]==0) len--; } bign operator * (const bign &b) { bign c;c.len=len+b.len; for (int i=0;i
                       
                        =0) g=0; else { g=1; x+=mod; } c.s[c.len++]=x; } c.clean(); return c; } bool operator < (const bign &b)const { if (len!=b.len) return len
                        
                         =0;i--) if (s[i]!=b.s[i]) return s[i]
                         
                           (const bign &b)const { return b<*this; } bool operator <= (const bign &b)const { return !(b>*this); } bool operator >= (const bign &b)const { return !(b<*this); } bool operator == (const bign &b)const { if (len!=b.len) return false; for (int i=0;i

改动对拍代码。发现使用压8位的long long 版大数从性能上确实要优于压4位的int版大数，尽管int版偶尔会稍快于long long版，但平均性能上long long版要比int版快20%~60%(包含IO)

数据生成代码：

### Author : fcbruce 
     
      ## Time : Fri 24 Oct 2014 06:33:17 PM CST##import randomT_T=100000print T_Tfor i in xrange(T_T):  a=random.randint(0,1237648236422345678987655432349875934875632123131523784682932317237132418743972317);  b=random.randint(0,12345678987623463824593658235543232123131238746239523172371376382423749824172324317);  print a+b,a

标程代码：

### Author : fcbruce 
     
      ## Time : Fri 24 Oct 2014 06:38:52 PM CST##n=input()for i in xrange(n):  a,b=map(int,raw_input().split())  print a+b,a-b,a*b

对拍代码：

#!/bin/bash## Author : fcbruce 
     
      ## Time : Fri 24 Oct 2014 07:01:27 PM CST##while true; do  python data.py > input  python std.py < input > std_output  begin_time_int=$(date "+%s%N")  ./bign_int < input >bign_int_output  end_time_int=$(date "+%s%N")     begin_time_longlong=$(date "+%s%N")  ./bign_longlong < input >bign_longlong_output  end_time_longlong=$(date "+%s%N")   use_time_int=$(expr $end_time_int - $begin_time_int)  use_time_longlong=$(expr $end_time_longlong - $begin_time_longlong)  echo "bign int"  diff std_output bign_int_output   if [ $? -ne 0 ]; then     echo "Wrong Answer"    break;  else    echo "Accepted"    echo "run time : " $use_time_int  fi  echo  echo "bign long long"  diff std_output bign_longlong_output   if [ $? -ne 0 ]; then     echo "Wrong Answer"    break;  else    echo "Accepted"    echo "run time : " $use_time_longlong  fi  echo  test $use_time_longlong -lt $use_time_int   if [ $? -ne 0 ] ; then    echo "int faster"  else    echo "long long faster"  fi  echo  echodone

部分測试结果（执行时间单位：十亿分之中的一个秒，測试环境：ubuntu10.04 ,编译开O2优化。gnu++0x。主频：2.26GHz × 2 ）：

参考资料：

《算法入门经典大赛》—— 刘如家

你可能感兴趣的文章