高精度运算(C++)

万进制高精度运算（C++语言）

目前在青少年信息学奥林匹克竞赛中所涉及到的高精度计算包括加(addition)、减(subtract)、乘(multiply)、除(divide)四种基本运算。其中乘法分高精度数乘高精度数和单精度数乘高精度数两种，除法一般指两个单精度数相除，求解最终指定精度的解，找出循环节或输出指定精度位数的小数。（注：高精度数与单精度数均指整数）

主要的解题思想是利用在小学就曾学习过的竖式加减乘除法则，用程序语言实现存在的问题主要有如何存储高精度数的值，如何实现计算等问题。 一. 高精度数字的存储

我们日常书写一个高精度数字，左侧为其高位，右侧为其低位，在计算中往往会因进位（carry ）或借位（borrow ）导致高位增长或减少，因此我们定义一个整型数组（int bignum[maxlen]）从低位向高

显然，在C++语言中，int 类型（4个字节/32位计算机）元素存储十进制的一位数字非常浪费空间，并且运算量也非常大，因此常将程序代码优化为万进制，即数组的每个元素存储高精数字的四位。

在后面的叙述过程中均以万进制为例介绍。（为什么选择万进制，而不选择更大的进制呢？十万进制中的最大值99999相乘时得到的值是9999800001超过4个字节的存储范围而溢出，从而导致程序计算错误。）

在实际编写程序代码过程中常作如下定义： const int base=10000; const int maxlen=1000+1; int bignum[maxlen];

说明：base 表示进制为万进制，maxlen 表示高精度数的长度，1个元素能存储4个十进制位，1000个元素就存储4000个十进制位，而加1表示下标为0的元素另有它用，常用作存储当前高精度数字的位数。 二. 各种运算的程序实现 （一）加法：

从上面的图中我们可以得知，做加法运算是从低位向高位进行，如果有进位，下一位进行相加时要加上进位，如果最高位已计算完还有进位，就要增加存储结果的位数，保存起进位来。关于进位的处理，往往定义单独变量carry 进行存储，程序实现的过程如图二所示：

高精度加法程序代码（bignum1+bignum2→bignum_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; pos

carry/=base; } }

说明：函数中的数组是引用传递，传递的是数组的首元素的地址，可用指针来代替，当前指针所指向的为0元素，后面的代码相同。

有的同学可能提出，在加法运算中的进位不管进制是多少，进位只可能出现1，用while 循环没有意义，在这里说明一下，为了跟后面乘法中出现的代码相匹配才采用这种处理方法，实现代码的统一性。 （二）减法：

图三表示出了减法的计算过程，与加法不同的地方是进位变成了借位，另外就是计算结果的位数可能会比被减数的位数少，因此在处理过程中要更要注意结果到底是多少位的。

其次，日常我们做减法时，如果被减数小于减数，我们是把两数反过来进行相减，在前面添加负号标识。因此，我们在编写减法子函数时是约定bignum1大于bignum2的，调用时首先判断两个高精度数的大小，然后根据两数的大小决定如何调用。减法的实现过程如图四所示：

高精度数比较程序代码：

int bignumcmp( int *bignum1, int *bignum2 ){ if (*bignum1-*bignum2) return *bignum1-*bignum2; for (int pos=*bignum1; pos>0; pos--) if ( bignum1[pos]-bignum2[pos] ) return bignum1[pos]-bignum2[pos]; return 0;

说明：bignum1>bignum2返回正整数，bignum1＝＝bignum2返回0，bignum1＜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

else{

borrow=0; } } while( !bignum_ans[*bignum_ans] ) --*bignum_ans; }

（三）乘法：

乘法的计算过程正如图五所示的从乘数的最低位起枚举每一位与被乘数相乘，累加到结果当中。高精度乘高精度实际是多次调用单精度数乘高精高数运算。

(4)

(3) 4 5

(2) 3 9 3

X (1) 2 7 3 3

1 4 1 4 0 6 2

2 3 2 6 2 1

3 2 3 8 1

4 1 4 4

图五 乘法的计算过程

首先看一下单精度数乘高精度数的实现过程，如图六所示：

