本站首页    管理页面    写新日志    退出


«November 2025»
日一二三四五六
1
2345678
9101112131415
16171819202122
23242526272829
30


公告

 


我的分类（专题）

日志更新

最新评论

留言板

链接


Blog信息
blog名称:Mr.Sun
日志总数:7
评论数量:22
留言数量:1
访问次数:53855
建立时间:2006年3月9日




[C / C++]关于用C实现大数字的运算
原创空间,  软件技术

小骏 发表于 2006/3/9 20:29:27

用标准C语言,计算机能帮你算的最大的数字也就限于2的32次方.超出了这个范围,就会溢出了.但是密码算法里很多算法,如著名的RSA,就要求要计算2的1024次方甚至更大的数量级的数字.而且,解决了这个问题也可以对计算机的理解有帮助. 首先,先看一下加法. 有两个思路可以参考: 如果有两个占用8个字节的内存单元要进行加法运算,也就是可以表示成2个int型元素组成的数组要进行加法运算,如果按照数组元素进行运算的话,那么低位的进行运算之后溢出了,那怎么办,关键就在于如何得知溢出.如果每次进行的运算不是2的32次方,而是小于2的32次方,那么溢出之后就可以知道.所以,我们只需要利用两个int型的临时空间,每次分别将要进行加法运算的两个大数字放进去24位,为什么要放24位,放31位不是更节省吗?但是31位不方便运算.所以一次就放3个字节进去.然后进行计算机提供的加法运算,之后来判断2个有效位为24位的数字进行运算的结果的第25位,如果该位为1,则表示运算溢出,否则无溢出.这种方法一般般,不好也不坏.呵呵.   另外一种方法就比较容易理解. 首先有一条原则就是:两个数字进行加法运算,结果无论如何也比其中任意一个数字要大.如果刚才的条件不成立,则表示溢出. 这样就可以按照数组元素依次进行运算了,只是每次运算完都要判断以便进位. 减法,乘法,除法就不多说了. 除了加减乘除,还有几个比较重要的运算.比如模幂运算.比如:计算A的B次方模M的结果.其中,A,B,M均为2的1024次方这样数量级的数字. 如果硬是要用加减乘除来计算,那么算到什么时候(反正是很远之后了,我也没具体算过).那么用什么办法来解决呢. 首先,考虑一个问题,如果我们要用一张张的纸叠加起来叠到月球上去,那么似乎这个问题是不可能的,但是如果我们用一张纸对折对折再对折,30多次之后就可以到月球了,呵呵,就是这个思路. 将无限化为有限,将指数级化为对数级. 我们知道,A的2次方=A的1次方*A的1次方.A的4次方=A的2次方*A的2次方. 还有,A的N次方模M,计算进行时可以在当结果大于M的时候就先取模. OK,前期工作就做到这里,现在开始正式的计算. 我们先把A的1次方.2次方.4.8......直到LOG以2为底B的对数次方模M的结果存储起来,然后将B视为2进制数. 比如:B的二进制形式为:      1   0   0   0   1   0   0   0   10001000 A的1,2,4,8次方的中间结果:a    b    c   d   .... 然后当B的二进制形式中出现1的时候,找出中间结果中相对应的一个结果,遍历B的二进制形式,将出现1的时候相对应的中间结果相乘然后模M,就可以得到最终结果. 其实能看到这里也挺不容易了,呵呵,这个问题我也只能表达成这样了,如果有问题,可以参考代码.   写了好多,手累...   不说什么了,贴代码: 注:由于个人原因,代码写到一半尚为完成. 以下先是大数字进行加减乘法的实现.   #include <stdio.h>#include <stdlib.h>typedef unsigned int BigInt;//定义unsigned int型为BigInt型 unsigned int Length(BigInt *input)//求一个BigInt型所占的空间长度{ int i=0; while(input[i]!=-1) {  i++; } return i;} bool NewInt(BigInt **input,unsigned int n)//为一个BigInt型分配空间{ if(((*input)=(BigInt*)malloc(n*sizeof(BigInt)+1))!=NULL){  for(int i=0;i<n;i++)   (*input)[i]=0;  (*input)[n]=-1;  return true; } return false;} void Print(BigInt *input)//打印一个BigInt型{ int i; for(i=Length(input)-1;i>=0;i--){  if(input[i]<16)   printf("0");  printf("%x",input[i]); } printf("\n");} unsigned int Max(BigInt *part1,BigInt *part2)//计算两个BigInt型中较长一个的长度{ if(Length(part1)>=Length(part2))  return Length(part1); else  return Length(part2);} unsigned int Min(BigInt *part1,BigInt *part2)//计算两个BigInt型中较短一个的长度{ if(Length(part1)>=Length(part2))  return Length(part2); else  return Length(part1);} void Add(BigInt *result,BigInt *part1,BigInt *part2)//加法,长的是part1,短的是part2{ int sum; int flag=0; int i; for(i=0;i<Min(part1,part2);i++){  sum=part1[i]+part2[i]+flag;  result[i]=sum&0xFF;  flag=(sum>>8);  sum=0; } for(i=Min(part1,part2);i<Max(part1,part2);i++){  sum=part1[i]+flag;  result[i]=sum&0xFF;  flag=(sum>>8);  sum=0; } result[Max(part1,part2)]=flag;} void Sub(BigInt *result,BigInt *part1,BigInt *part2)//减法,长的是part1,短的是part2{ int flag=0; int i; for(i=0;i<Min(part1,part2);i++){  if((part1[i]-part2[i]-flag)<=part1[i]){   result[i]=part1[i]-part2[i]-flag;   flag=0;  }else{   result[i]=256+part1[i]-part2[i]-flag;   flag=1;  } } for(i=Min(part1,part2);i<Max(part1,part2);i++){  if((part1[i]-flag)<=part1[i]){   result[i]=part1[i]-flag;   flag=0;  }else{   result[i]=256+part1[i]-flag;   flag=1;  } }} void Mult(BigInt *result,BigInt *part1,BigInt *part2)//乘法{ unsigned int a=0; unsigned int b=0; unsigned int c=0; unsigned int mult=0; int i; int j; int k; BigInt *temp; while(!NewInt(&temp,Length(part1)+Length(part2)))  ; for(i=0;i<Length(part1);i++){  for(j=0;j<Length(part2);j++){   mult=result[i+j]+part1[j]*part2[i]+c;   a=(mult>>8);   b=(mult&0xFF);   c=a;   temp[i+j]=b;  }  c=0;  temp[i+j]=a;  for(k=0;k<Length(temp);k++)   result[k]=temp[k]; }} int Compare(BigInt *part1,BigInt *part2)//part1和part2作比较,part1大返回1,part2大返回2,相等返回0{ if(Length(part1)>Length(part2))  return 1; if(Length(part1)<Length(part2))  return 0; BigInt *temp; while(!NewInt(&temp,Length(part1)))  ; Sub(temp,part1,part2); int j=0; for(int i=0;i<Length(temp);i++){  if(temp[i]!=0)   j=1; } if(j==0)  return 0; if(part1[Length(part1)-1]>temp[Length(temp)-1])  return 2; else  return 1;} void Squ(BigInt *result,BigInt *part1)//平方{} void Add1(BigInt *part1)//自加1{ unsigned int flag; unsigned int sum; sum=part1[0]+1; flag=(sum>>8); part1[0]=sum&0xFF; for(int i=1;i<Length(part1);i++){  sum=flag+part1[i];  part1[i]=sum&0xFF;  flag=(sum>>8); }} void Sub1(BigInt *part1)//自减1{ unsigned int flag=0; unsigned int sub; sub=part1[0]-1; if(sub>part1[0]){  part1[0]=256+part1[0]-1;  flag=1; }else{  part1[0]=part1[0]-1;  flag=0; } for(int i=1;i<Length(part1);i++){  sub=part1[i]-flag;  if(sub>part1[i]){   part1[i]=256+part1[i]-flag;   flag=1;  }else{   part1[i]=part1[i]-flag;   flag=0;  } }} void Zero(BigInt *input)//清零{ for(int i=0;i<Length(input);i++){  input[i]=0; }} void Copy(BigInt *output,BigInt *input)//复制,从高位开始,input较短,output较长{ for(int i=0;i<Length(input);i++)  output[i+Length(input)]=input[i];} void Copy1(BigInt *output,BigInt *input)//复制,从高位开始,input较长,output较短{ for(int i=0;i<Length(output);i++)  output[i]=input[i+Length(output)];} 对于模幂没有基于大数字写,只是基于INT型来写了一个DEMO.以后会尽快补上.呵呵. int Pow(int a,int b,int p)//a的b次方,并且是在模p上{ unsigned int temp1[32];//a的2进制表示 unsigned int temp2[32];//b的2进制表示 unsigned int result1[32];//a的（2的0-31）次方模p的结果 unsigned int final=0; if(b==0)  return 1; for(int i=0;i<32;i++){  temp1[i]=0;  temp2[i]=0;  result1[i]=0; } for(int i=0;i<32;i++){  temp1[i]=getBit(i,a);  temp2[i]=getBit(i,b); } result1[0]=a%p; for(int i=0;i<31;i++){  result1[i+1]=Squ(result1[i],p); } final=result1[FindFirstNotZero(temp2)]%p; for(int i=FindFirstNotZero(temp2)+1;i<32;i++){  if(temp2[i]==0)   ;  else{   final=Mult(final,result1[i],p)%p;  } } return final;}


