高精度算法

 　　一、基本方法：

　　在计算机上进行高精度计算，首先要处理好以下几个基本问题：

　　1、数据的接收与存储；
　　2、计算结果位数的确定；
　　3、进位处理和借位处理；
　　4、商和余数的求法；

　　下面我们逐一介绍一下这几个问题的解决方法。

　　1、数据的接收与存储：

　　要在计算机上进行高精度计算，首先就应该有精确的输入，即计算机要精确地接收和存储数据。通常：

　　①、当输入的数值在计算机允许的范围内时，可以用数值型变量来接收数据。
　　②、当输入的数据超过计算机允许显示的精度范围时，采用字符来接收数据。
　　③、分离各位数字。
　　接收数据子模块(字符型变量接收数据)：

　　　　　　　　　　　　QBASIC
　　　　　　　　　　　　PASCAL

INPUT a$
l=LEN(a$)
DIM a(l) 
FOR i = 1 TO l 
a(i) = VAL(MID$(a$, i, 1)) 
NEXT 
prucedure readdata(var in:array[1..100] of integer); 
var ch:char; 
i,k:integer; 
begin 
read(ch);k:=0; 
while ch in['0'..'9'] do begin 
inc(k);int[k]:=ord(ch)-48; 
read(ch); 
end; 
end;

　　2、计算结果位数的确定

　　①、两数之和的位数最大为较大的数的位数加1。
　　②、乘积的位数最大为两个因子的位数之和。
　　③、阶乘与乘方的位数可以采用对数运算来确定计算结果的位数。

　　3、进位处理和借位处理

　　①、加法的进位处理

　　进行加法处理时，先设置一个加法进位标志 T，并将 T 的初值设为 0。当两数相加时，从低位到高位，各位数字分别相加，如果相加后某个单元中的数大于 10，则将该单元中的数减去10，并将进位标志 T 设为 1，当对下一单元进行相加时，还要再加上前一个单元的进位标志 T。同时将 T 再次置为 0，不断重复，直到最高位为止。具体算法为：

　　　　　　　　　　　　QBASIC 
　　　　　　　　　　　　PASCAL

T=0 
对变量 I 从 1 到 N，重复下列步骤： 
C(I)=A(I)+B(I)+T:T=0 
IF C(I)>=10 THEN C(I)=C(I)-10:T=1 
T:=0; 
对变量 I 从 1 到 N，重复下列步骤： 
C[I]:=A[I]+B[I]+T;T:=0; 
IF C[I]>=10 THEN BEGIN 
C[I]:=C[I]-10;T:=1; 
END;

　　②、乘法的进位处理

　　　　　　　　　　　　QBASIC
　　　　　　　　　　　　PASCAL

Y=A(I)*B(I)+C:C=Y\10:C(I+J-1)=Y-C*10
Y:=A[I]*B[I]+C;C:=Y div 10;C[I+J-1]:=Y-C*10

　　③、减法的借位处理

　　　　　　　　　　　　BASIC
　　　　　　　　　　　　PASCAL 
IF A(I))<B(I) THEN 
A(I+1)=A(I+1)-1 
A(I)=A(I)+10 
END IF 
C(I)=A(I)-B(I) 
IF A[I]B[I] THEN BEGIN
A[I+1]:=A[I+1]-1; 
A[I]:=A[I]+10 
END IF 
C[I]:=A[I]-B[I];

　　4、商和余数的求法

　　设A，B分别为不大于9位的整数，则：

　　　　　　　　　　　　QBASIC
　　　　　　　　　　　　PASCAL

　　C=A\B为商的整数部分
　　X=A MOD B为余数
　　C:=A DIV B为商的整数部分
　　X:=A MOD B为余数

　　二、算法与实例：

　　1、求任意位数的加法运算

　　【问题分析】：

　　①、数据的接收和存储 采用字符串输入的方式，设参与运算的两个数分别为A和B，利用字符串函数把字符串转化为数值，将A、B中的每一位数字分别存储在A、B两个数组中，最低位在第一个单元中。(PASCAL语言中可以直接采用字符读取的方式来接收数据，而后通过ORD(x)-48的方式转化成数值。)

　　②、确定和的位数

　　设LA为A的位数，LB为B的位数，则两数之和的位数最大为较大加数位数加1，即如果LA>LB，则和的位数最大为LA+1。

　　③、进位处理

　　进行加法处理时，先设置一个加法进位标志 T，并将 T 的初值设为 0。当两数相加时，从低位到高位，各位数字分别相加，如果相加后某个单元中的数大于 10，则将该单元中的数减去10，并将进位标志 T 设为 1，当对下一单元进行相加时，还要再加上前一个单元的进位标志 T。同时将 T 再次置为 0，不断重复，直到最高位为止。

　　程序清单：(略)

QBASIC V4.5 语言源程序

Borland PASCAL V7.0 语言源程序

