高精度运算C++

1、万进制高精度运算（C+语言）目前在青少年信息学奥林匹克竞赛中所涉及到的高精度计算包括加（addition）、减（subtract）、乘（multiply）、除（divide）四种基本运算。其中乘法分高精度数乘高精度数和单精度数乘高精度数两种， 除法一般指两个单精度数相除，求解最终指定精度的解，找出循环节或输出指定精度位数的小数。（注：高精度数与单精度数均指整数）主要的解题思想是利用在小学就曾学习过的坚式加减乘除法则，用程序语言实现存在的问题主要有 如何存储高精度数的值，如何实现计算等问题。一. 高精度数字的存储我们日常书写一个高精度数字，左侧为其高位，右侧为其低位，在计算中往往会因进位（car

2、ry ）或借位（borrow ）导致高位增长或减少，因此我们定义一个整型数组（ int bignummaxlen）从低位向高 位实现高精度整数的存储，数组的每个元素存储高精度数中的一位。（如下表所示）高精度数3 （高位）,794 （低位）int bignumin,210显然，在C+语言中，int类型（4个字节/32位计算机）元素存储十进制的一位数字非常浪费空 间，并且运算量也非常大，因此常将程序代码优化为万进制，即数组的每个元素存储高精数字的四位。在后面的叙述过程中均以万进制为例介绍。（为什么选择万进制，而不选择更大的进制呢？十万进制中 的最大值99999相乘时得到的值是 9999800001

3、超过4个字节的存储范围而溢出，从而导致程序计算错在实际编写程序代码过程中常作如下定义：const int base=10000;const int maxlen=1000+1;int bignummaxlen;说明：base表示进制为万进制， maxlen表示高精度数的长度，1个元素能存储4个十进制位，1000个元 素就存储4000个十进制位，而加1表示下标为。的元素另有它用，常用作存储当前高精度数字的位数。二. 各种运算的程序实现（一）加法：首先回顾一下小学中曾学习的坚式加法，见图一：bignum19475461243bignum29181324341carry1000bignum_ans1

