高精度运算(C++).doc

万进制高精度运算（C+语言）目前在青少年信息学奥林匹克竞赛中所涉及到的高精度计算包括加(addition)、减(subtract)、乘(multiply)、除(divide)四种基本运算。其中乘法分高精度数乘高精度数和单精度数乘高精度数两种，除法一般指两个单精度数相除，求解最终指定精度的解，找出循环节或输出指定精度位数的小数。（注：高精度数与单精度数均指整数）主要的解题思想是利用在小学就曾学习过的竖式加减乘除法则，用程序语言实现存在的问题主要有如何存储高精度数的值，如何实现计算等问题。一. 高精度数字的存储我们日常书写一个高精度数字，左侧为其高位，右侧为其低位，在计算中往往会因进位（carry）或借位（borrow）导致高位增长或减少，因此我们定义一个整型数组（int bignummaxlen）从低位向高位实现高精度整数的存储，数组的每个元素存储高精度数中的一位。（如下表所示）高精度数3（高位）794（低位）int bignumin210显然，在C+语言中，int类型（4个字节/32位计算机）元素存储十进制的一位数字非常浪费空间，并且运算量也非常大，因此常将程序代码优化为万进制，即数组的每个元素存储高精数字的四位。在后面的叙述过程中均以万进制为例介绍。（为什么选择万进制，而不选择更大的进制呢？十万进制中的最大值99999相乘时得到的值是9999800001超过4个字节的存储范围而溢出，从而导致程序计算错误。）在实际编写程序代码过程中常作如下定义：const int base=10000;const int maxlen=1000+1;int bignummaxlen;说明：base表示进制为万进制，maxlen表示高精度数的长度，1个元素能存储4个十进制位，1000个元素就存储4000个十进制位，而加1表示下标为0的元素另有它用，常用作存储当前高精度数字的位数。二. 各种运算的程序实现（一）加法：首先回顾一下小学中曾学习的竖式加法，见图一：bignum19475461243bignum29181324341carry1000bignum_ans139313701584图一 加法的计算过程从上面的图中我们可以得知，做加法运算是从低位向高位进行，如果有进位，下一位进行相加时要加上进位，如果最高位已计算完还有进位，就要增加存储结果的位数，保存起进位来。关于进位的处理，往往定义单独变量carry进行存储，程序实现的过程如图二所示：初始化 进位carry赋初始值0，结果的位数为两个加数的最大位数。当前位超过最高位了？处理当前位和进位NY还有进位么？N结束处理进位Y图二 加法的实现过程高精度加法程序代码（bignum1+bignum2bignum_ans）：void addition(int *bignum1, int *bignum2, int *bignum_ans)int carry=0;memset( bignum_ans, 0, sizeof(bignum_ans) );/ memset作用是在一段内存块中填充某个给定的值，它是对较大的结构体或数组进行清零操作的一种最快方法。*bignum_ans=*bignum1*bignu2?*bignum1:*bignum2;for(int pos=1; pos0; pos-)if ( bignum1pos-bignum2pos ) return bignum1pos-bignum2pos; return 0;说明：bignum1bignum2返回正整数，bignum1bignum2返回0，bignum1bignum2返回负整数。解释：首先进行两数的位数的比较，如果位数相同再从高位向低位比较。高精度减法程序代码（bignum1-bignum2bignum_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_anspos=bignum1pos-borrow-bignum2pos;if(bignum_anspos0)bignum_anspos+=base;borrow=1;elseborrow=0;while( !bignum_ans*bignum_ans ) -*bignum_ans;（三）乘法：乘法的计算过程正如图五所示的从乘数的最低位起枚举每一位与被乘数相乘，累加到结果当中。高精度乘高精度实际是多次调用单精度数乘高精高数运算。1234X4321(1)1234(2)2468(3)3702(4)49365332114图五 乘法的计算过程首先看一下单精度数乘高精度数的实现过程，如图六所示：初始化 进位carry赋初始值0，结果的位数被乘数的位数。当前位超过最高位了？处理当前位和进位NY还有进位么？N结束处理进位Y图六 单精度乘高精度实现过程单精度乘高精度程序代码（n*bignumbignum_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;高精度数乘高精度数，实质就是在单精度数乘高精度数的基础上枚举各个乘数位与被乘数相乘，累计到结果当中。其中乘数中的第J位与被乘数中的第I位相乘时，结果应该保存到结果的第IJ1位中，因为如果存在进位的问题结果的位数可能为乘数与被乘数的位数和，也可能为两者位数和减一，这一点也应该单独处理。过程就不再展示了，具体的请阅读下面的程序代码：高精度乘高精度程序代码（bignum1*bignum2bignum_ans）：void BignumMultiply( int *bignum1, int *bignum2, int *bignum_ans)int carry=0, i, j;memset(bignum_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_ans ) -*bignum_ans;（四）除法：除法在高精度计算中是最为特殊的，在近几年联赛中并没有出现类似的题目，除法类的高精度题目会涉及到精度和循环节问题，在这里首先用表格分析两个例子：例一：3除以8，结果为0.375被除数3306040商0.375余数3640例二：45除以56，结果为0.803(571428)被除数454502020032040080240160480商0.803571428余数452203240824164832在例一中展示的为能被除尽的情形，能被除尽的条件是余数为0，而在例二中56并不能除尽45，出现571428这个循环节，出现循环节的条件是当前的余数曾经出现在前面求得的余数序列中。直接模拟除法操作进行程序设计的过程如图七所示：初始化 商存储数组quotient清零，余数数组remainder清零。余数为0？处理当前位NY结束 输出整除值，存储余数余数序列中出现过么？处理循环节YN图七 高精度除法实现过程根据上述处理过程编写代码如下：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-1) break;pos+;if(pos=maxlen) pos-; break; /是否已到求解的精度remainderpos=remainderpos-1*10%y;quotientpos=remainderpos-1*10/y;coutquotient0;if(remainder0)cout-1)for(i=1; i=repeat_pos; i+) coutquotienti;cout(;while(i=pos) cout-1) cout);coutendl;说明：maxlen为指定的精度或最大的小数位数加一，根据程序需要而定义。从上面的程序可以看出，在求得每一个余数后，都要到前面的余数序列中查找是否已存在，来判定是否出现循环节，这种方法即费时又浪费空间。有没有更好的方法来解决这个问题呢？我们从数学上的自然数找一下规律。任何一个自然数都可拆分为若干质数的幂的形式（n=p1K1*p2K2pnKn），在所有的质数中，只有2和5才能被除尽，其他的均出现循环节。我们是否可以从2和5上找出解决方法来呢？将被除数和除数转化为互质的两个数，从除数中统计出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;if(n20?n2:0;高精度除法程序代码：void divide(int x, int y)int BeforeRepeat=numBeforeRepeat(x, y);coutx/y; x%=y;if(x)cout.;for(int i=0; iBeforeRepeat; i+)x*=10;coutx/y;x%=y;if(x)cout(;int remainder=x;doremainder*=10;coutremainder/y;remainder%=y;while(remainder != x);cout);coutendl;利用这种解法一方面省去了余数和商的存储空间，另一方面也无需再到余数序列中查找余数是否出现过，即节省空间，又提高了程序的执行效率。所以遇到高精度除法问题时，可以优选第二种解法。三. 万进制高精度数的输出问题：采用万进制来进行高精的加、减、乘三种运算，虽然提高了程序的执行效率，但在输出时却带来了问题，如在加法示例中的结果从高位到低位分别为1，393，1370，1584，如果我们仍按照平常的输出一样直接输出时，结果为139313701584，但我们定义万进制时明确过每一位是占十进制的四位，393这一位应该输出0393而不是393。因此我们在输出时应首先输出最高位（因最高位前面是不补0的），然后再输出其他位，如果不足四位，用0补充。万进制输出程序代码：void printbignum(int *n)int *p=*n+n;coutn) cout.width(4); cout*p-; coutendl;至此，有关万进制的相关内容已全部介绍完毕，在本文中的示例代码仍可根据个人的习惯进行精简，在熟练使用以后，在解题的过程中，就不需要再为如何解决高精度问题浪费宝贵的时间啦。相关练习题可参考“编程实战”中的高精度专项练习题。附一：C语言输出控制语句：cout.fill(char ch)设置输