高精度运算精选PPT讲稿.ppt

《高精度运算精选PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《高精度运算精选PPT讲稿.ppt（24页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、关于高精度运算第一页，讲稿共二十四页哦Pascal语言的常用数据类型装配实型扩展型 第二页，讲稿共二十四页哦C+常用基本类型第三页，讲稿共二十四页哦问题的提出程序设计语言所处理加工的各类数据都有相应的值域限定，一旦某类型的数据超出了规定的范围，运算结果就会出错。但是在有些试题中，变量运算对象的数值范围是任何数据类型所无法容纳的，因此人们不得不采用高精度运算。第四页，讲稿共二十四页哦数据结构由于待处理的数据超过了任何一种数据类型所能容纳的范围，因此必须采用数字串数字串的形式输入，并将其转化为整数数组整数数组。该数组的每一个元素对应一位十进制数，由其下下标顺序标顺序指明位序号。运算规则如同算术运算

2、。由于高精度运算的结果可能使得数据长度发生增减，因此除需要用整数数组存储数据外，还需要用一个整数变量记录整数数组的元素个数，即数据的实际长度数据的实际长度。第五页，讲稿共二十四页哦C语言描述#defineMAXLEN10000typedefstructintlen;/*长度*/intsMAXLEN;/*表示整数的数组*/Integer;Integera,b;第六页，讲稿共二十四页哦C+语言描述constintMAXLEN=10000;classIntegerpublic:intlen;/长度intsMAXLEN;/表示整数的数组;Integera,b;第七页，讲稿共二十四页哦将数字串转化为整数

3、数组a的方法如下：CharsMAXLEN;cins;a.len=strlen(s);for(inti=0;ib.len?a.len:b.len;/确定最大位数确定最大位数for(inti=0;i=len;i+)c.si=0;/C各位清各位清0for(i=0;i=10)c.si-=10;/调整进位调整进位c.si+1+;/调整当前位调整当前位if(c.slen0)len+;/调整结果长度调整结果长度c.len=len;returnc;第十页，讲稿共二十四页哦说明C各位清各位清0：for(inti=0;ib)1.依照由低位至高位（第0位至第len-1位）的顺序进行减法运算。2.在每一次按位运算中，

4、若出现不够减的情况即a.sib0Integerc;intlen=a.len;for(inti=0;ilen;i+)c.si=0;for(i=0;ilen;i+)c.si+=a.si-b.si;if(c.si1)&(c.slen=0)len-;c.len=len;returnc;第十三页，讲稿共二十四页哦四、乘法（高精度四、乘法（高精度*单精度）单精度）c=a*b(a,c为为Integer,b为为int)n按照乘法规则，从a的第0位开始逐位与b相乘。n在第i位乘法运算中（0=i=a.len-1),a的i位与b的乘积必须加上i-1位的进位(i-1位的乘积除以10的整商)，然后规整积的i位（取i位的

5、乘积对10的余数）。第十四页，讲稿共二十四页哦Integermul1(constInteger&a,intb)Integerc;intlen=a.len;for(inti=0;i=MAXLEN;i+)c.si=0;for(i=0;i=10)c.slen+=c.slen-1/10;c.slen-1=c.slen-1%10;len+;c.len=len;returnc;第十五页，讲稿共二十四页哦五、乘法（高精度五、乘法（高精度*高精度）高精度）Integermul2(constInteger&a,constInteger&b)Integerc;intlen=a.len+b.len+1;for(in

6、ti=0;ilen;i+)c.si=0;for(i=0;ia.len;i+)for(intj=0;j1)&(c.slen-1=0)len-;c.len=len;returnc;第十六页，讲稿共二十四页哦六六.对上述算法的评价对上述算法的评价n优点：思路清晰，描述简单，易于实现。n缺点：1用整型向量存储高精度数，浪费空间。2用到的算法虽然简单，但效率太差。第十七页，讲稿共二十四页哦对上述算法的改进意见对上述算法的改进意见n1从数据结构上作进一步改进，充分利用内存空间，提高算法的空间效率。上述算法有很大的改进空间。n2改进算法的时间复杂性，特别是乘法和除法的算法效率，用大整数的乘法算法或更好的算法

7、作深入改进。n3将上述算法扩展到高精度实数算法。n4将上述算法扩展到高精度分数算法。第十八页，讲稿共二十四页哦改善高精度运算的效率改善高精度运算的效率n以上接触到的高精度存储方法是用一个整型数组来表示一个很大的数，数组中的每一个数表示一位十进制数字。但这种方法的缺点是，如果十进制数的位数很多，则对应数组的长度会很长，并增加了高精度计算的时间。那么有什么方法可以改善高精度运算的效率呢？下面，我们给出两种方法：n1.扩大进制数：扩大进制数：n2.建立因子表：建立因子表：第十九页，讲稿共二十四页哦1.扩大进制数：扩大进制数：n我们可以考虑用一个数记录2位数字、3位数字或更多位数字。n理论上来说，数组

8、中的每个数表示的数字越多，数组的长度就越短，程序运行的时间也就越短。但是，我们还需考虑到计算机中的一个数的取值范围，必须保证它们在运算过程中不会越界。n在权衡了两方面的情况后得出：用一个longint记录4位数字是最佳的方案。那么这个数组就相当于一个10000进制的数，其中每一个元素都是10000进制下的一位数。n两个整数（10000进制）数组的加法和减法与前面所讲的十进制运算方法相比，除了进制数有所变化外，其他没有什么区别。第二十页，讲稿共二十四页哦2.建立因子表：建立因子表：n任何自然数都可以表示为一系列质因数的乘积方式。npl,p2，pt为质因子。设num数组为自然数n，其中numi为因

9、子i的次幂数。显然，numk,numk-1，num1构成了一个自然数，有了自然数n的因子表num，就可以十分方便地进行乘法或除法运算。第二十一页，讲稿共二十四页哦n例如整数x含有k个因子i,n我们按照上述方法依次处理x的每一个因子，得出的num即为积或商。第二十二页，讲稿共二十四页哦本章复习题一、高精度加法运算算法高精度加法运算算法二、乘法（高精度二、乘法（高精度*单精度单精度,高精度高精度*高精度）高精度）(注注意意：不不能能忘忘记记数数据据结结构构，建建议议大大家家采采用用向向量量方方式改写算法式改写算法)三、上机练习：三、上机练习：2980,2981第二十三页，讲稿共二十四页哦感感谢谢大大家家观观看看第二十四页，讲稿共二十四页哦