8高精度运算

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