4、39313701584图一加法的计算过程从上面的图中我们可以得知，做加法运算是从低位向高位进行，如果有进位，下一位进行相加时要 加上进位，如果最高位已计算完还有进位，就要增加存储结果的位数，保存起进位来。关于进位的处 理，往往定义单独变量 carry进行存储，程序实现的过程如图二所示：高精度加法程序代码( bignum1+bignum2 bignum_ans ):void addition(int *bignum1, int *bignum2, int *bignum_ans)(int carry=0;memset( bignum_ans, 0, sizeof(bignum_ans);*big

5、num_ans=*bignum1>*bignu2?*bignum1:*bignum2;for(int pos=1; pos<=*bignum_ans; pos+)(carry+=bignum1pos+bignum2pos;bignum_anspos=carry%base;carry/=base;while(carry)bignum_ans+*bignum_ans=carry%base;carry/=base;说明：函数中的数组是引用传递，传递的是数组的首元素的地址，可用指针来代替，当前指针所指向的为0元素，后面的代码相同。有的同学可能提出，在加法运算中的进位不管进制是多少，进位只可

6、能出现1,用while循环没有意义，在这里说明一下，为了跟后面乘法中出现的代码相匹配才采用这种处理方法，实现代码的统一性。(二)减法：bignum11329475461243bignum21329181324341borrow0100bignum_ans085568722902图三减法的计算过程图三表示出了减法的计算过程，与加法不同的地方是进位变成了借位，另外就是计算结果的位数可 能会比被减数的位数少，因此在处理过程中要更要注意结果到底是多少位的。其次，日常我们做减法时，如果被减数小于减数，我们是把两数反过来进行相减，在前面添加负号标识。因此，我们在编写减法子函数时是约定bignum1大于bi

7、gnum2的，调用时首先判断两个高精度数的大小，然后根据两数的大小决定如何调用。减法的实现过程如图四所示：高精度数比较程序代码：int bignumcmp( int *bignum1, int *bignum2 )if (*bignum1-*bignum2) return *bignum1-*bignum2;for (int pos=*bignum1; pos>0; pos-)if ( bignum1pos-bignum2pos ) return bignum1pos-bignum2pos; return 0;说明：bignum1>bignum2 返回正整数，bignum1= bi

8、gnum2 返回 0, bignuml v bignum2 返回负整数。解释：首先进行两数的位数的比较，如果位数相同再从高位向低位比较。高精度减法程序代码( bignum1-bignum2 bignum_ans ): void subtract( int *bignum1, int *bignum2, int *bignum_ans )( int borrow=0;memset( bignum_ans, 0, sizeof(bignum_ans);*bignum_ans=*bignum1;for(int pos=1; pos<=*bignum_ans; pos+)(bignum_ansp

9、os=bignum1pos-borrow-bignum2pos; if(bignum_anspos<0)bignum_anspos+=base;borrow=1;elseborrow=0;while( !bignum_ans*bignum_ans ) -*bignum_ans;乘法的计算过程正如图五所示的从乘数的最低位起枚举每-位与被乘数相乘，累加到结果当中。局粕度乘局粕度头际是多次调用单粕度数乘局粕局数运鼻。1234X4321(1)1234(2)2468(3)3702(4)49365332114图五乘法的计算过程首先看图六单精度乘高精度实现过程单精度乘高精度程序代码( n*bignum

10、 bignum_ans): void SingleMultiply(int n, int *bignum, int *bignum_ans)(int carry=0;memset(bignum_ans, 0, sizeof(bignum_ans);*bignum_ans=*bignum;for(int pos=1; pos<=*bignum_ans; pos+)(carry+=n*bignumpos;bignum_anspos=carry%base;carry/=base;while(carry)(bignum_ans+*bignum_ans=carry%base;carry/=base

11、;高精度数乘高精度数，实质就是在单精度数乘高精度数的基础上枚举各个乘数位与被乘数相乘，累计到结果当中。其中乘数中的第J位与被乘数中的第I位相乘时，结果应该保存到结果的第I +J 1位中，因为如果存在进位的问题结果的位数可能为乘数与被乘数的位数和，也可能为两者位数和减一，这一点也应该单独处理。过程就不再展示了，具体的请阅读下面的程序代码：高精度乘高精度程序代码(bignum1*bignum2bignum_ans):void BignumMultiply( int *bignum1, int *bignum2, int *bignum_ans)(int carry=0, i, j;memset(b

12、ignum_ans, 0, sizeof(bignum_ans);for (j=1; j<=*bignum2; j+)(for(i=1; i<=*bignum1; i+)(bignum_ansi+j-1+=carry+bignum1i*bignum2j;carry=bignum_ansi+j-1/base;bignum_ansi+j-1%=base;一i=j+*bignum1;while(carry)(bignum_ansi+=carry%base;carry/=base;*bignum_ans=*bignum1+*bignum2;while( !bignum_ans*bignum

13、_ans ) -*bignum_ans;(四)除法：除法在高精度计算中是最为特殊的，在近几年联赛中并没有出现类似的题目，除法类的高精度题目0,而在例二中56并不能除尽45,出会涉及到精度和循环节问题，在这里首先用表格分析两个例子：例_： 3除以8,被除数3306040商0.375余数3640例二：45 除以 56,结果为 0.803(571428)被除数454502020032040080240160480商0.803571428余数452203240824164832在例一中展示的为能被除尽的情形，能被除尽的条件是余数为现571428这个循环节，出现循环节的条件是当前的余数曾经出现在前面求得

14、的余数序列中。直接模拟除法操作进行程序设计的过程如图七所示：根据上述处理过程编写代码如下:void divide(int x, int y)int remaindermaxlen, quotientmaxlen, repeat_pos=-1, pos=0;quotient0=x/y;remainder0=x%y;while( remainderpos )for(int i=0; i<pos; i+)/查找余数序列if(remainderi=remainderpos)repeat_pos=i; break; if(repeat_pos>-1) break;pos+;if(pos=ma

15、xlen) pos-; break; /是否已到求解的精度remainderpos=remainderpos-1*10%y;quotientpos=remainderpos-1*10/y;cout<<quotient0;if(remainder0)cout<<'.'int i=1;if(repeat_pos>-1)for(i=1; i<=repeat_pos; i+) cout<<quotienti;cout<<'('while(i<=pos) cout<<quotienti+;if(

16、repeat_pos>-1) cout<<')' cout<<endl;说明：maxlen为指定的精度或最大的小数位数加一，根据程序需要而定义。从上面的程序可以看出，在求得每一个余数后，都要到前面的余数序列中查找是否已存在，来判定 是否出现循环节，这种方法即费时又浪费空间。有没有更好的方法来解决这个问题呢？我们从数学上的自然数找一下规律。任何一个自然数都可拆分为若干质数的藉的形式 (n=p1K1*p2K2,p nKn)，在所有的质数中，只有 2和5才能被除尽，其他的均出现循环节。我们是否可以从2和5上找出解决方法来呢?将被除数和除数转化为互质的两个

17、数，从除数中统计出2和5的个数n2和n5,且一个2和一个5都仅产生一位小数，这些小数是肯定不出现在循环节中的。反过来说，在小数点后面，循环节前面小数的 位数就是n2和n5中的较大者。如果求解出循环节前的小数以后，余数仍不为0,那就存在着循环节了，循环节的长度为再次得到的这个余数。请看下面的代码：小数点后循环节前的位数程序代码：int numBeforeRepeat(int x, int y)(int n2=0, n5=0;while(y%2=0)n2+; y/=2;while(y%5=0)n5+; y/=5;while(x%2=0)n2-; x/=2;while(x%5=0)n5-; x/=2

18、;if(n2<n5) n2=n5;return n2>0?n2:0;高精度除法程序代码：void divide(int x, int y)int BeforeRepeat=numBeforeRepeat(x, y);cout<<x/y;x%=y;if(x)cout<<'.'for(int i=0; i<BeforeRepeat; i+)x*=10;cout<<x/y;x%=y;if(x)cout<<'('int remainder=x;doremainder*=10;cout<<rem

19、ainder/y;remainder%=y;while(remainder != x);cout<<')' cout<<endl;利用这种解法一方面省去了余数和商的存储空间，另一方面也无需再到余数序列中查找余数是否出 现过，即节省空间，又提高了程序的执行效率。所以遇到高精度除法问题时，可以优选第二种解法。三. 万进制高精度数的输出问题：采用万进制来进行高精的加、减、乘三种运算，虽然提高了程序的执行效率，但在输出时却带来了 问题，如在加法示例中的结果从高位到低位分别为1, 393, 1370, 1584,如果我们仍按照平常的输出一样直接输出时，结果为 139313701584,但我们定义万进制时明确过每一位是占十进制的四位，393这一位应该输出0393而不是393。因此我们在输出时应首先输出最高位(因