高精度算法大全
- 格式：pdf
- 大小：138.93 KB
- 文档页数：3
⾼精度算法⼤全
什么是⾼精度数？
在⼀般的科学计算中,会经常算到⼩数点后⼏百位或者更多,当然也可能是⼏千亿⼏百亿的⼤数字。⼀般这类数字我们统称为⾼精度数,⾼精度算法是⽤计算机对于超⼤数据的⼀种模拟加,减,乘,除,乘⽅,阶乘,开放等运算。
对于⼀个很⼤的数字N >= 10^ 100, 很显然这样的数字⽆法在计算机中正常存储。于是, 我们想到了办法,将这个数字拆开,拆成⼀位⼀位的 或者是四位四位的存储到⼀个数组中, ⽤⼀个数组去表⽰⼀个数字。这样这个数字就被称谓是⾼精度数。
对于⾼精度数,也要像平常数⼀样做加减乘除以及乘⽅的运算,于是就有了⾼精度算法:
由于计算机输⼊计算结果的精度通常受到计算机的限制，如：在双精度⽅式下，计算机最多只能输出16位有效数字，如果超过16位，则只能按浮点形式输出，另外，⼀般计算机实数表⽰的范围为1038，如果超过这个范围，计算机就⽆法表⽰了。但是我们可以通过⼀
⼀、基本⽅法：
（⼀）、数据的接收与存储
要在计算机上进⾏⾼精度计算，⾸先就应该有精确的输⼊，即计算机要精确地接收和存储数据。
基本思路：
1、以字符串的⽅式读⼊数字并保存在ac字符数中。
2、⽤strlen函数计算字符数组ac中总字符数（⾼精度数的位数）并保存在整型数组的a[0]中。
3、将字符串中的字符逐个字符转化成数字并保存在整型数组a中。这⼀部分的代码编写⾮常重要，运算都会从低位开始 (先算个位，再算⼗位，再……)在存储时需要倒序存储，也就是个位数存在a[1],⼗位数存在a[2]最⾼位存在a[a[0]]。
例如数字4678在数组中存储结构为：
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
4 8 7 6 4
下⾯的程序dh⼦函数完成了以字符⽅式读⼊两个字符串并将其转化成数字存储在数组a[]和b[]中。
#include
#include
using namespace std;
int a[1010],b[1010]; //⽤于存储拆解后的数字
void dh()
{
int an,bn,i;
char ac[1010],bc[1010];
cin>>ac>>bc;
a[0]=strlen(ac); //a⾼精度数的位数存在a[0]中
for(i=1;i<=a[0];i++)a[i]=ac[a[0]-i]-'0'; //倒序存储数字（+、-\*）
b[0]=strlen(bc); //b⾼精度数的位数存在b[0]中
for(i=1;i<=b[0];i++)b[i]=bc[b[0]-i]-'0';//倒序存储数字（+、-\*）
return;
}
int main()
{
dh();
return 0;
}
（⼆）、运算结果的输出
a[0] a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9]
4 0 0 0 1 0 0 0 0 0
b[0] b[1] b[2] b[3] b[4] b[5] b[6] b[7] b[8] b[9]
3 9 9 9 0 0 0 0 0 0
结果 1 0 0 0 0 0 0 0 0
这⾥只考虑⾼精加、⾼精减、⾼精乘这类倒序存放的数据的计算结果的输出，这三类数据由于是倒序存放，⽽且运算结果的位数很难确定，如1000-999=1，如下表所⽰
所以此类运算结果的输出⼀般都需要⼀个去除前导0的过程,也就是说忽略掉数组中后⾯所有的⽆效0，定位到数组中最右⼀个⾮0数字，再从最右侧的⾮0位开始依次输出数字。
具体代码:
i=1000(偷懒点的可以直接设数据位数上限)
while(a[i]==0)i--; //去除前导0
while(i>0)cout<
（三）、⾼精度数的加法运算（两个⾮负整数）
基本思路：
1、先以前⾯介绍的⽅式以读字符串的⽅式读取两个加数并转化存储到整型数组a和b中。
2、⽤⼀个变量c存储运算结果的最⼤位数（两个加数中的⼤数字的位数+1，+1是考虑到最后结果最⾼位位有可能有进位的问题，如50+990=1040）
3、⽤⼀个变量k来存储有可能的进位情况，初始化为0。
4、从最低位到最⾼位依次相加，将相加结果的个位保存在当前位，进位情况记录到k（0⽆进位，1 进位1），以便在进⾏下⼀次运算的时候把进位加进去。
具体代码如下：
void gjjia()
{
int i,c,k=0,t;
c=a[0]>b[0]?a[0]+1:b[0]+1;
for(i=1;i<=c;i++)
{
t=a[i]+b[i]+k;
a[i]=t%10;
k=t/10;
}
return;
}
（四）、⾼精度减法运算（两个数都是⾮负整数且被减数⼀定⽐减数⼤）
基本思路：
1、先以前⾯介绍的⽅式以读字符串的⽅式读取两个加数并转化存储到整型数组a和b中。
2、⽤⼀个变量c存储运算结果的最⼤位数（因为默认被减数⽐减数⼤，所的最⼤位数就是被减数的位数，减法运算结果的最⾼位不可能产⽣进位，不需要+1）
3、⽤⼀个变量k来存储有可能的借位情况，初始化为0。
4、从最低位到最⾼位依次相加，将相加结果的个位保存在当前位，进位情况记录到k（当前位的被减数⽐减数⼩需要向⾼位借位k=-1;否则k=0），以便在进⾏下⼀次运算的时候把借位减掉。
具体代码如下：
void gjjian()
{
int i,c,k=0,t;
c=a[0];
for(i=1;i<=c;i++)
{
if(a[i]+k>=b[i]){a[i]=a[i]+k-b[i];k=0;}
else{a[i]=a[i]+10+k-b[i];k=-1;}
}
}
（五）、⾼精度减法运算（两个数都是⾮负整数但不确定两者⼤⼩）
基本思路：由于不确定被减数和减数哪个更⼤，需要定义⼀个函数bijiao()来判断两个⾼精度数⼤⼩，⽤⼀个全局布尔型变量fu存储⼤⼩情况。被减数⼩，fu=1，否则fu=0。后⾯的⾼精减函数则根据fu的值来确定减法策略，fu=0时b-a否则是a-b,输出函数则根据fu情况来
判断两数⼤⼩函数：
bool bijiao()
{
int ai,bi;
ai=a[0];
while(a[ai]==0)a[ai--];//为了让⼤⼩⽐较更准确，都去掉前导0
bi=b[0];
while(b[bi]==0)b[bi--];//为了让⼤⼩⽐较更准确，都去掉前导0
if(ai
else if (ai>bi)retrun 1; //如果被减数的位数⽐减数⼤，返回1
else //两者位数相等则从⾼位开始逐位判断。
{
for(int j=ai;j>0;j--)
if(a[j]
else if(a[j])>b[j])return 1;
return 1; //两个数完全相等
}
}
两数相减函数
void gjjian()
{
int i,c,k=0,t;
if(fu==1)
{
c=a[0];
for(i=1;i<=c;i++)
{
if(a[i]+k>=b[i]){a[i]=a[i]+k-b[i];k=0;}
else {a[i]=a[i]+10+k-b[i];k=-1;}
}
}
else
{
c=b[0];
for(i=1;i<=c;i++)
{
if(b[i]+k>=a[i]){a[i]=b[i]+k-a[i];k=0;}
else{a[i]=b[i]+10+k-a[i]; k=-1;}
}
}
}
输出函数void shuchu()
{
int i=1000;
if(fu==0)cout<<"-";
while(a[i]==0)i--;
while(i>0)cout<
cout<
return;
}
（六）、考虑有正负号的⾼精度加、减法运算。
只需要在接收数据时判断接收的数字是否是负数，再在运算中设计相应的运算策略即可，例如：a(+)+b(-)转化成a-b等，不再详细说明。
（七）、⾼精乘法运算。
完成⾼精乘法运算的话只需列⼀个竖式的乘法运算就能轻松完成程序设计。找到其中的关键规律：个位和个位相乘，结果保存在个位，个位和⼗位相乘，结果保存在⼗位，⼗位和⼗位相乘结果保存在百位，依次类推可以得出递推公式，第i位的数和第j位数相除，结果保
所以程序只需再定⼀个数组c来保存a和b各位相乘的结果，最后统⼀完成各位的进位就可以了，相乘部分函数代码如下
void gjchen()
{
int i,j;
for(i=1;i<=a[0];i++)
for(j=1;j<=b[0];j++)
{
c[j+i-1] = c[j+i-1] + a[i]*b[j];
c[i+j]=c[i+j]+c[i+j-1]/10;
c[i+j-1]=c[i+j-1]%10;
}
}
（⼋）、⾼精度除法。
除法运算和前⾯所讲的⾼精加，⾼精减以及⾼精除不⼀样，⾼精除是从⾼位开始除（不理解的话，请⿇烦列⼀个竖式除法运算）。所有⾼精除的数据存储要正序存放，最⾼位在最左边（切记！切记！）。
同样，想要理解⾼精除法运算的原理，请默默的列⼀个竖式除法运算。
先看看⾼精度数除以低精度数。
设参与运算的两个数分别为a和b，以字符串的⽅式读⼊数a，并将a中的每⼀位数字分别存储在a数组中。由于b是低精度数，可以⽤⼀般的整数变量来接收和存储。
运算过程：由于除数是低精，所以我们完全可以定义⼀个整型变量t来完成除法运算，同时定义⼀个整型数组来存储商。第⼀轮算是将被除数的最⾼位a[1]赋值给t，将t/b的商存储在c[1](c[1]=t/b),并将余数存储在t（t=t%b）。第2轮运算就是将上轮运算的余数乘10再加上
例 123456 除以5
被除数 1 2 3 4 5 6
第⼀步 1 1除5，商0余1；
第⼆步 余1 12 前⾯的余1*10+2=12，12除5商2余2
余2 23 前⾯的余2*10+3=23，23除5商4余3
余3 34 前⾯的余3*10+4=34，34除5商6余4
余4 45 前⾯的余4*10+5=45，45除5商9余0
余0 6 前⾯的余0*10+6=6，6除5商1余1
商 0 2 4 6 9 1 最后余1
输出商时要注意两点：1、去除⽆效的前导0；2、按位输出到c数组的最低位（a[0]商的最低位位数和被除数的最低位的位数相同）位为⽌。
代码如下：
#include
#include
using namespace std;
int a[1010]; //被除数
int b ; //除数
int c[1010]; //商
int d; //余数
void gjchudj()
{
c[0]=a[0];
int i, t=0;
for(i=1;i<=a[0];i++){t=t*10+a[i];c[i]=t/b;t=t%b;}
d=t;
}
void shuchu()
{
int i=1;
while(c[i]==0)i++;
while(i<=c[0])cout<
cout<
return;
}
void dh()
{
int an,bn,i,t,d;
char ac[1010];
cin>>ac>>b;
d=strlen(ac);//a⾼精度数的位数存在a[0]中,要注意，如果输⼊的
t=0; //数字有前导0的话，需要先清除前导0，代码如下：
while(ac[t]=='0')t++;
a[0]=d-t;
for(i=t;i<=d;i++)a[i-t+1]=ac[i]-'0';
}
int main()
{
dh();
gjchudj();
shuchu();
return 0;
}
⾼精度数除以⾼精度数。
采⽤字符串读⼊的⽅式接收和存储数据，设参与运算的两个数分别为A和B，并将相应的字符串转化为数值，将A、B中的每⼀位数字分别存储在a和b数组中。
运算思路：⽤减法代替除法运算。
下⾯以12345678（存在数组a中）除以11111组b中）为例模拟整个运算过程（⽤c数组存商）。
