荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: OneSecond (别问我是谁), 信区: ACMICPC
标 题: 高精度 --nju huhaiming
发信站: 荔园晨风BBS站 (Fri Jul 30 20:36:15 2004), 站内信件
发信人: huhaiming (一生只爱她), 信区: Program
标 题: 高精度 --nju
发信站: 荔园晨风BBS站 (Sun May 11 11:30:50 2003), 转信
高精度计算
由于计算机输入计算结果的精度通常受到计算机的限制，如：在双精度方式下，计算机最
多只能输出16位有效数字，如果超过16位，则只能按浮点形式输出，另外，一般计算机实
数表示的范围为1038，如果超过这个范围，计算机就无法表示了。但是我们可以通过一些
简单的办法来解决这个问题。这就是我们要说的高精度计算机。
一、 基本方法：
在计算机上进行高精度计算，首先要处理好以下几个基本问题：
1、 数据的接收与存储；
2、 计算结果位数的确定；
3、 进位处理和借位处理；
4、 商和余数的求法；
下面我们逐一介绍一下这几个问题的解决方法。
1. 数据的接收与存储：
要在计算机上进行高精度计算，首先就应该有精确的输入，即计算机要精确地接收和存储
数据。通常：
①、当输入的数值在计算机允许的范围内时，可以用数值型变量来接收数据。
②、当输入的数据超过计算机允许显示的精度范围时，采用字符来接收数据。
③、分离各位数字。
接收数据子模块(字符型变量接收数据)：
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，不断重复，直到最高位为止。具体算法为：
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;
②、 乘法的进位处理
Y:=A[I]*B[I]+C;C:=Y div 10;C[I+J-1]:=Y-C*10
③、 减法的借位处理
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];
④、 商和余数的求法
设A，B分别为不大于9位的整数，则：
C:=A DIV B为商的整数部分
X:=A MOD B为余数
二、 算法与实例：
1. 求任意位数的加法运算
数据的接收和存储
采用字符串输入的方式，设参与运算的两个数分别为A和B，利用字符串函数把字符串转化
为数值，将A、B中的每一位数字分别存储在A、B两个数组中，最低位在第一个单元中。(P
ASCAL语言中可以直接采用字符读取的方式来接收数据，而后通过ORD(x)-48的方式转化成
数值。)
确定和的位数
设LA为A的位数，LB为B的位数，则两数之和的位数最大为较大加数位数加1，即如果LA>LB
，则和的位数最大为LA+1。
进位处理
进行加法处理时，先设置一个加法进位标志 T，并将 T 的初值设为 0。当两数相加时，从
低位到高位，各位数字分别相加，如果相加后某个单元中的数大于 10，则将该单元中的数
减去10，并将进位标志 T 设为 1，当对下一单元进行相加时，还要再加上前一个单元的进
位标志 T。同时将 T 再次置为 0，不断重复，直到最高位为止。
程序清单：
program gjdjs;
const n=100;
type arrtype=array[1..n] of integer;
var
a,b:arrtype;
t,s,j,l:integer;
procedure readdata(var int:arrtype);
var
ch:char;
i,k:integer;
begin
writeln('Input a number:');
read(ch);k:=0;
while ch in['0'..'9'] do begin
inc(k);
int[k]:=ord(ch)-48;
read(ch);
end;
for i:=k downto 1 do begin
int[n+i-k]:=int[i];
int[i]:=0;
end;
end;
begin
readdata(a);readln;
readdata(b);writeln;
t:=0;
for j:=n downto 1 do begin
s:=a[j]+b[j]+t;
a[j]:=s mod 10;
t:=s div 10;
end;
j:=1;writeln('output:');
while a[j]=0 do j:=j+1;
while j<=n do begin
write(a[j]);
inc(j);
end;
writeln;
end.
2. 求任意位数的减法运算
数据的接收和存储
采用字符串输入的方式，设参与运算的两个数分别为A和B，利用字符串函数把字符串
转化为数值，将A、B中的每一位数字分别存储在A、B两个数组中，最低位在第一个单元中
。(PASCAL语言中可以直接采用字符读取的方式来接收数据，而后通过ORD(x)-48的方式转
化成数值。)
确定差的位数
设LA为A的位数，LB为B的位数，则两数之差的位数最大为较大数的位数，即如果LA>L
B，则差的位数最大为LA。
借位处理
做减法运算时，要先判断是否需要借位，如果需要借位，从上一位借过一个10，上一
位的数减去1，处理完之后再相减。
负数的处理
如果减数大于被减数，则交换A、B的值，并令负数标志 T=-1。当打印计算结果时，先
判断 T 的值是否为-1，如果T=-1，则在数值前面先输出一个负号。
程序清单：
program gjdjs;
const n=100;
type arrtype=array[1..n] of integer;
var
a,b:arrtype;
g,t,j,l:integer;
s:char;
f:boolean;
procedure readdata(var int:arrtype);
var
ch:char;
i,k:integer;
begin
writeln('Input a number:');
read(ch);k:=0;
while ch in['0'..'9'] do begin
inc(k);
int[k]:=ord(ch)-48;
read(ch);
end;
for i:=k downto 1 do begin
int[n+i-k]:=int[i];
int[i]:=0;
end;
end;
begin
readdata(a);readln;
readdata(b);writeln;
f:=true;j:=1;
while (a[j]=b[j]) and (j<n) do j:=j+1;
if a[j]<b[j] then f:=false;
if f then s:=' ' else begin
s:='-';
for l:=1 to n do begin
t:=a[l];a[l]:=b[l];b[l]:=t;
end;
end;
t:=0;
for j:=n downto 1 do
if a[j]>=b[j]+g then begin
a[j]:=a[j]-b[j]-g;
g:=0;
end
else begin
a[j]:=10+a[j]-b[j]-g;
g:=1;
end;
j:=1;writeln('output:');write(s);
while (a[j]=0) and (j<n) do j:=j+1;
while j<=n do begin
write(a[j]);
inc(j);
end;
writeln;
end.
3. 求任意位数的乘法运算
数据的接收和存储
采用字符串输入的方式，设参与运算的两个数分别为A和B，利用字符串函数把字符串
转化为数值，将A、B中的每一位数字分别存储在A、B两个数组中，最低位在第一个单元中
。(PASCAL语言中可以直接采用字符读取的方式来接收数据，而后通过ORD(x)-48的方式转
化成数值。)
确定积的位数
设LA为A的位数，LB为B的位数，乘积的位数最多为LA+LB，最少为LA+LB-1。所以，乘
积的位数上限为LA+LB。
算法
首先计算被乘数与乘数的个位数字的乘积，把结果保存到积数组中，然后再用被乘数
去乘以乘数的十位数字，把结果退一位加到积数组中。每加一次乘积结果就进行一次进位
处理，其方法与加法中的进位处理一样。
程序清单：
program gjdcs;
const n=100;
type arrtype=array[0..n] of integer;
arrtype2=array[1..2*n] of integer;
var
a,b,d:arrtype;
c:arrtype2;
g,i,j,s:integer;
procedure readdata(var int:arrtype);
var
ch:char;
i,k:integer;
begin
writeln('Input a number:');
read(ch);k:=0;
while ch in['0'..'9'] do begin
inc(k);
int[k]:=ord(ch)-48;
read(ch);
end;
for i:=k downto 1 do begin
int[n+i-k]:=int[i];
int[i]:=0;
end;
end;
begin
readdata(a);readln;
readdata(b);writeln;
for i:=n downto 1 do begin
g:=0;
for j:=n downto 1 do begin
s:=a[j]*b[i]+g;
d[j]:=s mod 10;
g:=s div 10;
end;
d[0]:=s;
g:=0;
for j:=n downto 0 do begin
s:=d[j]+c[i+j]+g;
c[i+j]:=s mod 10;
g:=s div 10
end;
end;
j:=1;writeln('output:');
while (c[j]=0) and (j<2*n) do j:=j+1;
while j<=2*n do begin
write(c[j]);
inc(j);
end;
writeln;
end.
4. 求A÷B的精确值
算法
由于A和B都是计算机允许的显示精度，故A、B均可使用数值变量来接收与存储。A÷B的精
确值有两种情况：
①、 A能被B整除，没有余数。
②、 A不能被B整除，对余数进行处理。
首先我们知道，在做除法运算时，有一个不变的量和三个变化的量，不变的量是除数，三
个变化的量分别是：被除数、商和余数。做除法运算时，每次都是用被除数减去商与除数
的积，如果所得余数不为零，则将其扩大10倍再次作为被除数，继续试除，直至余数为零
或达到要求的精确度为止。最后，必须对精确度的后一位求商，然后判断其值而四舍五入
得出最后的结果。
程序清单：
program jqdcf;
const n=100;
type arrtype=array[0..n] of integer;
var
a,b,c:arrtype;
i,j,k,l,m:integer;
begin
write('Input a number:');readln(m);
write('Input a number:');readln(k);
write('Input a accuracy:');readln(l);
write(m,'/',k,'=');
a[0]:=m;
b[0]:=m div k;
c[0]:=m mod k;
if c[0]=0 then write(b[0])
else begin
for i:=1 to l+1 do begin
a[i]:=c[i-1]*10;
b[i]:=a[i] div k;
c[i]:=a[i] mod k;
if c[i]=0 then i:=l+1;
end;
if b[l+1]>4 then b[l]:=b[l]+1;
for i:=l downto 1 do
if b[i]>=10 then begin
b[i]:=b[i]-10;
b[i-1]:=b[i-1]+1;
end
else
i:=1;
write(b[0],'.');
for i:=1 to l do write(b[i]);
end;
readln;
end.
5. 求多精度A÷单精度B的商和余数。
数据的接收和存储
采用字符串输入的方式，设参与运算的两个数分别为A和B，利用字符串函数把字符串转化
为数值，将A中的每一位数字分别存储在A数组中，最低位在第一个单元中。(PASCAL语言中
可以直接采用字符读取的方式来接收数据，而后通过ORD(x)-48的方式转化成数值。)。B则
可以用一般的整数变量来接收和存储。
算法
首先，我们知道，在做除法运算时，有一个不变的量和三个变化的量，不变的量是除数，
三个变化的量分别是：被除数、商和余数。做除法运算时，每次都是用被除数减去商与除
数的积，如果所得余数不为零，则将其扩大10倍再次作为被除数，继续试除，直至余数为
零或达到要求的精确度为止。
程序清单：
program gjdcydjd;
const n=100;
type arrtype=array[0..n] of integer;
var
a:arrtype;
g,b,i,j,s:integer;
procedure readdata(var int:arrtype);
var
ch:char;
i,k:integer;
begin
write('Input a number:');
read(ch);k:=0;
while ch in['0'..'9'] do begin
inc(k);
int[k]:=ord(ch)-48;
read(ch);
end;
for i:=k downto 1 do begin
int[n+i-k]:=int[i];
int[i]:=0;
end;
end;
begin
readdata(a);writeln;
write('Input the numbr b:');
readln(b);writeln;
g:=0;
for i:=1 to n do begin
s:=a[i]+g*10;
a[i]:=s div b;
g:=s mod b;
end;
j:=1;writeln('output:');
while (a[j]=0) and (j<n) do j:=j+1;
while j<=n do begin
write(a[j]);
inc(j);
end;
if g<>0 then writeln('......',g);
writeln;
end.
6. 求多精度A÷多精度B的商和余数。
数据的接收和存储
采用字符串输入的方式，设参与运算的两个数分别为A和B，利用字符串函数把字符串转化
为数值，将A、B中的每一位数字分别存储在A和B数组中，最低位在第一个单元中。(PASCA
L语言中可以直接采用字符读取的方式来接收数据，而后通过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倍。
程序清单：
program gjdcygjd;
const n=100;
type arrtype=array[1..n] of integer;
var
a,b,c:arrtype;
g,s,i,j,k,l:integer;
procedure readdata(var int:arrtype);
var
ch:char;
i,k:integer;
begin
write('Input a number:');
read(ch);k:=0;
while ch in['0'..'9'] do begin
inc(k);
int[k]:=ord(ch)-48;
read(ch);
end;
for i:=k downto 1 do begin
int[n+i-k]:=int[i];
int[i]:=0;
end;
end;
function f(a,b:arrtype):boolean;
var j:integer;
begin
f:=true;j:=1;
while (a[j]=b[j]) and (j<n) do j:=j+1;
if a[j]<b[j] then f:=false
end;
procedure sub;
var
i:integer;
begin
g:=0;
for i:=n downto 1 do
if a[i]>=b[i]+g then
begin
a[i]:=a[i]-b[i]-g;
g:=0;
end
else
begin
a[i]:=10+a[i]-b[i]-g;
g:=1;
end;
end;
procedure ine(n:integer);
var i,s:integer;
begin
g:=0;
c[n]:=c[n]+1;
for i:=n downto 1 do begin
s:=c[i]+g;
c[i]:=s mod 10;
g:=s div 10;
end;
end;
begin
readdata(a);readln;
readdata(b);writeln;
j:=1;
while f(a,b) do begin
j:=j+1;
for i:=2 to n do b[i-1]:=b[i];
b[n]:=0;
end;
while j>0 do begin
while f(a,b) do begin
ine(n-j+1);
sub;
end;
j:=j-1;
for i:=n downto 2 do begin
b[i]:=b[i-1];
b[i-1]:=0;
end;
end;
j:=1;writeln('output:');
while (c[j]=0) and (j<n) do j:=j+1;
while j<=n do begin
write(c[j]);
inc(j);
end;
j:=1;
while (a[j]=0) and (j<=n) do j:=j+1;
if j<=n then write('......');
while j<=n do begin
write(a[j]);
inc(j);
end;
writeln;
end.
--
※ 修改:·huhaiming 於 May 11 11:34:19 修改本文·[FROM: 192.168.0.200]
※ 转载:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.0.200]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店