高精度计算
朴素高精度
由于待处理的数据超过了任何一种数据类型所能容纳的范围,因此必须采用数串形式输入,并将其转化为数组。该数组的每一个元素对应一个十进制数,由其下标顺序指明位序号。由于高精度运算可能使得数据长度发生变化,因此除要用整数数组存储数据外,还需要一个整数变量纪录整数数组的元素个数,即数据的实际长度。
type
numtype=array[1..255] of integer;
var
a:numtype;
la:byte;
s:string;
begin
readln(s);
la:=length(s);
for i:=1 to la do
a[la-i+1]:=ord(s[i])-ord('0');
end.
高精度加法运算
首先,确定a和b中的最大位数x,然后依照由低位至高位的顺序进行加法运算。在每一次运算中,a当前位加b当前位的和除以10,其整商即为进位,其余数即为和的当前位。在进行了x位的加法后,若最高位有进位(a[x+1]<>0),则a的长度为x+1。
以下只列出关键程序:
type
numtype=array[1..255] of longint;
var
a,b,s:numtype;
la,lb,ls:longint;
procedure plus(var a:numtype;var la:longint;b:numtype;lb:longint); {利用过程实现}
var
i,x:longint;
begin
if la>=lb
then x:=la
else x:=lb;
for i:=1 to x do
begin
a[i]:=a[i]+b[i];
a[i+1]:=a[i+1]+a[i] div 10;
a[i]:=a[i] mod 10;
end;
while a[x+1]<>0 do
x:=x+1;
la:=x; {最高位若有进位,则长度增加}
end;
高精度减法运算(a>b)
依照由低位至高位的顺序进行减法运算。在每一次位运算中,若出现不够减的情况,则向高位借位。在进行了la位的减法后,若最高位为零,则a的长度减1(一位一位测试,直到确切长度)。
以下只列出关键程序:
type
numtype=array[1..255] of longint;
var
a,b:numtype;
la,lb: longint;
procedure minus(var a:numtype;var la: longint;b:numtype;);
var
i:word;
begin
for i:=1 to la do
begin
if a[i]
then begin
dec(a[i+1]);
a[i]:=a[i]+10;
end;
a[i]:=a[i]-b[i];
end;
while (a[la]=0) and (la>1) do
dec(la);
end;
高精度乘法运算
按照乘法规则,从a的第1位开始逐位与c(c为字节型)相乘。在第i位乘法运算中,a的i位与c的乘积必须加上i-1位的进位,然后规整积的i-1位。
以下只列出关键程序:其中C为小于10的整数,如果不是小于10的整数,则按位分解该数。type
numtype=array[1..1000] of word;
var
a:numtype;
la:word;
procedure multiply(var a:numtype;var la:word;c:word);
var
i:word;
begin
a[1]:=a[1]*c;
for i:=2 to la do
begin
a[i]:=a[i]*c;
a[i]:=a[i]+a[i-1] div 10;
a[i-1]:=a[i-1] mod 10;
end;
while a[la]>=10 do
begin
inc(la);
a[la]:=a[la-1] div 10;
a[la-1]:=a[la-1] mod 10;
end;
end;
压位高精度
扩大进制数改善高精度运算效率
朴素高精度采用1位一存的朴素方法,那为什么不能充分利用已经很快的longint计算呢?要知道,算 1+1=2 和 10+10=20 时间上不会差很多的!
把数字看成 10000 位数字用 longint 存
把数字看成 100000000位数字用 int64 存
把数字看成 2^k 位数字采用位运算快速运算
用整数数组每一个元素表示一个十进制整数的方法存在的缺点是:如果十进制的位数很多,则对应的数组的长度会很长,并增加了高精度计算的时间。
如果用一个元素记录2位数字、3位数字或更多位数字,则数组的长度可以明显缩小,但是还要考虑数的取值范围问题,必须保证程序运行过程中不越界。在权衡了两方面的情况后得出:用一个longint记录4位数字是最佳的方案。那么这个数组就相当于一个10000进制的数,其中每一个元素都是10000进制下的一位数。
一、数据类型定义:
type
numtype=array[1..10000] of longint; {可以存储40000位十进制数}
var
a,n:numtype;
la,ln:byte;
s:ansistring; {任意长度的字符串类型}
二、整数数组的建立和输出
readln(s);
k:=length(s);
for i:=1 to k do
begin
j:=(k-i+4) div 4;
n[j]:=n[j]*10+ord(s[i])-48;
end;
ln:=(k+3) div 4;
当得出最后结果n后,必须按照次高位到最低位的顺序,将每一位元素由10000进制数转换成十进制数,即必须保证每个元素对应4位十进制数。例如n[i]=0015(0<=i<=ln-2),对应的十进制数不能为15,否则会导致错误结果。可以按照如下方法输出n对应的十进制数:
write(n[ln]);
for i:=ln-1 downto 1 do
write(n[i] div 1000,(n[i] div 100) mod 10,(n[i] div 10) mod 10,n[i] mod 10);
三、基本运算
两个10000进制整数的加法和减法与前面的十进制运算方法类似,只是进制变成了10000进制。
1、整数数组减1(n:=n-1,n为整数数组)
从n[1]出发寻找第一个非零的元素,由于接受了低位的借位,因此减1,其后缀全为9999。如果最高位为0,则n的长度减1。
j:=1;
while (n[j]=0) do inc(j); {寻找第一个非零的元素}
dec(n[j]); {该位接受低位的借位,因此减1}
for i:=1 to j-1 do
n[i]:=9999; {其后缀全为9999}
if (j=ln) and (n[j]=0) {如果最高位为0,则n的长度减1}
then dec(ln);
2、整数数组除以整数(a:=a div i,a为整数数组,i为整数)
按照从高位到低位的顺序,逐位相除,把余数乘进制后加到下一位继续相除。如果最高位为0,则a的长度减1。
l:=0;
for j:=la downto 1 do
begin
inc(a[j],l*10000);
l:=a[j] mod i;
a[j]:=a[j] div i;
end;
while a[la]=0 do dec(la);
3、两个整数数组相乘(a:=a*n,a和n为整数数组)
按照从高位到低位的顺序,将数组a的每一个元素与n相乘。
procedure multiply(a,b:numtype;la,lb:longint;var s:numtype;var ls:longint); var
i,j:longint;
begin
for i:=1 to la do
for j:=1 to lb do
s[i+j-1]:=s[i+j-1]+a[i]*b[j];
for i:=1 to la+lb-1 do
begin
s[i+1]:=s[i+1]+s[i] div 10000;
s[i]:=s[i] mod 10000;
end;
if s[la+lb]=0
then ls:=la+lb-1
else ls:=la+lb;
end;
2.计算结果位数确定
用数学方法确定。利用对数函数(ln)。
3.进位与借位处理
加法:if a[i]>10 then begin a[i]=a[i]-10 ; a[i+1]=a[i+1]+1
减法:if a[i]
4.商与余数处理
除法:商=A DIV B, 余数=A MOD B
运算符重载
Operator 运算符 ( a , b : 数据类型) :数据类型
Overload 可加可不加
顺带提一下 Overload 的妙用
Procedure Swap ( var a , b : longint);
Procedure Swap ( var a , b : hp); overload;
可以用同样的过程名表示不同的过程
自定义高精度类型 type hp=array [0..1000] of longint 数字位数用 a[0] 贮存
如果需要符号位用 a[-1] 贮存
Operator +(a,b:HP)c:HP;
Var i,l:longint;
Begin
if a[0]>b[0] then l:=a[0] else l:=b[0];
fillchar(c,sizeof(c),0);
For i:= 1 to l do
Begin
inc(c[i],(a[i]+b[i]) Mod KM);
c[i+1]:=(a[i]+b[i]) Div KM;
End;
if c[l+1]<>0 then inc(l); c[0]:=l;
End;
Operator *(a,b:HP)c:HP;
Var i,j,l:longint;
Begin
fillchar(c,sizeof(c),0);
For i:= 1 to a[0] do
For j:= 1 to b[0] do
Begin
inc(c[i+j-1],a[i]*b[j]);
inc(c[i+j],c[i+j-1] Div KM);
c[i+j-1]:=c[i+j-1] Mod KM;
End;
l:=a[0]+b[0]+1;
while (l>1) and (c[l]=0) do dec(l); c[0]:=l; End;
Operator *(a:HP; b:longint)c:HP;
Var i,j,l:longint;
Begin
fillchar(c,sizeof(c),0);
For i:= 1 to a[0] do
Begin
inc(c[i],a[i]*b);
c[i+1]:= c[i] div KM;
c[i]:=c[i] mod KM;
End;
l:=a[0]; if c[l+1]<>0 then inc(l);
while c[l]>KM do
begin
c[l+1]:=c[l] div KM;
c[l]:=c[l] mod KM;
inc(l);
end;
c[0]:=l;
End;
Operator /(a:HP; b:longint)c:HP;
Var //d:longint;
i,l:longint;
Begin
l:=a[0]; d:=0; fillchar(c,sizeof(c),0);
For i:= l downto 1 do
Begin
d:=d*KM+a[i];
c[i]:= d div b;
d:= d mod b;
End;
While (L>1) and (c[l]=0) do dec(l); c[0]:=l; End;
Operator >(a,b:HP)c:boolean;
var i:longint;
begin
if a[0]>b[0] then exit(true) else
if a[0]
for i:= a[0] downto 1 do
if a[i]>b[i] then exit(true) else
if a[i]
exit(false);
end;
练习题:用高精度计算出s=1!+2!+3!+ (100)
program jiecheng;
type
numtype=array[1..255] of longint;
var
s,t:numtype;
ls,lt,i:longint;
procedure plus(var a:numtype;var la:longint;b:numtype;lb:longint); var
i,x:byte;
begin
if la>=lb
then x:=la
else x:=lb;
for i:=1 to x do
begin
a[i]:=a[i]+b[i];
a[i+1]:=a[i+1]+a[i] div 10000;
a[i]:=a[i] mod 10000;
end;
while a[x+1]<>0 do
x:=x+1;
la:=x;
end;
procedure multiply(var a:numtype;var la:longint;c:longint);
var
i:longint;
begin
a[1]:=a[1]*c;
for i:=2 to la do
begin
a[i]:=a[i]*c;
a[i]:=a[i]+a[i-1] div 10000;
a[i-1]:=a[i-1] mod 10000;
end;
while a[la]>=10000 do
begin
inc(la);
a[la]:=a[la-1] div 10000;
a[la-1]:=a[la-1] mod 10000;
end;
end;
begin
lt:=1;
t[1]:=1;
ls:=0;
for i:=1 to 100 do
begin
multiply(t,lt,i);
plus(s,ls,t,lt);
end;
write(s[ls]);
for i:=ls-1 downto 1 do
write(s[i] div 1000,(s[i] div 100) mod 10,(s[i] div 10) mod 10,s[i] mod 10); writeln;
writeln;
end.
保留100位有效数字
【题目描述】
输入任意两个整数a,b(a,b均在长整型范围内),计算a/b的结果,保留100位有效数字,最后一位要求四舍五入。
【输入格式】
两个数a,b
【输出格式】
a/b的商,保留100位有效数字
【输入样例】
129 13
【输出样例】
9.923076923076923076923076923076923076923076923076923076923076923076923076923076923 076923076923076923
【解题思路】
保留100位有效数字不代表保留100位小数。比如说,商的整数部分为5位数,则只应算到小数点后第95位;而如果商的第1个有效数字从万分位开始,则应算到小数点后第103位。
program project11;
var
a:extended;
begin
read(a,b);
c:=a div b;
r:=a mod b;
if c=0
then lc:=0
else begin
str(c,s);
lc:=length(s);
end;
write(c,'.');
for i:=1 to 100-lc do begin
j:=i;
r:=r*10;
if r<>0
then while r
begin
r:=r*10;
x[i]:=0;
j:=i+1;
end;
c:=r div b;
x[j]:=c;
r:=r mod b;
end;
for i:=1 to 100-lc do write(x[i]);
end.
高精度计算 由于计算机具有运算速度快,计算精度高的特点,许多过去由人来完成的烦琐、复杂的数学计算,现在都可以由计算机来代替。 计算机计算结果的精度,通常要受到计算机硬件环境的限制。例如,pascal 要计算的数字超过19位,计算机将按浮点形式输出;另一方面,计算机又有数的表示范围的限制,在一般的微型计算机上,实数的表示范围为l0-38 -l038。例如,在计算N!时,当N=21时计算结果就超过了这个范围,无法计算了。这是由计算机的硬件性质决定的,但是,我们可以通过程序设计的方法进行高精度计算(多位数计算)。 学习重点 1、掌握高精度加、减、乘、除法。 3、理解高精度除法运算中被除数、除数、商和余数之间的关系。 4、能编写相应的程序,解决生活中高精度问题。 学习过程 一、高精度计算的基本方法 用free pascal程序进行高精度计算,首先要处理好以下几个基本问题:【数据的输入与保存】 (1)一般采用字符串变量存储数据,然后用length函数测量字符串长度确定其位数。 (2)分离各位数位上的数字 分离各数位上的数通常采用正向存储的方法。以“163848192”为例,见下表:A[9] A[8] A[7] A[6] A[5] A[4] A[3] A[2] A[1] 1 6 3 8 4 8 1 9 2 基本原理是A[1]存放个位上的数字,A[2]存放十位上的数字,……依此类推。即下标小的元素存低位上的数字,下标大的元素存高位上的数字,这叫“下标与位权一致”原则。 【计算结果位数的确定】 (1)高精度加法:和的位数为两个加数中较大数的位数+1。 (2)高精度减法:差的位数为被减数和减数中较大数的位数。 (3)高精度乘法:积的位数为两个相乘的数的位数之和。 (4)高精度除法:商的位数按题目的要求确定。 【计算顺序与结果的输出】 高精度加、减、乘法,都是从低位到高位算起,而除法相反。输出结果都是从高位到低位的顺序,注意:高位上的零不输出(整数部分是零除外)。 高精度加法 【参考程序】 var a,b:array[1..10000] of byte; i,w,la,lb:integer;