高精度运算c语言PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,高精度运算,内蒙古师范大学计算机与信息工程学院,孟繁军,1,运算的前提条件：类型范围,确定各类型的取值范围,int:-2,147,483,6482,147,483,647,unsigned int:0 to 4,294,967,295,long int:-2,147,483,648 to 2,147,483,647,long long:-9,223,372,036,854,775,808 to 9,223,372,036,854,775,807,float:3.4E+/-38(7 digits),double:1.7E+/-308(15 digits),long double:1.2E+/-4932(19 digits),2,2025/4/20 周日,高精度运算的基本方法,1,、加数、减数、运算结果的输入和存储运算因子超出了整型、实型能表示的范围，肯定不能直接用一个数的形式来表示。在运算过程中，能表示多个数的数据类型有两种：,数组和字符串。,（,1,）数组：每个数组元素存储,1,位（在优化时，这里是一个重点！），有多少位就需要多少个数组元素；用数组表示数的优点：每一位都是数的形式，可以直接加减；运算时非常方便用数组表示数的缺点：数组不能直接输入；输入时每两位数之间必须有分隔符，不符合数值的输入习惯；,（,2,）字符串：字符串的最大长度是多少，可以表示多少位数字？用字符串表示数的优点：能直接输入输出，输入时，每两位数之间不必分隔符，符合数值的输入习惯；用字符串表示数的缺点：字符串中的每一位是一个字符，不能直接进行运算，必须先将它转化为数值再进行运算；运算时非常不方便；,（,3,）因此，综合以上所述，对上面两种数据结构取长补短：用字符串读入数据，用数组存储数据：,3,2025/4/20 周日,高精度运算的运算过程,在往下看之前，大家先列竖式计算,35+86,。注意的问题：（,1,）运算顺序：两个数靠右对齐；从低位向高位运算；先计算低位再计算高位；（,2,）运算规则：同一位的两个数相加再加上从低位来的进位，成为该位的和；这个和去掉向高位的进位就成为该位的值；如上例：,3+8+1=12,，向前一位进,1,，本位的值是,2,；可借助取余,、,整除运算完成这一步；（,3,）最后一位的进位：如果完成两个数的相加后，进位位值不为,0,，则应添加一位；（,4,）如果两个加数位数不一样多，则按位数多的一个进行计算；,4,2025/4/20 周日,高精度的十进制算,一般形式：,输入时为数串,转化为整数数组（该数组的每一个元素对应一位十进制数，并使用一变量记录数组的实际长度，即数组元素有效个数）,转化方法：,memset(a,0,number*sizeof(int);,k=length(s);,for(i=1;i=lb),x=la;,else,x=lb;,for(i=1;i=x;i+),ai=ai+bi;,ai+1=ai+1+ai/10;,ai=ai%10;,while(ax+10),x=x+1;,la=x-1;,7,2025/4/20 周日,减法运算,依照由低位至高位（第,1,位至第,la,位）的顺序进行减法运算。,在每一次的减法运算中，若出现不够减的情况,(aibi),，则向高位借位,(ai+1=ai+1-1,ai=ai+10),。,在进行了,la,位的减法后，若最高位为零,(ala=0),则,a,的长度减,1。,8,2025/4/20 周日,减法运算算法,/*a=a-b*/,void sub(int a,int b),int i;,for(i=1;i=la;i+),if(aibi),ai+1=ai+1-1;,ai=ai+10;,ai=ai-bi;,while(ala=0)la-;,9,2025/4/20 周日,乘法运算,按照乘法规则，从,a,的第,1,位开始逐位与,C,相乘。,在第,i,位乘法运算中（,1ila,）,a,的,i,位与,C,的乘积必加上,i-1,位的进位（,i-1,位的乘积除以,10,的整商），然后规整积的,i-1,位（取,i-1,位的乘积对,10,的余数）。,10,2025/4/20 周日,乘法运算算法,void multiply(int a,int c),int i;,a1=a1*c;,for(i=2;i=10),la=la+1;,ala=ala-1/10;,ala-1=ala-1%10;,11,2025/4/20 周日,改善的高精度运算的效率,以上的方法的有明显的缺点：（,1,）浪费空间：一个整型变量只存放一位（,0-9,）；（,2,）浪费时间：一次加减只处理一位；,改进办法：,(1),扩大进制数：考虑用一个数组元素记录,2,位数字、,3,位数字或更多位的数字。（但是要考虑到计算机中的一个数的取值范围，必须保证在运算过程中不会越界）如，一个数组元素存放四位数；这样数组就相当于,10000,进制的数。,(2),建立因子表：,12,2025/4/20 周日,扩大进制数,1,数据类型,int a10000;,string st;,int la,ln;,2,整数数组的建立和输出,当输入数串,st,后，我们从左而右扫描数串,st,以四个数码为一组，将之对应的,10000,进制数据存入数组,n,中。具体方法如下：,13,2025/4/20 周日,扩大进制数（,cont.,）,建立：,scanf(“%s”,st);,K=len(st);,For(i=0;ik;i+),j=(k-i+3)/4-1;,nj=nj*10+sti+1-48;,ln=(k+3)/4;,14,2025/4/20 周日,扩大进制数（,cont.,）,输出：,printf(nln-1);,for(i=ln-2;i=0;i-),printf(“%d%d%d%d”,ni/1000,(ni/100)%10,(ni/10)%10,ni%10);,15,2025/4/20 周日,基本运算,（,1,）整数数组减,1（n=n-1,n,为整数数组,）,从,n0,出发往左扫描，寻找第一个非零的元素（,nj0,nj-1=nj-2=nj-3=n0=0,）。由于该位接受了低位的借位，因此减,1，,其后缀全为,9999。,如果最高位为,0，,则,n,的长度减,1,j=0;,While(nj=0)j+;,nj=nj-1;,for(k=0;k=0lj-),aj=aj+l*1000;,l=aj%i;,aj=ai/i;,While(ala-1=0)la=la-1;,18,2025/4/20 周日,基本算法（两个整数数组相乘）,a=a*n;,按照由高位到低位的顺序，将,a,数组的每一个元素与,n,相乘。当计算到,aj*n,时，根据乘法规则，,aj-1,a0,不变，,aj,为原,aj,与,n0,的乘积，,aj+k,加上,aj*nk,的乘积,(k=ln-1,ln-2,1),然后按照由低位到高位的顺序处理进位。最后，如果,ala-1*n,有进位，则乘积,a,的有效位数为,la+ln;,否则,a,的有效位数为,la+ln-1.,19,2025/4/20 周日,两个整数数组相乘,(cont.),For(j=la-1;j=0;j-),for(k=ln-1;k=1;k-),aj+k=aj+k+aj*nk;,aj=aj*n0;,l-=0;,For(j=0;jla+ln;j+),l=l+aj;,aj=l%10000;,l=l/10000;,If(ala+ln-10),la=la+ln,Else,la=la+ln-1;,20,2025/4/20 周日,