数组型高精度数详解

《数组型高精度数详解》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数组型高精度数详解ByNettle2009-9-9数组型高精度数详解ByNettle第14页共14页数组型高精度数详解ByNettle2009-9-9一、高精度简介二、高精度数三、高精度数与整型的运算四、高精度数与高精度数的运算五、高精度数的进制转换六、高精度幂运算七、压位高精度数一、高精度简介首先要知道在计算机里面每一种数据类型都有自己的存储量。由于存储量的限制所以都有着各自的精度，下面是一些常用数据类型的精度：以Pascal为例整型的精度就是在该类型范围内所有的数。整型范围Shortint-128…127Intege

2、r-32768…32767Longint-2147483648…2147483647Int64-9223372036854775808…9223372036854775807Byte0…255Word0…65535Longword0…4294967295Qword0…18446744073709551615实型的精度是指当该类型的数据位数超过精度范围时自动对超过的部分进行四舍五入。比如将1234567890123存入real时就会变为1.234568E12，后面的890123被四舍五入，只保留了位数。实型范围精度real

3、2.9E-39…1.7E3811至12single1.5E-45…3.4E387至8double5.0E-324…1.7E30815至16但是在某些计算中，参与运算的数的范围大大超出了标准数据类型（整型，实型）能表示的范围的运算，例如求两个100位数的和的精确值。如果用一个整型变量，无论如何也是存储不了的，用实型则会造成数据的不精确。　　于是，我们想到了办法，将这个数字拆开，拆成一位一位的或者是四位四位的存储到一个数组中，用一个数组去表示一个数字，这样表示的数字就被称为高精度数。　　对于高精度数，也要像平常数一样做加减乘

4、除以及乘方的运算，于是就有了高精度算法。第14页共14页数组型高精度数详解ByNettle2009-9-9二、高精度数[高精度数的定义]高精度数事实上就是一个整型数组，根据题目中用的数据的位数设定数组的大小。为了方便通常将高精度数创建为一个新类型，如下：C++Pascaltypedefinthp[250];typehp=array[0..250]ofinteger;此时hpa或a:hp就表示a为hp类型即大小为250的int数组。在本文中a[0]将存储高精度数的位数，而从a[1]到a[a[0]]分别从低位到高位存储高精度

5、数的每一位数（这样每当一位超过9时，会向前一进位的高精度数，为十进制高精度数）。未使用的部分均为0。例如将123456789012存入a中为数组下标012345678910111213…存储数据1221098765432100则a表示一个12位数，从右至左分别为210987654321。[高精度数的读入]高精度数一般采用字符串的方式，也可以采用字符的方式（以回车符作为结束的标志）。非读入型的高精度数，同常赋值为a[0]=a[1]=1（多用于乘法）或a[0]=1,a[1]=0（多用于加减）下面为字符串式的读入（十进制）：字

6、符串，特别说明C++里字符串以下标0开始，Pascal以1开始。C++PascalvoidInit(hp&a){strings;intl;memset(a,0,sizeof(a));//清零cin>>s;l=s.size();//得到数的位数for(inti=l;i>=1;i--)a[i]=s[l-i]-'0';a[0]=l;return;}procedureInit(vara:hp);vars:string;l,i:integer;beginfillchar(a,sizeof(a),0);//清零readln(s);l

7、=length(s);fori:=ldownto1doa[i]:=ord(s[l–i+1])–ord('0');a[0]:=l;end;[高精度进位]当a[i]上的数据大于等于10的时候，就要向高位进位了。因为该数组中下标越大，位数越高，故对a[i]位进行进位的操作为：第14页共14页数组型高精度数详解ByNettle2009-9-9C++Pascala[i+1]=a[i]/10;a[i+1]:=a[i]div10;a[i]%=10a[i]:=a[i]mod10;如果a[a[0]]位也大于等于10，在进位的同时就要考虑a

8、[0]的值的改变了。本文的处理方式是先估计a[0]能改变的最大值，再依次减小，直到达到准确位数。C++Pascall=a[0]+MAX;while(a[l]==0&&l>1)l--;a[0]=l;l:=a[0]+MAX;while(a[l]=0andl>1)dodec(l);a[0]:=l;[高精度退位]当a[i]上