高精度运算(C++)

《高精度运算(C++)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、个高精度数字，左侧为其高位，右侧为其低位，在计算中往往会因进位（carry）或借位（borrow）导致高位增长或减少，因此我们定义一个整型数组（intbignum[maxlen]）从低位向高位实现高精度整数的存储，数组的每个元素存储高精度数中的一位。（如下表所示）高精度数3（高位）……794（低位）intbignum[i]n……210显然，在C++语言中，int类型（4个字节/32位计算机）元素存储十进制的一位数字非常浪费空间，并且运算量也非常大，因此常将程序代码优化为万进制，即数组的每个元素存储高精数字的四位。在后面的叙述过程中均以万进制为例介绍。（为什么选择万进制，

3、而不选择更大的进制呢？十万进制中的最大值99999相乘时得到的值是9999800001超过4个字节的存储范围而溢出，从而导致程序计算错误。）在实际编写程序代码过程中常作如下定义：constintbase=10000;constintmaxlen=1000+1;intbignum[maxlen];说明：base表示进制为万进制，maxlen表示高精度数的长度，1个元素能存储4个十进制位，1000个元素就存储4000个十进制位，而加1表示下标为0的元素另有它用，常用作存储当前高精度数字的位数。二.各种运算的程序实现（一）加法：首先回顾一下小学中曾学习的竖式加法，见图一：bi

4、gnum1[]9475461243bignum2[]9181324341carry1000bignum_ans[]139313701584图一加法的计算过程从上面的图中我们可以得知，做加法运算是从低位向高位进行，如果有进位，下一位进行相加时要加上进位，如果最高位已计算完还有进位，就要增加存储结果的位数，保存起进位来。关于进位的处理，往往定义单独变量carry进行存储，程序实现的过程如图二所示：初始化进位carry赋初始值0，结果的位数为两个加数的最大位数。当前位超过最高位了？处理当前位和进位NY还有进位么？N结束处理进位Y......供学习、参考、下载、分享......

5、word......专业资料、精品文档图二加法的实现过程高精度加法程序代码（bignum1+bignum2→bignum_ans）：voidaddition(int*bignum1,int*bignum2,int*bignum_ans){intcarry=0;memset(bignum_ans,0,sizeof(bignum_ans));//memset作用是在一段内存块中填充某个给定的值，它是对较大的结构体或数组进行清零操作的一种最快方法。*bignum_ans=*bignum1>*bignu2?*bignum1:*bignum2;for(intpos=1;pos<=

6、*bignum_ans;pos++){carry+=bignum1[pos]+bignum2[pos];bignum_ans[pos]=carry%base;carry/=base;}while(carry){bignum_ans[++*bignum_ans]=carry%base;carry/=base;}}说明：函数中的数组是引用传递，传递的是数组的首元素的地址，可用指针来代替，当前指针所指向的为0元素，后面的代码相同。有的同学可能提出，在加法运算中的进位不管进制是多少，进位只可能出现1，用while循环没有意义，在这里说明一下，为了跟后面乘法中出现的代码相匹配才采

7、用这种处理方法，实现代码的统一性。（二）减法：bignum1[]1329475461243bignum2[]1329181324341borrow0100bignum_ans[]085568722902图三减法的计算过程图三表示出了减法的计算过程，与加法不同的地方是进位变成了借位，另外就是计算结果的位数可能会比被减数的位数少，因此在处理过程中要更要注意结果到底是多少位的。其次，日常我们做减法时，如果被减数小于减数，我们是把两数反过来进行相减，在前面添加负号标识。因此，我们在编写减法子函数时是约定bignum1大于bignum2的，调用时首