欢迎来到天天文库
浏览记录
ID:45759796
大小:85.00 KB
页数:7页
时间:2019-11-17
《高精度运算(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的,调用时首
此文档下载收益归作者所有