首页 > 代码库 > 探寻C/C++中更快的大数(自然数集)模板
探寻C/C++中更快的大数(自然数集)模板
本文系fcbruce个人原创整理,转载请注明出处http://blog.csdn.net/u012965890/article/details/40432511,谢谢!
我们知道在C/C++中int型可处理-2^31~2^31-1(32位及以上编译器),long long型可处理-2^63~2^63-1的数据,这实际上是非常有限的,在很多情况下,我们往往会处理范围更大的数据。Java中有BigInteger类,python中想要多大就有多大(取决于内存),但是C/C++就显得有些乏力,这时候我们会手写大数类,用一个数组记录一个数,来模拟竖式计算。通常我们会一位一位地储存数据,这样易于实现,逻辑清晰,方便理解,但是一定程度上牺牲了效率,浪费了资源,那么能否多位存储数据并操作呢,显然是可以的。
我们知道int类型能表示的最大数量级为10^10左右,为了避免乘法溢出,我们不妨用一个int存储4位数字(10^4),可以轻易写下如下代码(仅含加、减、乘和比较操作):
/* * * Author : fcbruce <fcbruce8964@gmail.com> * * Time : Fri 24 Oct 2014 02:43:41 PM CST * */ #include <cstdio> #include <iostream> #include <sstream> #include <cstdlib> #include <algorithm> #include <ctime> #include <cctype> #include <cmath> #include <string> #include <cstring> #include <stack> #include <queue> #include <list> #include <vector> #include <map> #include <set> #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<max(len,b.len);i++) { int x=g; if (i<len) x+=s[i]; if (i<b.len) x+=b.s[i]; c.s[c.len++]=x%mod; g=x/mod; } return c; } void clean() { while (len>1 && s[len-1]==0) len--; } bign operator * (const bign &b) { bign c;c.len=len+b.len; for (int i=0;i<len;i++) for (int j=0;j<b.len;j++) c.s[i+j] += s[i] * b.s[j]; for (int i=0;i<c.len-1;i++) { c.s[i+1]+=c.s[i]/mod; c.s[i]%=mod; } c.clean(); return c; } bign operator - (const bign &b) { bign c;c.len=0; for (int i=0,g=0;i<len;i++) { int x=s[i]-g; if (i<b.len) x-=b.s[i]; if (x>=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<b.len; for (int i=0;i<len;i++) if (s[i]!=b.s[i]) return s[i]<b.s[i]; return false; } bool operator > (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<len;i++) if (s[i]!=b.s[i]) return false; return true; } bign operator += (const bign &b) { *this=*this+b; return *this; } }; int bign::width=4; int bign::mod=10000; int main() { #ifdef FCBRUCE // freopen("/home/fcbruce/code/t","r",stdin); #endif // FCBRUCE int T_T; scanf("%d",&T_T); bign a,b,c; char s1[233],s2[233],s[233]; while (T_T--) { scanf("%s %s",s1,s2); a=s1;b=s2; c=a+b; c.str(s); printf("%s ",s); c=a-b; c.str(s); printf("%s ",s); c=a*b; c.str(s); printf("%s\n",s); } return 0; }
其中void str(char *)函数为将该大数转换成字符串。
随机生成100000组10^82数量级以下的数据并进行对拍,没有发现错误。
long long能表示的数据范围更大,能压更多的位数,会不会更快呢?不妨一次压8位,对以上代码稍加改动即可
/* * * Author : fcbruce <fcbruce8964@gmail.com> * * Time : Fri 24 Oct 2014 02:43:41 PM CST * */ #include <cstdio> #include <iostream> #include <sstream> #include <cstdlib> #include <algorithm> #include <ctime> #include <cctype> #include <cmath> #include <string> #include <cstring> #include <stack> #include <queue> #include <list> #include <vector> #include <map> #include <set> #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<max(len,b.len);i++) { long long x=g; if (i<len) x+=s[i]; if (i<b.len) x+=b.s[i]; c.s[c.len++]=x%mod; g=x/mod; } return c; } void clean() { while (len>1 && s[len-1]==0) len--; } bign operator * (const bign &b) { bign c;c.len=len+b.len; for (int i=0;i<len;i++) for (int j=0;j<b.len;j++) c.s[i+j] += s[i] * b.s[j]; for (int i=0;i<c.len-1;i++) { c.s[i+1]+=c.s[i]/mod; c.s[i]%=mod; } c.clean(); return c; } bign operator - (const bign &b) { bign c;c.len=0; long long g=0ll; for (int i=0;i<len;i++) { long long x=s[i]-g; if (i<b.len) x-=b.s[i]; if (x>=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<b.len; for (int i=0;i<len;i++) if (s[i]!=b.s[i]) return s[i]<b.s[i]; return false; } bool operator > (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<len;i++) if (s[i]!=b.s[i]) return false; return true; } bign operator += (const bign &b) { *this=*this+b; return *this; } }; int bign::width=8; long long bign::mod=100000000ll; int main() { #ifdef FCBRUCE // freopen("/home/fcbruce/code/t","r",stdin); #endif // FCBRUCE int T_T; scanf("%d",&T_T); bign a,b,c; char s1[233],s2[233],s[233]; while (T_T--) { scanf("%s %s",s1,s2); a=s1;b=s2; c=a+b; c.str(s); printf("%s ",s); c=a-b; c.str(s); printf("%s ",s); c=a*b; c.str(s); printf("%s\n",s); } return 0; }
修改对拍代码,发现使用压8位的long long 版大数从性能上确实要优于压4位的int版大数,虽然int版偶尔会稍快于long long版,但平均性能上long long版要比int版快20%~60%(包括IO)
数据生成代码:
# # # Author : fcbruce <fcbruce8964@gmail.com> # # Time : Fri 24 Oct 2014 06:33:17 PM CST # # import random T_T=100000 print T_T for i in xrange(T_T): a=random.randint(0,1237648236422345678987655432349875934875632123131523784682932317237132418743972317); b=random.randint(0,12345678987623463824593658235543232123131238746239523172371376382423749824172324317); print a+b,a
标程代码:
# # # Author : fcbruce <fcbruce8964@gmail.com> # # 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 <fcbruce8964@gmail.com> # # 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 echo done
部分测试结果(运行时间单位:十亿分之一秒,测试环境:ubuntu10.04 ,编译开O2优化,gnu++0x,主频:2.26GHz × 2 ):
参考资料:
《算法竞赛入门经典》—— 刘汝佳
探寻C/C++中更快的大数(自然数集)模板