在一般的科学计算中,会经常算到小数点后几百位或者更多,当然也可能是几千亿几百亿的大数字.
一般这类数字我们统称为高精度数,高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除,乘方,阶乘,开放等运算.
譬如一个很大的数字N >= 10^ 100, 很显然这样的数字无法在计算机中正常存储.
于是, 我们想到了办法,将这个数字拆开,拆成一位一位的 或者是四位四位的存储到一个数组中, 用一个数组去表示一个数字.这样这个数字就被称谓是高精度数.
对于高精度数,也要像平常数一样做加减乘除以及乘方的运算,于是就有了高精度算法:
下面提供了Pascal的高精度加法, 高精度乘以单精度, 高精度乘以高精度的代码, 其他版本请各位大牛添加进来吧!
Pascal代码如下(非完整); k为预定进制，加大进制以提高速度。
Procedure HPule(a, b: Arr; Var c:Arr); //高精度加法
Var
i: Integer;
Begin
FillChar(c, SizeOf(c), 0);
For i:= 1 To Maxn-1 Do Begin
c〔i〕:= c〔i〕 + a〔i〕 + b〔i〕;
c〔i + 1〕 := c〔i〕 Div k;
c〔i〕 := c〔i〕 Mod k；
End;
End;
Procedure HPule(a: Arr; b:Integer; Var c:Arr); //高精度乘以单精度
Var
i: Integer;
Begin
FillChar(c, SizeOf(c), 0);
For i:= 1 To Maxn-1 Do Begin
c〔i〕 := c〔i〕 + a〔i〕 * b;
c〔i+1〕:= c〔i〕 Div k;
c〔i〕:= c〔i〕 Mod k
End;
End;
Procedure HPule(a, b: Arr; ; Var c:Arr); //高精度乘以高精度
Var
i, j: Integer;
Begin
FillChar(c, SizeOf(c), 0);
For i:= 1 To Maxn Do
For j := 1 To Maxn Begin
c〔i+j-1〕 := c〔i+j-1〕 + a〔i〕 * b〔j〕;
c〔i+j〕:= c〔i+j-1〕 Div k;
c〔i+j-1〕:= c〔i+j-1〕 Mod k
End;
End;
Ps:为了防止百度错误识别, 过程中有不少符号是全角状态输入.
高精度加法
var
a,b,c:array[1..201] of 0..9;
n:string;
lena,lenb,lenc,i,x:integer;
begin
write('Input augend:'); readln(n);lena:=length(n);
for i:=1 to lena do a[lena-i+1]:=ord(n)-ord('0');{加数放入a数组}
write('Input addend:'); readln(n); lenb:=length(n);
for i:=1 to lenb do b[lenb-i+1]:=ord(n)-ord('0');{被加数放入b数组}
i:=1;
while (i<=lena) or(i<=lenb) do
begin
x := a + b + x div 10; {两数相加，然后加前次进位}
c := x mod 10; {保存第i位的值}
i := i + 1
end;
if x>=10 {处理最高进位}
then begin lenc:=i; c:=1 end
else lenc:=i-1;
for i:=lenc downto 1 do write(c); writeln {输出结果}
end.
高精度乘法（低对高）
const max=100; n=20;
var a:array[1..max]of 0..9;
i,j,k;x:integer;
begin
k:=1; a[k]:=1;{a=1}
for i:=2 to n do{a*2*3….*n}
begin
x:=0;{进位初始化}
for j:=1 do k do{a=a*i}
begin
x:=x+a[j]*i; a[j]:=x mod 10;x:=x div 10
end;
while x>0 do {处理最高位的进位}
begin
k:=k+1;a[k]:=x mod 10;x:=x div 10
end
end;
writeln;
for i:=k dowento 1 write(a){输出a}
end.
高精度乘法（高对高）
var a,b,c:array[1..200] of 0..9;
n1,n2:string; lena,lenb,lenc,i,j,x:integer;
begin
write('Input multiplier:'); readln(n1);
write('Input multiplicand:'); readln(n2);
lena:=length(n1); lenb:=length(n2);
for i:=1 to lena do a[lena-i+1]:=ord(n1)-ord('0');
for i:=1 to lenb do b[lenb-i+1]:=ord(n2)-ord('0');
for i:=1 to lena do
begin
x:=0;
for j:=1 to lenb do{对乘数的每一位进行处理}
begin
x := a*b[j]+x div 10+c;{当前乘积+上次乘积进位+原数}
c:=x mod 10;
end;
c:= x div 10;{进位}
end;
lenc:=i+j;
while (c[lenc]=0) and (lenc>1) do dec(lenc); {最高位的0不输出}
for i:=lenc downto 1 do write(c); writeln
end.
高精度除法
fillchar(s,sizeof(s),0);{小数部分初始化}
fillchar(posi,sizeof(posi),0); {小数值的位序列初始化}
len←0;st←0; {小数部分的指针和循环节的首指针初始化}
read(x,y);{读被除数和除数}
write(x div y);{输出整数部分}
x←x mod y;{计算x除以y的余数}
if x=0 then exit;{若x除尽y，则成功退出}
while len<limit do{若小数位未达到上限，则循环}
begin
inc(len);posi[x]←len;{记下当前位小数，计算下一位小数和余数}
x←x*10; s[len]←x div y;x←x mod y;
if posi[x]<>0 {若下一位余数先前出现过，则先前出现的位置为循环节的开始}
then begin st←posi[x]; break;end;{then}
if x=0 then break; {若除尽，则成功退出}
end;{while}
if len=0
then begin writeln;exit;end;{若小数部分的位数为0，则成功退出；否则输出小数点}
write('.');
if st=0 {若无循环节，则输出小数部分，否则输出循环节前的小数和循环节}
then for i←1 to len do write(s)
else begin
for i←1 to st-1 do write(s);
write('(');
for i←st to len do write(s);
write(')');
end;{else}
所谓的高精度运算,是指参与运算的数(加数,减数,因子……）范围大大超出了标准数据类型（整型，实型）能表示的范围的运算。例如，求两个200位的数的和。这时，就要用到高精度算法了。在这里，我们首先讨论高精度加法。
[编辑本段]高精度加法
高精度运算主要解决以下三个问题：
一、加数、减数、运算结果的输入和存储
运算因子超出了整型、实型能表示的范围，肯定不能直接用一个数的形式来表示。在Pascal中，能表示多个数的数据类型有两种：数组和字符串。
数组：每个数组元素存储1位（在优化时，这里是一个重点！），有多少位就需要多少个数组元素；用数组表示数的优点：每一位都是数的形式，可以直接加减；运算时非常方便。用数组表示数的缺点：数组不能直接输入；输入时每两位数之间必须有分隔符，不符合数值的输入习惯；
字符串：String型字符串的最大长度是255，可以表示255位。Ansistring型字符串长度不受限制。用字符串表示数的优点：能直接输入输出，输入时，每两位数之间不必分隔符，符合数值的输入习惯；用字符串表示数的缺点：字符串中的每一位是一个字符，不能直接进行运算，必须先将它转化为数值再进行运算；运算时非常不方便；
综合以上所述，对上面两种数据结构取长补短：用字符串读入数据，用数组存储数据：
var st:string;
x,y:array[0..255]of integer;{定义两个数组,X和Y,用来储存数}
i,j,l1,l2:integer;
begin
readln(st);
l1:=length(st);{------length(x),该函数是获取字符串X的长度,返回为整型}
for i:=0 to 255 do x[i]:=0;{数组初始化}
for i:=l1 downto 1 do
x[l1-i+1]:=ord(st[i])-ord('0');{------这里是重点,把字符串转换为数值,储存在数组中}
readln(st);
l2:=length(st);{------length(x),该函数是获取字符串X的长度,返回为整型}
for i:=0 to 255 do y[i]:=0;{数组初始化}
for i:=l2 downto 1 do
y[l2-i+1]:=ord(st[i])-ord('0');{------这里是重点,把字符串转换为数值,储存在数组中}
对字符串转为数值原理补充:ord(x)-48,如果X='1',因为'1'的ASCLL码是49,所以减去48就等于1,间接地把字符转换为数值了,各位初手要好好体会.
二、运算过程
在往下看之前，大家先列竖式计算35+86。
注意的问题：
（1）运算顺序：两个数靠右对齐；从低位向高位运算；先计算低位再计算高位；
（2）运算规则：同一位的两个数相加再加上从低位来的进位，成为该位的和；这个和去掉向高位的进位就成为该位的值；如上例：3+8+1=12，向前一位进1，本位的值是2；可借助MOD、DIV运算完成这一步；
（3）最后一位的进位：如果完成两个数的相加后，进位位值不为0，则应添加一位；
（4）如果两个加数位数不一样多，则按位数多的一个进行计算；
if l1<l2 then l1:=l2;
for i:=1 to l1 do
begin
x[i]:=x[i]+y[i];
x[i+1]:=x[i+1]+x[i] div 10;
x[i]:=x[i] mod 10;
end;
三、结果的输出（这也是优化的一个重点）
按运算结果的实际位数输出
var st:string;
x,y:array[0..255]of integer;
i,j,l1,l2:integer;
begin
readln(st);
l1:=length(st);
for i:=0 to 255 do x[i]:=0;
for i:=l1 downto 1 do
x[l1-i+1]:=ord(st[i])-ord('0');
readln(st);
l2:=length(st);
for i:=0 to 255 do y[i]:=0;
for i:=l2 downto 1 do
y[l2-i+1]:=ord(st[i])-ord('0');
if l1<l2 then l1:=l2;
for i:=1 to l1 do
begin
x[i]:=x[i]+y[i];
x[i+1]:=x[i+1]+x[i] div 10;
x[i]:=x[i] mod 10;
end;
write('x+y=');
j:=255;
while x[j]=0 do j:=j-1;
for i:=j downto 1 do write(x[i]);
readln;
end.
四、优化：
以上的方法的有明显的缺点：
（1）浪费空间：一个整型变量（-32768~32767）只存放一位（0~9）；
（2）浪费时间：一次加减只处理一位；
针对以上问题，我们做如下优化：一个数组元素存放四位数；（integer的最大范围是32767，5位的话可能导致出界）将标准数组改为紧缩数组。第一步的具体方法：
l:=length(s1);
k1:=260;
repeat {————有关字符串的知识}
s:=copy(s1,l-3,4);
val(s,a[k1],code);
k1:=k1-1;
s1:=copy(s1,1,l-4);
l:=l-4;
until l<=0;
k1:=k1+1;
而因为这个改进，算法要相应改变：
（1）运算时：不再逢十进位，而是逢万进位（mod 10000; div 10000);
（2）输出时：最高位直接输出，其余各位，要判断是否足够4位，不足部分要补0；例如：1，23，2345这样三段的数，输出时，应该是100232345而不是1232345。
改进后的算法：
program sum;
var s1,s2,s:string;
a,b,c:packed array [1..260] of integer;
i,l,k1,k2,code:integer;
begin
write('input s1:');readln(s1);
write('input s2:');readln(s2);
l:=length(s1);
k1:=260;
repeat {————有关字符串的知识}
s:=copy(s1,l-3,4);
val(s,a[k1],code);
k1:=k1-1;
s1:=copy(s1,1,l-4);
l:=l-4;
until l<=0;
k1:=k1+1;
l:=length(s2);
k2:=260;
repeat
s:=copy(s2,l-3,4);
val(s,b[k2],code);
k2:=k2-1;
s2:=copy(s2,1,l-4);
l:=l-4;
until l<=0;
k2:=k2+1;
if k1<k2 then k:=k1 else k:=k2;
y:=0;
for i:=260 downto k do
begin
x:=a+b+y;
c:=x mod 10000;
y:=x div 10000;
end;
if y<>0 then begin k:=k-1;c[k]:=y;end;
write(c[k]);
for i:=k+1 to 260 do
begin
if c<1000 then write('0');
if c<100 then write('0');
if c<10 then write('0');
write(c);
end;
writeln;
end.
参考资料：hi.baidu.com/xukq