阅读全文(4466) | 回复(4) | 编辑 | 精华
 


回复:关于用C实现大数字的运算
原创空间,  软件技术

jojoke(游客)发表评论于2007/12/19 19:53:56

首先,考虑一个问题,如果我们要用一张张的纸叠加起来叠到月球上去,那么似乎这个问题是不可能的,但是如果我们用一张纸对折对折再对折,30多次之后就可以到月球了,呵呵,就是这个思路. 2^30 = 1073741824 每张纸的厚度设为 0.2毫米， 那么对折30次后的厚度为214748364毫米 = 214748米 = 214公里，达不到月球啊 -_-!!


个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除
 


回复:关于用C实现大数字的运算
原创空间,  软件技术

jojoke(游客)发表评论于2007/12/19 17:12:21

以下引用silentpose(游客)在2006-4-16 11:14:19的评论:有没有用C++来实现大数类的+，-，*，/，>=,<=,++,--的列子呀,求救求救,救命啊!十万火急 关于大数运算的c++类，欢迎到我的空间看看 http://jojoke.cnblogs.com/

个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除
 


回复:关于用C实现大数字的运算
原创空间,  软件技术

你好(游客)发表评论于2007/1/10 15:33:18

你后来 模幂基于大数 的代码写好了吗 ？ 如果写好了能不能把所有的完整的代码给我发一份呢 谢谢你了 我的EMAIL： hynchina@gmail.com

个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除
 


回复:关于用C实现大数字的运算
原创空间,  软件技术

silentpose(游客)发表评论于2006/4/16 11:14:19

有没有用C++来实现大数类的+，-，*，/，>=,<=,++,--的列子呀,求救求救,救命啊!十万火急

个人主页 | 引用回复 | 主人回复 | 返回 | 编辑 | 删除
 


» 1 »

发表评论：
昵称：
密码：
主页：
标题：
验证码：  (不区分大小写,请仔细填写,输错需重写评论内容！)



站点首页 | 联系我们 | 博客注册 | 博客登陆

Sponsored By W3CHINA
W3CHINA Blog 0.8 Processed in 0.500 second(s), page refreshed 144807265 times.
《全国人大常委会关于维护互联网安全的决定》  《计算机信息网络国际联网安全保护管理办法》
苏ICP备05006046号