大数运算的简介
大数运算，顾名思义，就是很大的数值的数进行一系列的运算。
我们知道，在数学中，数值的大小是没有上限的，但是在计算机中，由于字长的限制，计算机所能表示的范围是有限的，当我们对比较小的数进行运算时，如：1234+5678，这样的数值并没有超出计算机的表示范围，所以可以运算。但是当我们在实际的应用中进行大量的数据处理时，会发现参与运算的数往往超过计算机的基本数据类型的表示范围，比如说，在天文学上，如果一个星球距离我们为100万光年，那么我们将其化简为公里，或者是米的时候，我们会发现这是一个很大的数。这样计算机将无法对其进行直接计算。
可能我们认为实际应用中的大数也不过就是几百位而已，实际上，在某些领域里，甚至可能出现几百万位的数据进行运算，这是我们很难想象的。如果没有计算机，那么计算效率可想而知。
既然在计算机中无法直接表示，那么大数到底如何进行运算呢，学习过数据结构的都知道线性表，将大数拆分然后存储在线性表中，不失为一个很好的办法。
大数除法，可以类比人类手算，添位比较取商，中间结果与除数相减所得到的差参与下一轮运算，直到结束。这里需要注意添位时，商有时需要补零，而且除法运算需要使用加、减、乘、比较运算。
JAVA中如何精确进行大数计算
使用Java.math包中的 BigInteger, BigDecimal这两个类。 这两个类可以处理包含任意长度数字序列的数值。BigInteger类实现任意精度的整数运算，BigDicimal实现任意精度的浮点数运算。 语出Core Java
大数四则运算完整代码
struct Node // 定义一个双向链表用来存贮结果
{
char data; // 数据*定义为字符的原因：要显示负号
Node *next; // 尾指针
Node *ahead; // 首指针
};
/*————————————————————————–
*函数名称： 大数加法
*函数过程：1 比较两个数那一个长
* 2 以长的作为循环次数
* 3 对应项相加 进位存贮直到下高位相加用
* 4 直到循环结束
* 5 !!!!!!没设计负数相加
*入口参数：numa，numb，result字符串
*出口参数：无
*编辑环境：winSP2 + VC2003 + C++
*————————————————————————–*/
void addition(char *numa, char *numb,char *result) // 计算两大数之和
{
char *pna = findend(numa); // 指向numa的一个指针。point numa pna 指向乘数的最低位，
char *pnb = findend(numb); //指向numb的一个指针 //pnb 指向被乘数的最低位，
int along=(int)strlen(numa); //标记数字a的长度；
int blong=(int)strlen(numb); //标记数字b的长度；
int times = 0; // 标致要计算多少次。
int carry=0,temp_result; //存贮进位 和临时结果的
Node *head, // 用于存贮头指针
*pstart, // 用于存贮计算时的首指针
*pnew; //作于申请新结点
head = pstart =new Node; //初始化首结点和头结点。
pstart -》 data = 0;
pstart -》 next = NULL;
pstart -》 ahead = NULL;
if (abigerb(numa ,numb)》=1)
times = (int)strlen(numa); //比较两个字符串长度，以大的作为循环次数
else
{
times = (int)strlen(numb);
pna = findend(numb); //交换指针
pnb = findend(numa);
along=(int)strlen(numb); //标记数字a的长度；
blong=(int)strlen(numa); //标记数字b的长度；
}
while ((times– && (times》=0))|| carry != 0)
{
if(!pstart-》next) //如果当前为空结点，则申请新结点
{
pnew = new Node;
pnew -》 data = 0;
pnew -》 next = NULL;
pnew -》 ahead = pstart;
pstart -》 next = pnew;
}
else temp_result =(pstart-》data +(*pna-48)+(*pnb-48)+carry) ; //自身的值+新值+进位 作为当前的新值
pstart -》 data = temp_result%10; //存贮个位
carry = temp_result/10; //存贮进位
pstart = pstart -》 next; //结点移动
blong–;
if(blong》0)pnb–; //指针移向被加数高位
else *pnb=48; //之后相减就变为了0不作任何运算；
pna–; //加数指针移动，
}
pstart =head; //寻找链表的结尾点
while(pstart-》next != 0)
{
pstart-》data += 48; //!!《《《因为我们的输出是字符。所以再此加上48》》》》 逆顺输出
pstart = pstart-》next ;
}
int tip = 0; //转为字符串用
pstart = pstart-》ahead ; //找有效字
//cout《《“\n结果是 : “;
while(pstart != 0) //输出正序的结果；
{
result[tip++] = pstart-》data;
//cout《 data;
pstart = pstart-》ahead ;
}
result[tip] = ’\0’;
pstart =head; //释放空间
while(pstart-》next != 0)
{
pnew = pstart-》next ;delete pstart;
pstart =pnew;
}
return ;
}
//比较两个数字符串大小的函数
//返回值说明:0是alongblong ; 2是along=blong
int abigerb(char *numa, char *numb) //比较两个数最高位那一个大
{
int along=(int)strlen(numa); //标记数字a的长度；
int blong=(int)strlen(numb); //标记数字b的长度；
char *pna = numa; //指向数A的最高位，
char *pnb = numb; //指向数B的最高位，
if (along》blong) return 1;
if (along==blong)
{
while(*pna) //比较两个数那一个大
{
if(*pna》*pnb)return 1;
else if(*pna《*pnb)return 0 ;
else if(*pna==*pnb) //1111与1112
}
return 2; //这表明找到最后了还是全相等;
}
return 0 ;
}
/*————————————————————————–
*函数名称： 大数减法
*函数过程：1 比较两个数那一个长
* 2 以长的作为循环次数
* 3 如果两个数长度相等，从最高位开始比直到发现那一个数更大，使大项减去小项
* 4 对应项相减 进位存贮直到下高位相加用
* 5 每一位对应项相减时，处理三种可能的情况，a=b,ab;
* 6 a=b时，则计算,11-12,111-112,要考虑借位
* 7 直到循环结束
*入口参数：numa，numb，result字符串
*出口参数：无
*————————————————————————–*/
void subtract(char *numa, char *numb,char *result)//计算减
{ char *pna = findend(numa);//指向numa的一个指针。point numa pna 指向减数的最低位，
char *pnb = findend(numb);//指向numb的一个指针 //pnb 指向被减数的最低位，
int along=(int)strlen(numa);//标记数字a的长度；
int blong=(int)strlen(numb);//标记数字b的长度；
int times = 0; // 标记要计算多少次。
int carry=0; //存贮借位
int clear0=0; //消除结果最前面无用的’0’ 13-5 = 08 的效果！！
int isnegative=0; //用来加上被减数大于减数时补上最后一个负号
Node *head, // 用于存贮头指针
*pstart, // 用于存贮计算时的首指针
*pnew; //作于申请新结点
head = pstart =new Node;//初始化首结点和头结点。
pstart -》 data = 0;
pstart -》 next = NULL;
pstart -》 ahead = NULL;
if (abigerb(numa ,numb))
times = strlen(numa);//比较两个字符串长度，以大的作为循环次数
else //交换位置以降低难度
{
times = strlen(numb);//让数（字符串）长的减去数（字符串）短的
pna = findend(numb);//交换指针
pnb = findend(numa);
along=(int)strlen(numb);//标记数字a的长度；
blong=(int)strlen(numa);//标记数字b的长度；
isnegative=1;//标记最后要加上负号
}
while ((times– && (times》=0))|| carry != 0)//carry != 0 说没有借位时
{
if(!pstart-》next)//如果当前为空结点，则申请新结点
{
pnew = new Node;
pnew -》 data = 0;
pnew -》 next = NULL;
pnew -》 ahead = pstart;
pstart -》 next = pnew;
}
if(times《0)//如果计算完之后，借位等于1，，说明必然为负值;
{ pstart -》 data = -3 ;//让它等于负号 ’-’//-3来源于负号与0相差3。。
break; }
else
{
if ( *pna == *pnb )//减数等于被减数时。结果等于直截相减的结果；并置借位为0
{
if(carry==0)pstart -》 data = (*pna-48)-(*pnb-48); //111-11的情况
else
{
pstart-》data = (*pna-48)-(*pnb-48)+10 -carry;//1121-1112 carry=1;
}
}
if( *pna 》 *pnb )//减数大于被减数时。结果等于直截相减的结果；并置借位为0
{
pstart -》 data = (*pna-48)-(*pnb-48)-carry; //存贮个位
carry=0;
}
else if( *pna 《 *pnb )//说明被减数大于减数，让结果加10，相当于借位 (carry)为1
{ if(times》0)
pstart-》data = (*pna-48)-(*pnb-48)+10 -carry;//13-5的情况作为新值
else
pstart-》data = (*pnb-48)-(*pna-48) -carry; //3-5 作为当前的新值
carry=1;
}
}
pstart = pstart -》 next;
//结点移动
blong–;
if(blong》0)pnb–;//指针移向被减数高位
else *pnb=48;//之后相减就变为了0不作任何运算，其实可以优化的。但代码会长！而且还需要重新开结点。所以放弃； pna–;//被数指针移动，
}
if(isnegative==1)////加上负号处理。增加一长度并置为负号
{
pnew = new Node;
pnew -》 data = 0;
pnew -》 next = NULL;
pnew -》 ahead = pstart;
pstart -》 next = pnew;
pstart-》data=-3;//因为寻找链表的结尾点要统一加48。又因为‘-’是45。所以等于‘-3’
}
pstart =head;//寻找链表的结尾点
while(pstart-》next != 0)
{
pstart-》data += 48;//!!《《《因为我们的输出是字符。所以再此加上48》》》》 逆顺输出
pstart = pstart-》next ;
}
int tip = 0;//转为字符串用
clear0=0;// 消除结果最前面无用的’0’ 13-5 = 08 的效果 ..》》修改字符串的首指针
pstart = pstart-》ahead ;//找有效字
while(pstart != 0)//输出正序的结果；
{ if(clear0==0 && ((int)pstart-》data)==48&&pstart-》ahead!=0)// 消除结果最前面无用的’0’ ;
//不输出任何东西
else
result[tip++] = pstart-》data;
if(((int)pstart-》data)!=48&&((int)pstart-》data)!=45)clear0=1;//’－’号
pstart = pstart-》ahead ;
}
result[tip] = ’\0’;
pstart =head; //释放空间
while(pstart-》next != 0)
{
pnew = pstart-》next ;
delete pstart;
pstart =pnew;
}
return ;
}
/*————————————————————————–
*函数名称： 大数乘法
*函数过程：1 输入两个大数作为字符串
* 2 作一个双向链表
* 3 两个指针分别指向数字字符串的最低位
* 4 以第一个数的最低的一个位乘以第二个数的所有项存于链表中
* 5 链表首指针移
* 6 重复4，5依次从最低位乘到最高位
* 7 乘完后因为最低位是链表首，最后一位是链表尾。所以在逆顺输出链表。
* 4 直到循环结束
*入口参数：numa，numb，result字符串
*出口参数：无
*————————————————————————–*/
void multiply(char *numa, char *numb ,char *result)//用来储结果的)//计算乘积
{ char *pna = findend(numa);//指向numa的一个指针。point numa pna 指向乘数的最低位，
char *pnb = findend(numb);//指向numb的一个指针
//pnb 指向被乘数的最低位，
int along=(int)strlen(numa);//标记数字a的长度；
int blong=(int)strlen(numb);//标记数字b的长度；
int carry=0,temp_result;//存贮进位 和临时结果的
Node *head, // 用于存贮头指针
*pstart, // 用于存贮计算时的首指针
*pnew, //作于申请新结点
*pgo; //作为每计算完一行时，回到下一行起始节点用,移位标致来用
head = pstart =new Node;//初始化首结点和头结点。
pstart -》 data = 0;
pstart -》 next = NULL;
pstart -》 ahead = NULL;
while (along–)
{
pgo = pstart;//保存进位点
blong = (int)strlen(numb);//初始化长度
pnb = findend(numb); //初始化指针
while ((blong– && (blong》=0))|| carry != 0)
{ if(!pstart-》next)//如果当前为空结点，则申请新结点
{ pnew = new Node;
pnew -》 data = 0;
pnew -》 next = NULL;
pnew -》 ahead = pstart;
pstart -》 next = pnew;
}
if(blong《0)temp_result = carry ;//处理只有进位的情况
else temp_result =(pstart-》data+(*pna-48)*(*pnb-48)+carry);//自身值+新值+进位作为新值
pstart -》 data = temp_result%10; //存贮个位
carry = temp_result/10; //存贮进位
pstart = pstart -》 next; //结点移动
pnb–; //指针移向被乘数高位
}
pstart = pgo-》next; //前进一个位置；
pna–; //指针移向乘数高位
}
pstart =head;//寻找链表的结尾点
while(pstart-》next != 0) {
pstart-》data += 48;//!!《《《因为我们的输出是字符。所以再此加上48》》》》 逆顺输出
pstart = pstart-》next ; }
int tip = 0;//转为字符串用
pstart = pstart-》ahead ;//找有效字
while(pstart != 0)//输出正序的结果；
{ result[tip++] = pstart-》data;
pstart = pstart-》ahead ; }
result[tip] = ’\0’;
pstart =head; //释放空间
while(pstart-》next != 0) {
pnew = pstart-》next ;
delete pstart;
pstart =pnew;
}
return ;
}
/*————————————————————————–
*函数名称： 大数除法2–
*函数想法：1 用指针指向除数的最高位，保存临时字符串； tempstr[a++] = pna
* 2 如果临时字符串大于被除数，则相减。结果等于余数
* if(tempstr》numb)tempstr = tempstr – numb
* 3 如果小于被除数且指针到头，余数 等于 临时字符串
* if(tempstr *
*入口参数：numa，numb，result,remainder字符串
*出口参数：无
*————————————————————————–*/
void divide2( char *numa, char *numb,char *result,char *remainder)//计算除法2
{ char one=“1“;//临时字符串….
char one2=“1“;//
char zero=“0“;//
char numb2;//
char tempstr=““;//临时字符串 i
nt ia=0,ia2=0;//tempstr的指示器
bool moveon=false;//翻转牌
char *pna = numa;//指向numa的一个指针point numa pna //指向减数的最低位，
char *pnb = findend(numb);//指向numb的一个指针 //pnb 指向被减数的最低位，
Node *head, // 用于存贮头指针
*pstart, // 用于存贮计算时的首指针
*pnew; //作于申请新结点
head = pstart =new Node;//初始化首结点和头结点。
pstart -》 data = 0;
pstart -》 next = NULL;
pstart -》 ahead = NULL;
moveon = false; while(*pna)
{ if(!pstart-》next)//如果当前为空结点，则申请新结点
{ pnew = new Node;
pnew -》 data = 0;
pnew -》 next = NULL;
pnew -》 ahead = pstart;
pstart -》 next = pnew; }
ia=(int)strlen(tempstr);//取的长度
tempstr[ia++] = *(pna++);
tempstr[ia] =’\0’; //转换为字符串
if(tempstr==’0’)//处理高位也是0的那种 如00
{
ia2=0;
while(tempstr[ia2]==’0’)++ia2;
while(ia2》=1)//清除无用的0
{
ia=ia2-1;
tempstr[ia]=tempstr[ia2];
–ia2;
}
tempstr[++ia2]=’\0’;
}
while(abigerb(tempstr,numb)》0)//如果tempstr大于等于numb
{
if(tempstr==’0’)//处理高位也是0的那种 如00—-此乃冗余代码，留做记念用
{
ia2=0;
while(tempstr[ia2]==’0’)++ia2;
if(ia==ia2 )
}
strcpy(numb2,numb);
subtract(tempstr, numb,tempstr);//A-B strcpy(numb,numb2);
if(tempstr==’-’)//若判断的不准，变为了负数就再加上B。。
{
strcpy(numb2,numb);
addition(tempstr, numb,tempstr);//A-B
strcpy(numb,numb2);
ia2=0; //修正之后的长度。因为加法中未做负数运算
ia=0; //为了消除最后的那一个负号，整体向前移动。
while(tempstr[ia2]!=’\0’)++ia2;
while(ia2》=1)//清除无用的0 {
tempstr[ia]=tempstr[ia+1];
++ia;
–ia2; }
tempstr[ia]=’\0’;
moveon = true;
break; }
pstart-》data++ ; //结果自加
moveon = true; }
if(moveon) pstart = pstart -》 next; //结点移动
}
strcpy(remainder,tempstr);//存贮余数
int tip = 0;//转为字符串用
pstart =head;//寻找链表的结尾点
while(pstart-》next != 0) {
pstart-》data += 48;//!!《《《因为我们的输出是字符。所以再此加上48》》》》 逆顺输出
result[tip++] = pstart-》data;
pstart = pstart-》next ; }
result[tip] = ’\0’;//存贮结果
pstart =head; //释放空间
while(pstart-》next != 0) {
pnew = pstart-》next ;delete pstart; pstart =pnew; }
return ;
}
C语言中如何实现大数计算
/*关于任意精度大数的高精度求幂运算
在以前的文章中看到介绍一种算法，就是使用10000进制法，用数组来存储数据。
原理如下:
先说计数方法:
十进制和其他进制都是用权和数字(好象这里名词不对,记不清楚了)来计数的:
比如
num=123456790
这个数的大小就是:
0*10^0+9*10^1+7*10^2+…+1*10^8
我们可以这样来写这个数:
123 456 790
令a=123,b=456,c=790
那么,abc看起来就象和123456790是一样的
看到这里你明白了吧?
我们可以分段表示一个非常大的数而不必考虑它的溢出,
而只用考虑段数是否大于一个数即可
举个例子:
上边,a的最大值是999,bc也同样都是,我们只用保证这三个数不溢出
那么,num就不会溢出
再一个乘法.
我们老祖宗给我们留下的算盘,很妙,
它其实就是最基本的计算机之一
我们算乘方时,
只用乘以一个数:
这样来列式子:
123456790
*2=
————–
246913580
即:
123 456 790
*2= *2= *2=
—– —– ——
246 912 (1)580(溢出) 第三段有溢出,加到上一段
—– —– ——–
246 913 580
呵呵,就这样,打算盘一样,进位.
至此,我们已经将需要计算的溢出和乘方计算问题解决了,只用看代码了:
程序用一个含有1024个无符号整数(上限65536)的数组来存放各段数据
每一个数是一段,每一个数据可以表示9999这么大的数(便于进位)
计算一次,检查是否超过9999,如果超过,把这一段减去10000,
然后向上一个位(即上一个数)进1(这可以称为 “一万进制 “)
程序可以计算小于2的13605次方,大于0次方的任意的二的乘方
其实这样算起来一点也没有必要,不过,我觉得好玩,过瘾.
另外,借助对数,可以很轻松的算出这些来,
相比之下,本程序无任何误差而已
我称这个算法为 “ ’一万进制 ’算盘法 “:
*/
#include “stdio.h “
int main(void)
{
static unsigned int temp;/*分段储存数据*/
unsigned int position=1;/*记录共有几段*/
int overflow=0; /*记录在算每一段时是否溢出*/
long
times=10000,tm_cnt,sgn_cnt;/*默认10000次计算,可以更改,两个计数器(乘方次数,段的位置)*/
temp=2;/*初始值为2*/
if(times》 13000)
{
printf( “your input is too large “);/*检查输入是否越界*/
exit(0);
}
/*开始计算,外层为乘方次数,内层为每一位计算*/
for(tm_cnt=0;tm_cnt 《times-1;tm_cnt++)
{
for(sgn_cnt=0;sgn_cnt 《position;sgn_cnt++)
{
temp[sgn_cnt] 《 《=1;/*相当于乘2*/
if(overflow==1) /*检查上次是否有溢出*/
{
/*有的话,将溢出加到这一段,同时置溢出为0*/
++temp[sgn_cnt];
overflow=0;
}
if(temp[sgn_cnt]》 9999)
{
/*检查本次是否溢出,溢出的话,*/
temp[sgn_cnt]-=10000;
overflow=1;
}
}
if(overflow==1)
{
++position;
++temp[sgn_cnt];
overflow=0;
}
if(position》 1023)
{
printf( “times: %d error! “,tm_cnt);
exit(1);
}
}
printf( “%d “,temp[sgn_cnt-1]);
for(sgn_cnt=position-2;sgn_cnt》 =0;sgn_cnt–)
{
if(temp[sgn_cnt] 《1000)
printf( “0 “);
if(temp[sgn_cnt] 《100)
printf( “0 “);
if(temp[sgn_cnt] 《10)
printf( “0 “);
printf( “%d “,temp[sgn_cnt]);
if((sgn_cnt+1)%15==0)
printf( “\n “);
}
return 0;
}
2的1000次方：
199 5063 1168 8075
8384 8837 4216 2683 5850 8382 3496 8318 8619 2454 8520 0894 9852 9438 8302
2194 6631 9199 6168 4036 1945 9789 9331 1294 2320 9124 2715 5649 1349 4137
8111 7593 7859 3209 6323 9578 5573 0046 7937 9452 6765 2465 5126 6059 8955
2055 0086 9181 9331 1542 5086 0846 0618 1046 8550 9074 8660 8962 4888 0904
8989 4838 0092 5394 1633 2578 5062 1568 3094 7390 2556 9123 8806 5225 0966
4387 4441 0467 5987 1626 9854 5322 2868 5381 6169 4315 7756 2964 0762 8368
8076 0732 2285 3509 1641 4761 8395 6381 4589 6946 3899 4108 4096 0536 2678
2106 4621 4273 3339 4036 5255 6564 9530 6031 4268 0234 9694 0033 5934 3166
5145 9297 7732 7966 5775 6061 7258 2031 4079 9419 8179 6073 7824 5683 7622
8003 7302 8854 8725 1900 8344 6458 1454 6505 5792 9601 4148 3392 1615 7345
8813 9257 0953 7976 9119 2778 0082 6957 7356 7444 4123 0620 1875 7836 3255
0272 8323 7892 7071 0373 8028 6639 3031 4281 3324 1401 6241 9567 1690 5740
6141 9654 3423 2463 8801 2488 5614 7305 2074 3199 2259 6117 9625 0130 9928
6024 1708 3408 0760 5932 3201 6126 8492 2884 9625 5841 3128 4406 1536 7389
5148 7114 2563 1511 1089 7455 1420 3313 8202 0293 1640 9575 9646 4756 0104
0584 5841 5660 7204 4962 8670 1651 5061 9206 3100 4186 4222 7590 8670 9005
7460 6417 8569 5191 1456 0550 6825 1250 4060 0751 9842 2618 9805 9237 1180
5444 4788 0729 0639 5242 5483 3922 1982 7074 0447 3162 3767 6084 6613 0337
7870 6039 8034 1319 7133 4936 5462 2700 5631 6993 7455 5082 4178 0972 8109
8329 1314 4035 7187 7524 7685 0985 7276 9379 2643 3221 5993 9987 6886 6608
0836 8837 8380 2764 3282 7751 7227 3657 5727 4478 4112 2943 8973 3810 8616
0742 3253 2919 7481 3120 1976 0417 8281 9656 9747 5898 1645 3125 8434 1359
5986 2784 1301 2818 5406 2834 7664 9088 6905 2104 7580 8826 1582 3961 9857
7012 2407 0443 3058 3075 8690 3931 9604 6034 0497 3156 5832 0867 2105 9133
0090 3752 8234 1553 9745 3943 9771 5257 4552 9051 0212 3109 4732 1610 7534
7482 5740 7752 7398 6348 2984 9834 0756 9379 5564 6638 6218 7456 9499 2790
1657 2103 7013 6443 3135 8172 1431 1791 3982 2298 3845 8473 3444 0270 9641
8285 1005 0729 2774 8364 5505 7863 4501 1008 5298 7812 3894 7392 8699 5408
3434 6158 8070 4395 9118 9858 1514 5779 1771 4361 9698 7281 3145 9483 7832
0208 1474 9821 7185 8011 3890 7122 8250 9058 2681 7436 2205 7747 5921 4176
5371 5687 7256 1490 4582 9049 9246 1028 6300 8153 5583 3081 3010 1987 6758
5623 4343 5389 5540 9175 6234 0084 4887 5261 6264 3568 6488 3351 9463 7203
7729 3240 0944 5624 6923 2543 5040 0678 0272 7383 7755 3764 0672 6898 6362
4103 7491 4109 6671 8557 0507 5909 8100 2467 8988 0178 2719 2595 3381 2824
2195 4028 3027 5940 8448 9550 1467 6668 3896 9799 6886 2416 3631 3376 3939
0337 3455 8014 0763 6741 8777 1105 5384 2257 3949 9110 1864 6821 9696 5816
5148 5130 4942 2236 9947 7147 6306 9155 4682 1768 2876 2003 6277 7257 7237
8136 5331 6111 9681 1280 7926 6948 1887 2012 9864 3660 7685 5163 9860 5346
0229 7871 5575 1794 7385 2463 6944 6923 0878 9426 5948 2170 0805 1120 3223
6549 6288 1690 3573 9121 3683 3839 3591 7564 1873 3850 5109 7027 1613 9154
3959 0991 5981 5465 4417 3363 1165 6936 0311 2224 9937 9699 9922 6781 7323
5802 3111 8626 4457 5299 1357 5817 5008 1998 3923 6284 6152 4988 1088 9602
3224 4362 1737 7161 8086 3570 1546 8484 0586 2232 9792 8538 7562 3486 5564
4053 6962 6220 1896 3571 0288 1236 1567 5125 4333 8303 2700 2909 7668 6505
6855 7157 5055 1672 7518 8991 9412 9711 3376 9014 9916 1813 1517 1544 0077
2865 0573 1895 5745 0920 3301 8530 4847 1138 1831 5407 3240 5331 9038 4620
8403 6421 7637 0391 1550 6397 8900 0742 8536 7219 6280 9034 7797 4533 3204
6836 8795 8685 8023 7952 2186 2912 0080 7428 1955 1317 9481 5762 4448 2985
1846 1509 7048 8802 7274 7215 7468 8131 5947 5040 9732 1150 8049 8190 4558
0341 6826 9497 8714 1316 0632 1068 6391 5116 8177 4304 7925 9670 9376
怎样实现大数快速模运算
大多数的编译器只能支持到64位的整数运算，即我们在运算中
所使用的整数必须小于等于64位，即：0xffffffffffffffff
也就是18446744073709551615，这远远达不到RSA的需要，于是
需要专门建立大数运算库来解决这一问题。
最简单的办法是将大数当作字符串进行处理，也就是将大数用
10进制字符数组进行表示，然后模拟人们手工进行“竖式计算”
的过程编写其加减乘除函数。但是这样做效率很低，因为1024
位的大数其10进制数字个数就有数百个，对于任何一种运算，
都需要在两个有数百个元素的数组空间上做多重循环，还需要
许多额外的空间存放计算的进位退位标志及中间结果。当然其
优点是算法符合人们的日常习惯，易于理解。
另一种思路是将大数当作一个二进制流进行处理，使用各种移
位和逻辑操作来进行加减乘除运算，但是这样做代码设计非常
复杂，可读性很低，难以理解也难以调试。
C语言 实现大数的计算
/*关于任意精度大数的高精度求幂运算 在以前的文章中看到介绍一种算法，就是使用10000进制法，用数组来存储数据。 原理如下: 先说计数方法: 十进制和其他进制都是用权和数字(好象这里名词不对,记不清楚了)来计数的: 比如 num=123456790 这个数的大小就是: 0*10^0+9*10^1+7*10^2+…+1*10^8 我们可以这样来写这个数: 123 456 790 令a=123,b=456,c=790 那么,abc看起来就象和123456790是一样的 看到这里你明白了吧? 我们可以分段表示一个非常大的数而不必考虑它的溢出, 而只用考虑段数是否大于一个数即可 举个例子: 上边,a的最大值是999,bc也同样都是,我们只用保证这三个数不溢出 那么,num就不会溢出 再一个乘法. 我们老祖宗给我们留下的算盘,很妙, 它其实就是最基本的计算机之一 我们算乘方时, 只用乘以一个数: 这样来列式子: 123456790 *2= ————– 246913580 即: 123 456 790 *2= *2= *2= —– —– —— 246 912 (1)580(溢出) 第三段有溢出,加到上一段 —– —– ——– 246 913 580 呵呵,就这样,打算盘一样,进位. 至此,我们已经将需要计算的溢出和乘方计算问题解决了,只用看代码了: 程序用一个含有1024个无符号整数(上限65536)的数组来存放各段数据 每一个数是一段,每一个数据可以表示9999这么大的数(便于进位) 计算一次,检查是否超过9999,如果超过,把这一段减去10000, 然后向上一个位(即上一个数)进1(这可以称为 “一万进制 “) 程序可以计算小于2的13605次方,大于0次方的任意的二的乘方 其实这样算起来一点也没有必要,不过,我觉得好玩,过瘾. 另外,借助对数,可以很轻松的算出这些来, 相比之下,本程序无任何误差而已 我称这个算法为 “ ’一万进制 ’算盘法 “: */ #include “stdio.h “ int main(void) { static unsigned int temp;/*分段储存数据*/ unsigned int position=1;/*记录共有几段*/ int overflow=0; /*记录在算每一段时是否溢出*/ long times=10000,tm_cnt,sgn_cnt;/*默认10000次计算,可以更改,两个计数器(乘方次数,段的位置)*/ temp=2;/*初始值为2*/ if(times》 13000) { printf( “your input is too large “);/*检查输入是否越界*/ exit(0); } /*开始计算,外层为乘方次数,内层为每一位计算*/ for(tm_cnt=0;tm_cnt 《times-1;tm_cnt++) { for(sgn_cnt=0;sgn_cnt 《position;sgn_cnt++) { temp[sgn_cnt] 《 《=1;/*相当于乘2*/ if(overflow==1) /*检查上次是否有溢出*/ { /*有的话,将溢出加到这一段,同时置溢出为0*/ ++temp[sgn_cnt]; overflow=0; } if(temp[sgn_cnt]》 9999) { /*检查本次是否溢出,溢出的话,*/ temp[sgn_cnt]-=10000; overflow=1; } } if(overflow==1) { ++position; ++temp[sgn_cnt]; overflow=0; } if(position》 1023) { printf( “times: %d error! “,tm_cnt); exit(1); } } printf( “%d “,temp[sgn_cnt-1]); for(sgn_cnt=position-2;sgn_cnt》 =0;sgn_cnt–) { if(temp[sgn_cnt] 《1000) printf( “0 “); if(temp[sgn_cnt] 《100) printf( “0 “); if(temp[sgn_cnt] 《10) printf( “0 “); printf( “%d “,temp[sgn_cnt]); if((sgn_cnt+1)%15==0) printf( “\n “); } return 0; } 2的1000次方： 199 5063 1168 8075 8384 8837 4216 2683 5850 8382 3496 8318 8619 2454 8520 0894 9852 9438 8302 2194 6631 9199 6168 4036 1945 9789 9331 1294 2320 9124 2715 5649 1349 4137 8111 7593 7859 3209 6323 9578 5573 0046 7937 9452 6765 2465 5126 6059 8955 2055 0086 9181 9331 1542 5086 0846 0618 1046 8550 9074 8660 8962 4888 0904 8989 4838 0092 5394 1633 2578 5062 1568 3094 7390 2556 9123 8806 5225 0966 4387 4441 0467 5987 1626 9854 5322 2868 5381 6169 4315 7756 2964 0762 8368 8076 0732 2285 3509 1641 4761 8395 6381 4589 6946 3899 4108 4096 0536 2678 2106 4621 4273 3339 4036 5255 6564 9530 6031 4268 0234 9694 0033 5934 3166 5145 9297 7732 7966 5775 6061 7258 2031 4079 9419 8179 6073 7824 5683 7622 8003 7302 8854 8725 1900 8344 6458 1454 6505 5792 9601 4148 3392 1615 7345 8813 9257 0953 7976 9119 2778 0082 6957 7356 7444 4123 0620 1875 7836 3255 0272 8323 7892 7071 0373 8028 6639 3031 4281 3324 1401 6241 9567 1690 5740 6141 9654 3423 2463 8801 2488 5614 7305 2074 3199 2259 6117 9625 0130 9928 6024 1708 3408 0760 5932 3201 6126 8492 2884 9625 5841 3128 4406 1536 7389 5148 7114 2563 1511 1089 7455 1420 3313 8202 0293 1640 9575 9646 4756 0104 0584 5841 5660 7204 4962 8670 1651 5061 9206 3100 4186 4222 7590 8670 9005 7460 6417 8569 5191 1456 0550 6825 1250 4060 0751 9842 2618 9805 9237 1180 5444 4788 0729 0639 5242 5483 3922 1982 7074 0447 3162 3767 6084 6613 0337 7870 6039 8034 1319 7133 4936 5462 2700 5631 6993 7455 5082 4178 0972 8109 8329 1314 4035 7187 7524 7685 0985 7276 9379 2643 3221 5993 9987 6886 6608 0836 8837 8380 2764 3282 7751 7227 3657 5727 4478 4112 2943 8973 3810 8616 0742 3253 2919 7481 3120 1976 0417 8281 9656 9747 5898 1645 3125 8434 1359 5986 2784 1301 2818 5406 2834 7664 9088 6905 2104 7580 8826 1582 3961 9857 7012 2407 0443 3058 3075 8690 3931 9604 6034 0497 3156 5832 0867 2105 9133 0090 3752 8234 1553 9745 3943 9771 5257 4552 9051 0212 3109 4732 1610 7534 7482 5740 7752 7398 6348 2984 9834 0756 9379 5564 6638 6218 7456 9499 2790 1657 2103 7013 6443 3135 8172 1431 1791 3982 2298 3845 8473 3444 0270 9641 8285 1005 0729 2774 8364 5505 7863 4501 1008 5298 7812 3894 7392 8699 5408 3434 6158 8070 4395 9118 9858 1514 5779 1771 4361 9698 7281 3145 9483 7832 0208 1474 9821 7185 8011 3890 7122 8250 9058 2681 7436 2205 7747 5921 4176 5371 5687 7256 1490 4582 9049 9246 1028 6300 8153 5583 3081 3010 1987 6758 5623 4343 5389 5540 9175 6234 0084 4887 5261 6264 3568 6488 3351 9463 7203 7729 3240 0944 5624 6923 2543 5040 0678 0272 7383 7755 3764 0672 6898 6362 4103 7491 4109 6671 8557 0507 5909 8100 2467 8988 0178 2719 2595 3381 2824 2195 4028 3027 5940 8448 9550 1467 6668 3896 9799 6886 2416 3631 3376 3939 0337 3455 8014 0763 6741 8777 1105 5384 2257 3949 9110 1864 6821 9696 5816 5148 5130 4942 2236 9947 7147 6306 9155 4682 1768 2876 2003 6277 7257 7237 8136 5331 6111 9681 1280 7926 6948 1887 2012 9864 3660 7685 5163 9860 5346 0229 7871 5575 1794 7385 2463 6944 6923 0878 9426 5948 2170 0805 1120 3223 6549 6288 1690 3573 9121 3683 3839 3591 7564 1873 3850 5109 7027 1613 9154 3959 0991 5981 5465 4417 3363 1165 6936 0311 2224 9937 9699 9922 6781 7323 5802 3111 8626 4457 5299 1357 5817 5008 1998 3923 6284 6152 4988 1088 9602 3224 4362 1737 7161 8086 3570 1546 8484 0586 2232 9792 8538 7562 3486 5564 4053 6962 6220 1896 3571 0288 1236 1567 5125 4333 8303 2700 2909 7668 6505 6855 7157 5055 1672 7518 8991 9412 9711 3376 9014 9916 1813 1517 1544 0077 2865 0573 1895 5745 0920 3301 8530 4847 1138 1831 5407 3240 5331 9038 4620 8403 6421 7637 0391 1550 6397 8900 0742 8536 7219 6280 9034 7797 4533 3204 6836 8795 8685 8023 7952 2186 2912 0080 7428 1955 1317 9481 5762 4448 2985 1846 1509 7048 8802 7274 7215 7468 8131 5947 5040 9732 1150 8049 8190 4558 0341 6826 9497 8714 1316 0632 1068 6391 5116 8177 4304 7925 9670 9376
两个大数的加减如何运算（请详细解答）
这里有介绍用数组进行大数运算
public class BigNumber {
public static int add(int a, int b) {
int carry = 0;
int c = new int[a.length];
for(int i = a.length – 1; i 》= 0; i–) {
c[i] = a[i] + b[i] + carry;
if(c[i] 《 10000)
carry = 0;
else { // 进位
c[i] = c[i] – 10000;
carry = 1;
}
}
return c;
}
public static int sub(int a, int b) {
int borrow = 0;
int c = new int[a.length];
for(int i = a.length – 1; i 》= 0; i–) {
c[i] = a[i] – b[i] – borrow;
if(c[i] 》= 0)
borrow = 0;
else { // 借位
c[i] = c[i] + 10000;
borrow = 1;
}
}
return c;
}
public static int mul(int a, int b) { // b 为乘数
int carry = 0;
int c = new int[a.length];
for(int i = a.length – 1; i 》=0; i–) {
int tmp = a[i] * b + carry;
c[i] = tmp % 10000;
carry = tmp / 10000;
}
return c;
}
public static int div(int a, int b) { // b 为除数
int remain = 0;
int c = new int[a.length];
for(int i = 0; i 《 a.length; i++) {
int tmp = a[i] + remain;
c[i] = tmp / b;
remain = (tmp % b) * 10000;
}
return c;
}
public static void main(String args) {
int a = {1234, 5678, 9910, 1923, 1124};
int b = {1234, 5678, 9910, 1923, 1124};
int c = BigNumber.add(a, b);
for(int i = 0; i 《 c.length; i++) {
System.out.print(c[i]);
}
System.out.println();
}
}
对于计算机来说，做大数（比如2^1024）运算和小数(比如2^(-1024)）运算哪个更难
如果不要求精度，那就是大数、小数一样简单，反正都是浮点数1e+xxx和1e-xxxx一样的计算消耗；如果考虑精度，大数和小数要保留完整的所有位数，那么大数、小数运算是一样的难，都是一个庞大的数组（例如int x）里面进行整数运行运算。
古代大数是怎么计算的
古代人用算筹计算。用算筹表示一个数，采用十进位制，并且纵式横式交替使用。个位数用纵式表示，十位数用横是表示，百位数再用纵式表示“……”空格表示零。