图六 单精度乘高精度实现过程

单精度乘高精度程序代码（n*bignum→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

高精度数乘高精度数，实质就是在单精度数乘高精度数的基础上枚举各个乘数位与被乘数相乘，累计到结果当中。其中乘数中的第J 位与被乘数中的第I 位相乘时，结果应该保存到结果的第I ＋J －1位中，因为如果存在进位的问题结果的位数可能为乘数与被乘数的位数和，也可能为两者位数和减一，这一点也应该单独处理。过程就不再展示了，具体的请阅读下面的程序代码： 高精度乘高精度程序代码（bignum1*bignum2→bignum_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

（四）除法：

除法在高精度计算中是最为特殊的，在近几年联赛中并没有出现类似的题目，除法类的高精度题目会涉及到精度和循环节问题，在这里首先用表格分析两个例子： 例一：3除以8

例二：45

在例一中展示的为能被除尽的情形，能被除尽的条件是余数为0，而在例二中56并不能除尽45，出现571428这个循环节，出现循环节的条件是当前的余数曾经出现在前面求得的余数序列中。 直接模拟除法操作进行程序设计的过程如图七所示：

图七 高精度除法实现过程

根据上述处理过程编写代码如下： void divide(int x, int y){ int remainder[maxlen], quotient[maxlen], repeat_pos=-1, pos=0; quotient[0]=x/y; remainder[0]=x%y; while( remainder[pos] ){ for(int i=0; i-1) break; pos++; if(pos==maxlen) {pos--; break; }//是否已到求解的精度 remainder[pos]=remainder[pos-1]*10%y; quotient[pos]=remainder[pos-1]*10/y; } cout-1){ for(i=1; i

cout-1) cout

说明：maxlen 为指定的精度或最大的小数位数加一，根据程序需要而定义。

从上面的程序可以看出，在求得每一个余数后，都要到前面的余数序列中查找是否已存在，来判定是否出现循环节，这种方法即费时又浪费空间。有没有更好的方法来解决这个问题呢？

我们从数学上的自然数找一下规律。任何一个自然数都可拆分为若干质数的幂的形式

（n=p1*p2„pn ），在所有的质数中，只有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); cout

利用这种解法一方面省去了余数和商的存储空间，另一方面也无需再到余数序列中查找余数是否出现过，即节省空间，又提高了程序的执行效率。所以遇到高精度除法问题时，可以优选第二种解法。

三. 万进制高精度数的输出问题：

采用万进制来进行高精的加、减、乘三种运算，虽然提高了程序的执行效率，但在输出时却带来了问题，如在加法示例中的结果从高位到低位分别为1，393，1370，1584，如果我们仍按照平常的输出一样直接输出时，结果为[1**********]4，但我们定义万进制时明确过每一位是占十进制的四位，393这一位应该输出0393而不是393。因此我们在输出时应首先输出最高位（因最高位前面是不补0的），然后再输出其他位，如果不足四位，用0补充。

K1K2Kn

万进制输出程序代码：

void printbignum(int *n){ int *p=*n+n; coutn){ cout.width(4); cout

至此，有关万进制的相关内容已全部介绍完毕，在本文中的示例代码仍可根据个人的习惯进行精简，在熟练使用以后，在解题的过程中，就不需要再为如何解决高精度问题浪费宝贵的时间啦。相关练习题可参考“编程实战”中的高精度专项练习题。

附一：C ＋＋语言输出控制语句：

cout.fill(char ch) 设置输出留空位置的填充字符（作用于所有的输出）只调用一次 cout.width(int n)

附二：相关英文单词carry['kær ɪ]: 进位 borrow['bɒr əʊ]: 借位 addition[ə'di ʃən]: 加 subtract[səb'trækt]: 减 multiply['mʌlt ɪpla ɪ]: 乘

附三：编程实战URL

http://xpaq.kmip.net/bbs/forumdisplay.php?fid=163

divide[di'vaid]: 除 quotient['kwəuʃənt]: 商 remainder[rɪ'me ɪnd ə(r)]: 余数 decimal['desɪml]: 小数

设置输出域的宽度（只作用于下一次输出）

每次都要调用