　　2、求任意位数的减法运算

　　①、数据的接收和存储

　　采用字符串输入的方式，设参与运算的两个数分别为A和B，利用字符串函数把字符串转化为数值，将A、B中的每一位数字分别存储在A、B两个数组中，最低位在第一个单元中。(PASCAL语言中可以直接采用字符读取的方式来接收数据，而后通过ORD(x)-48的方式转化成数值。)

　　②、确定差的位数

　　设LA为A的位数，LB为B的位数，则两数之差的位数最大为较大数的位数，即如果LA>LB，则差的位数最大为LA。

　　③、借位处理

　　做减法运算时，要先判断是否需要借位，如果需要借位，从上一位借过一个10，上一位的数减去1，处理完之后再相减。

　　④、负数的处理

　　如果减数大于被减数，则交换A、B的值，并令负数标志 T=-1。当打印计算结果时，先判断 T 的值是否为-1，如果T=-1，则在数值前面先输出一个负号。

　　程序清单：(略)

QBASIC V4.5 语言源程序

Borland PASCAL V7.0 语言源程序

　　3、求任意位数的乘法运算

　　①、数据的接收和存储

　　采用字符串输入的方式，设参与运算的两个数分别为A和B，利用字符串函数把字符串转化为数值，将A、B中的每一位数字分别存储在A、B两个数组中，最低位在第一个单元中。(PASCAL语言中可以直接采用字符读取的方式来接收数据，而后通过ORD(x)-48的方式转化成数值。)

　　②、确定积的位数

　　设LA为A的位数，LB为B的位数，乘积的位数最多为LA+LB，最少为LA+LB-1。所以，乘积的位数上限为LA+LB。

　　③、算法

　　首先计算被乘数与乘数的个位数字的乘积，把结果保存到积数组中，然后再用被乘数去乘以乘数的十位数字，把结果退一位加到积数组中。每加一次乘积结果就进行一次进位处理，其方法与加法中的进位处理一样。

　　程序清单：(略)

QBASIC V4.5 语言源程序

Borland PASCAL V7.0 语言源程序

　　4、求A÷B的精确值

　　由于A和B都是计算机允许的显示精度，故A、B均可使用数值变量来接收与存储。A÷B的精确值有两种情况：

　　①、A能被B整除，没有余数。
　　②、A不能被B整除，对余数进行处理。首先，我们知道，在做除法运算时，有一个不变的量和三个变化的量，不变的量是除数，三个变化的量分别是：被除数、商和余数。做除法运算时，每次都是用被除数减去商与除数的积，如果所得余数不为零，则将其扩大10倍再次作为被除数，继续试除，直至余数为零或达到要求的精确度为止。最后，必须对精确度的后一位求商，然后判断其值而四舍五入得出最后的结果。

　　程序清单：(略)

QBASIC V4.5 语言源程序

Borland PASCAL V7.0 语言源程序

　　5、求多精度A÷单精度B的商和余数。

　　①、数据的接收和存储

　　采用字符串输入的方式，设参与运算的两个数分别为A和B，利用字符串函数把字符串转化为数值，将A中的每一位数字分别存储在A数组中，最低位在第一个单元中。(PASCAL语言中可以直接采用字符读取的方式来接收数据，而后通过ORD(x)-48的方式转化成数值。)。B则可以用一般的整数变量来接收和存储。

　　②、算法

　　首先，我们知道，在做除法运算时，有一个不变的量和三个变化的量，不变的量是除数，三个变化的量分别是：被除数、商和余数。做除法运算时，每次都是用被除数减去商与除数的积，如果所得余数不为零，则将其扩大10倍再次作为被除数，继续试除，直至余数为零或达到要求的精确度为止。

　　程序清单：(略)

QBASIC V4.5 语言源程序

Borland PASCAL V7.0 语言源程序

　　6、5、求多精度A÷多精度B的商和余数。

　　①、数据的接收和存储

　　采用字符串输入的方式，设参与运算的两个数分别为A和B，利用字符串函数把字符串转化为数值，将A、B中的每一位数字分别存储在A和B数组中，最低位在第一个单元中。(PASCAL语言中可以直接采用字符读取的方式来接收数据，而后通过ORD(x)-48的方式转化成数值。)。

　　②、算法

　　可以用减法代替除法运算：不断比较A[1..n]与B[1..n]的大小，如果A[1..n]>=B[1..n]则商C[1..n]+1→C[1..n]，然后就是一个减法过程：A[1..n]-B[1..n]→A[1..n]。由于简单的减法速度太慢，故必须进行优化。设置一个位置值J，当A[1..n]>B[1..n]时。B[1..n]左移→B[0..n]，j:=j+1，即令B[1..n]增大10倍。这样就减少了减法的次数。当j>0且A[1..n]<B[0..n]时，B[0..n]右移→B[0..n]，j=j-1，即令B[1..n]缩小10倍。