一、前言
高精度运算,是指参与运算的数(加数,减数,因子……）范围大大超出了标准数据类型（整型，实型）能表示的范围的运算。例如，求两个200位的数的和。这时，就要用到高精度算法了 高精度使用数组来存储整数，模拟手算进行四则运算
由于计算机运算是有模运算,数据范围的表示有一定限制,如整型int(C++中int 与long相同)表达范围是(-2^31~2^31-1),unsigned long(无符号整数)是(0~2^32-1),都约为几十亿.如果采用实数型,则能保存最大的double只能提供15~16位的有效数字,即只能精确表达数百万亿的数.因此,在计算位数超过十几位的数时,不能采用现有类型,只能自己编程计算.
二、高精度计算通用方法:
高精度计算时一般用一个数组来存储一个数,数组的一个元素对应于数的一位 (当然,在以后的学习中为了加快计算速度,也可用数组的一个元素表示数的多位数字,暂时不讲),表示时,由于数计算时可能要进位,因此为了方便,将数由低位到高位依次存在数组下标对应由低到高位置上,另外,我们申请数组大小时,一般考虑了最大的情况,在很多情况下,表示有富余,即高位有很多0,可能造成无效的运算和判断,因此,我们一般将数组的第0个下标对应位置来存储该数的位数（每次计算过后要由于进位借位会位数有影响要记得更改）.
如数:3485(三千四百八十五)，表达在数组a[10]上情况是:
下标：0 1 2 3 4 5 6 7 8 9
内容：4 5 8 4 3 0 0 0 0 0
说明：位数 个位 十位 百位 千位
具体在计算加减乘除时方法就是小学时采用的列竖式方法． 注：高精度计算时一般用正数，对于负数，通过处理符号位的修正。
三．高精度数的存储
１．如对数采用的字符串输入
#include <iostream>
#include <cstring>
using namespace std;
const int N=100;//最多100位
int main()
{
int a[N+1],i;
string s1;
cin>>s1;//数s1
memset(a,0,sizeof(a)); //数组清0
a[0]=s1.length(); //位数
for(i=1;i<=a[0];i++) a[i]=s1[a[0]-i]-'0';//将字符转为数字并倒序存储．（s的末尾记录在a的小下标处）
return 0;
}
2.直接读入
#include <iostream>
using namespace std;
const int N=100;//最多100位
int main()
{
int a[N+1],i,s,key;
cin>>key;//数key
memset(a,0,sizeof(a)); //数组清0
i=0;//第0位
while(key) //当key大于0
{
a[++i]=key%10;//取第i位的数
key=key/10;
}
a[0]=i; //共i位数
return 0;
}
3.直接初始化(用a[]存储)
初始化为0: memset(a,0,sizeof(a));
初始化为1: memset(a,0,sizeof(a));a[0]=1;a[1]=1;
以下程序都只写函数，不写完整程序，所有高精度数存储都满足上述约定。
四.高精度数比较
int compare(int a[],int b[]) //比较a和b的大小关系，若a>b则为1，a<b则为-1,a=b则为0
{int i;
if (a[0]>b[0]) return 1;//a的位数大于b则a比b大
if (a[0]<b[0]) return -1;//a的位数小于b则a比b小
for(i=a[0];i>0;i--) //从高位到低位比较（位数相同时候）
{if (a[i]>b[i]) return 1;
if (a[i]<b[i]) return -1;}
return 0;//各位都相等则两数相等。
}
五、高精度加法
int plus(int a[],int b[]) //计算a=a+b
{int i,k;
k=a[0]>b[0]?a[0]:b[0]; //k是a和b中位数最大的一个的位数
for(i=1;i<=k;i++)
{a[i+1]+=(a[i]+b[i])/10; //若有进位，则先进位
a[i]=(a[i]+b[i])%10;} //计算当前位数字,注意：这条语句与上一条不能交换。
if(a[k+1]>0)
a[0]=k+1; //修正新的a的位数（a+b最多只能的一个进位）
else a[0]=k;
return 0;
}
ps：由于开数组的时候，考虑到结果的最大可能，所以前面几位都是0，进位的时候直接累加上进位数据即可
六、高精度减法
要先比较两个数的大小，大数-小数。通过返回值决定结果的正负
int gminus(int a[],int b[]);//计算a=a-b，返加符号位0:正数 、-1:负数
{ int flag,i
flag=compare(a,b); //调用比较函数判断大小
if (falg==0)//相等
{memset(a,0,sizeof(a));return 0;} //若a=b，则a=0,也可在return前加一句a[0]=1,表示是 1位数0
if(flag==1){ //大于
for(i=1;i<=a[0];i++){
if(a[i]<b[i]){ a[i+1]--;a[i]+=10;} //若不够减则向上借一位
a[i]=a[i]-b[i];
}
while(a[a[0]]==0) a[0]--; //修正a的位数
return 0;}
if (flag==-1){//小于 则用a=b-a,返回-1。大数b-小数a，返回负号
for(i=1;i<=b[0];i++){
if(b[i]<a[i]){ b[i+1]--;b[i]+=10;} //若不够减则向上借一位
a[i]=b[i]-a[i];
}
a[0]=b[0];
while(a[a[0]]==0) a[0]--; //修正a的位数
return -1;}
}
七、高精度乘法1(高精度乘单精度数，单精度数是指通常的整型数)
int multi1(int a[],long key) //a=a*key,key是单精度数
{int i,k;
if (key==0){memset(a,0,sizeof(a));a[0]=1;return 0;} //单独处理key=0
for(i=1;i<=a[0];i++)a[i]=a[i]*key;//先每位乘起来
for(i=1;i<=a[0];i++){a[i+1]+=a[i]/10;a[i]%=10;} //进位
//注意上一语句退出时i=a[0]+1
while(a[i]>0) {a[i+1]=a[i]/10;a[i]=a[i]%10;i++;a[0]++];} //继续处理超过原a[0]位数的进位,修正a的位数
return 0;
} # 八、高精度乘法2（高精度乘以高精度、要求用尽可能少的存储单元） 算法：用数组保存两个高精度数，然后逐位相乘，注意考虑进位和总位数。
源程序如下：
#include <stdio.h>
main()
{
int a[240] = {0}, b[240] = {0}, c[480] = {0};
int i, j, ka, kb, k;
char a1[240], b1[240];
gets(a1);
ka = strlen(a1);
gets(b1);
kb = strlen(b1);
k = ka + kb;
for(i = 0; i < ka; i++) a[i] = a1[ka-i-1] - '0';
for(i = 0; i < kb; i++) b[i] = b1[kb-i-1] - '0';
for(i = 0; i < ka; i++)
for(j = 0; j < kb; j++)
{
c[i + j] = c[i + j] + a[i] * b[j];
c[i + j +1] = c[i + j +1] + c[i + j]/10;
c[i + j] = c[i + j] % 10;
}
if(!c[k]) k--;
for(i = k-1; i >= 0; i--) printf("%d", c[i]);
}
ps:2的幂可以转化成左移运算 i«m——-即：i=i*2^m
其余关于高精度之间的除法，乘法，和阶层运算，可以根据上面的方法写出。 参考详见：高精度算法
九、拓展：斯特林公式
斯特林公式是用于n极大的时候，近似模拟n！的值的数学公式。 它有个很大的优点就是，n越大，模拟的越好。尤其当n很大的时候，计算量大，复杂的时候，就显示出优点。
Stirling公式的意义在于：当n足够大时，n!计算起来十分困难，虽然有很多关于n!的等式，但并不能很好地对阶乘结果进行估计，尤其是n很大之后，误差将会非常大。但利用Stirling公式可以将阶乘转化成幂函数，使得阶乘的结果得以更好的估计。而且n越大，估计得越准确。
公式：
上述公式满足：
要计算n！的位数，可以利用配套的位数公式N！的位数=lgN！+1;
当n!=1的时候，所有位数都可以符合以下下面的公式：
