高精度运算精选PPT.ppt

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

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

2、规则如同算术运算。由于高精度运算的结果可能使得数据长度发生增减，因此除需要用整数数组存储数据外，还需要用一个整数变量记录整数数组的元素个数，即数据的实际长度数据的实际长度。现在学习的是第5页，共24页C语言描述#defineMAXLEN10000typedefstructintlen;/*长度*/intsMAXLEN;/*表示整数的数组*/Integer;Integera,b;现在学习的是第6页，共24页C+语言描述constintMAXLEN=10000;classIntegerpublic:intlen;/长度intsMAXLEN;/表示整数的数组;Integera,b;现在学习的是第7页

3、，共24页将数字串转化为整数数组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;现在学习的是第10页，共24页说明C各位清各位清0：for(inti=0;ib)1.依照由低位至高位（第0位至第len-1位）的顺序进行

4、减法运算。2.在每一次按位运算中，若出现不够减的情况即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;现在学习的是第13页，共24页四、乘法（高精度四、乘法（高精度*单精度）单精度）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位的乘积除以1

5、0的整商)，然后规整积的i位（取i位的乘积对10的余数）。现在学习的是第14页，共24页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;现在学习的是第15页，共24页五、乘法（高精度五、乘法（高精度*高精度）高精度）Integermul2(constInteger&a,constInteger&b)Integerc;intl

6、en=a.len+b.len+1;for(inti=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;现在学习的是第16页，共24页六六.对上述算法的评价对上述算法的评价n优点：思路清晰，描述简单，易于实现。n缺点：1用整型向量存储高精度数，浪费空间。2用到的算法虽然简单，但效率太差。现在学习的是第17页，共24页对上述算法的改进意见对上述算法的改进意见n1从数据结构上作进一步改进，充分利用内存空间，提高算法的空间效率。上述算法有很大的改进空间。n2改进算法的时间复杂性，特别

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

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

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