高精度加法的输入及处理方式浅析

赵心龙

摘 要：利用计算机进行数值运算，经常会遇到数值太大的情况，有时又会遇到对运算的精度要求特别高的情况。针对这些情况，都要用“高精度运算”来解决，下面以加法为例简要分析高精度运算的输入及处理方式。

关键词：高精度；数组；字符串

利用计算机进行数值运算，经常会遇到数值太大，超出Longint、int64等系统标准数据类型的有效范围；有时又会遇到对运算的精度要求特别高的情况，如计算圆周率π，要求精确到小数点后100位，此时real、double等数据类型也无能为力了。针对这些情况，就需要用“高精度运算”来解决。

高精度数据的读入可以采用两种方法，一是一位一位读入并存储到数组中；二是采用字符串方式读入，再逐位处理成数字存储在数组中。在实际使用时，按大家习惯可以选择不同的处理方式。高精度运算一般都是采用模拟的方法解决，所以输入时一定要注意按位对齐。

一、采用数组方式读入，按数组进行运算

定义存储数组：var p：array[1..n] of integer；

代码一：read（ch）；

k：=0；

while ch in[‘0..‘9] do //读入数组

begin

inc（k）；

p[k]：=ord（ch）-48；

read（ch）；

end；

read（ch）将数据一位一位读入。k初值为零，且循环过程中递增，p[1]至p[k]依次存储数据的高位至低位。

代码二：for i：=k downto 1 do //处理数组，使数据按位右对齐

begin

p[n+i-k]：=p[i]；

p[i]：=0；

end；

p[n+i-k]：=p[i]将整个数组向后平移，最后一位移至p[n]，第一位移至p[n+1-k]，使参与运算的数据按位右对齐。

代码二在代码一的基础上，经过处理后，两个高精度数低位对齐，符合我们做加法、减法、乘法的运算习惯。

二、采用字符串方式读入，转换成数组运算

定义字符串：var sa，sb：string；数据类型string定义的字符串长度为0-255，如果输入更长的字符串，可以将字符串定义为无限字符串ansistring。

用字符串方式读入两个高精度数，readln（sa）；readln（sb）；

计算出每个字符串的长度，la：=length（sa）； lb：=length（sb）；

代码三： for i：=1 to la do a[i]：=ord（sa[la+1-i]）-48；

for i：=1 to lb do b[i]：=ord（sb[lb+1-i]）-48；

字符‘0的ASSCⅡ码是48，ord（ ）函数的作用是将字符转换成数值，例如输入的字符‘8，通过ord（8）-48可以将字符‘8转换成与之等价的数值，即字符‘8转换成数字8。通过下标的变化a[i]：=ord（sa[la+1-i]）-48，将输入的字符串‘12345转换成数组a，每一位数值存储顺序恰与数组a的下标相反，其中a[1]=5，a[2]=4，a[3]=3，a[4]=2，[5]=1。

以上过程是把两个高精度数逐位处理并转存到a、b两个数组中，数组下标从1开始存储数的低位。这种读入的方法利用了字符串的性质，符合人们读数的习惯，但计算时需要将字符串转换成数组。a[i]：=ord（sa[la+1-i]）-48中sa的下标可以根据自己的习惯灵活处理。

三、采用字符串方式读入，直接进行运算

代码四：

while length（sa）>length（sb）do sb：=‘0+sb；

while length（sb）>length（sa）do sa：=‘0+sa；

比较读入的两个字符串长度，通过在字符串前加‘0的方式将两个字符串长度补齐，其原理是在数的高位添加0而不影响数的大小。在运算处理方面，我们可以通过字符串的下标如sa[i]访问字符串中的单个字符，然后将字符转换成数值进行运算。

高精度运算的首要问题是读入方式和存储方式的转换，方式一时间复杂度O（n）；方式二时间复杂度O（length（s）），如果两个字符串的长度差大，此方式优于方式一；方式三时间复杂度O（|length（sa）-length（sb）|），如果两个字符串的长度差小，此方式优于方式一。虽然方式二、三在某些情形下优于方式一，但与人的逻辑习惯不符，所以这几种方法可以灵活运用。

参考文献：

[1]吴再陵.全国青少年信息学奥林匹克联赛培训教材[M].南京大学出版社，2006.

[2] 狄光智，赵同林.数组实现高精度计算的方法研究[J].电脑编程技巧与维护，2009（10）.

编辑 姚晓媛