高精度算法大全

高精度算法大全

在一般的科学计算中,会经常算到小数点后几百位或者更多,当然也可能是几千亿几百亿的大数字.

一般这类数字我们统称为高精度数,高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除,乘方,阶乘,开放等运算.

譬如一个很大的数字N >= 10^ 100, 很显然这样的数字无法在计算机中正常存储.

于是, 我们想到了办法,将这个数字拆开,拆成一位一位的 或者是四位四位的存储到一个数组中, 用一个数组去表示一个数字.这样这个数字就被称谓是高精度数.

对于高精度数,也要像平常数一样做加减乘除以及乘方的运算,于是就有了高精度算法:

由于计算机输入计算结果的精度通常受到计算机的限制，如：在双精度方式下，计算机最多只能输出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。

②、乘积的位数最大为两个因子的位数之和。

③、阶乘：lgn!=lgn+lg(n-1)+lg(n-2)...................+lg3+lg2+lg1

=lnn/ln10+ln(n-1)/ln10+ln(n-2)/ln10+................+ln3/ln10+ln2/ln10+ln1/ln10

=trunc(1/ln10* (lnn+ln(n-1)+ln(n-2)+...........+ln3+ln2+ln1) )

乘方：lg(a ^b)=trunc(lg(a^b))+1

=trunc(b*lg a )+1

=trunc(b*ln a / ln10)+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] A[I+1]:=A[I+1]-1;

A[i]:=A[i]+10

END IF

C[i]:=A[i]-B[i];

4、商和余数的求法

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

C:=A DIV B为商的整数部分

X:=A MOD B为余数

二、算法与实例：

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

【问题分析】：

①、数据的接收和存储

采用字符串输入的方式，设参与运算的两个数分别为A和B，利用字符串函数把字符串转

化为数值，将A、B中的每一位数字分别存储在A、B两个数组中，最低位在第一个单元中。(PA

SCAL语言中可以直接采用字符读取的方式来接收数据，而后通过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．从键盘上读入两个100位长的正实数，编程求出它们的和。

[分析]：与上例不同，我们这次考要考虑的是实数问题，即小数点的问题，我们按照小学数学中的带小数的数的加法规则，应该先对齐小数点，然后实施加法，所以可以先对齐小数点，然后删除小数点实施整数加法，最后还原小数点。

对于最后的结果，还要进行规格化：小数最后的零应该省去。

这里我们用逐步求精的方法给出程序：

program 正实数加法

1-1：以字符串的形式读入两个实数；

1-2：对齐小数点和各相应数位；

1-3：记录小数点的位置，删除加数和被加数中的小数点；

1-4：按照整数加法求出和；

1-5：还原小数点；

1-6：规格输出结果。

1- 2：对齐小数点和各相应数位部分的求精

1-2-1：根据小数点的位置判断是否是整数，若是整数则在最后添上小数点；

1-2-2：分别记录加数和被加数小数点的位置和整数部分、小数部分的长度；

1-2-3：在整数部分较短的数前面添零，在小数部分较短的数后面添零对齐各相应数位；

1-2-4：重新记录小数点的位置，即整数部分的长度。

1-6：规格输出结果部分的求精：

1-6-1：最后一位是零则删除最后一位；

1-6-2：若小数部分被删除玩，即最后一位是小数点则删除小数点。

按照以上的逐步求精，编制程序如下：

var

s1,s2,s3 : string; {用字符串表示加数、被加数和和}

l1,l2 : integer; {加数和被加数的位数（长度）}

z1,z2,x1,x2 : integer; {加数和被加数的整数部分和小数部分的位数（长度）}

pointpos : integer; {小数点的位置}

i,j,k : integer;

begin

readln(s1);readln(s2);

k:=pos('.',s1);if k=0 then s1:=s1+'.';

k:=pos('.',s2);if k=0 then s2:=s2+'.'; {添上小数点}

l1:=length(s1);k:=pos('.',s1); z1:=k-1;x1:=l1-k;

l2:=length(s2);k:=pos('.',s2); z2:=k-1;x2:=l2-k; {记录小数点的位置}

if z1>z2 then {整数部分对齐}

for k:=1 to z1-z2 do s2:='0'+s2

else

for k:=1 to z2-z1 do s1:='0'+s1;

if x1>x2 then {小数部分对齐}

for k:=1 to x1-x2 do s2:=s2+'0'

else

for k:=1 to x2-x1 do s1:=s1+'0';

k:=pos('.',s1);delete(s1,k,1);delete(s2,k,1);s3:=s1;pointpos:=k;

{删除小数点}

j:=0;

for i:=length(s3) downto 1 do

begin

k:=ord(s1[i])-ord('0')+ord(s2[i])-ord('0')+j;

if k>9 then begin j:=1 ;k:=k-10 end else j:=0;

s3[i]:=chr(ord('0')+k);

end; {逐位加法计算}

if j=1 then

begin

s3:='1'+s3; {最高位的进位}

pointpos:=pointpos+1;

end;

insert('.',s3,pointpos); {还原小数点}