第二课 多精度数值处理

 所谓多精度值处理，就是在对给定的数据范围，用语言本身提供的数据类型无法直接进行处理（主要指加减乘除运算），而需要采用特殊的处理办法进行。看看下面的例子。

例1 从键盘读入两个正整数，求它们的和。

分析：从键盘读入两个数到两个变量中，然后用赋值语句求它们的和，输出。但是，我们知道，在pascal语言中任何数据类型都有一定的表示范围。而当两个被加数据大时，上述算法显然不能求出精确解，因此我们需要寻求另外一种方法。在读小学时，我们做加法都采用竖式方法，如图1。

这样，我们方便写出两个整数相加的算法。

如果我们用数组A、B分别存储加数和被加数，用数组C存储结果。则上例有

A[1]=6, A[2]=5, A[3]=8, B[1]=5,B[2]=5, B[3]=2, C[4]=1,C[3]=1, C[2]=1,C[1]=1,两数相加如图2所示。由上图可以看出：

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

if C[i]>10 then begin C[i]:= C[i] mod 10; C[i+1]:= C[i+1]+1 end;

因此，算法描述如下：

procedure add(a,b;var c);

{ a,b,c都为数组，a存储被加数，b存储加数，c存储结果 }

var i,x:integer;

begin

   i:=1

   while (i<=a数组长度>0) or(i<=b数组的长度) do begin

x := a[i] + b[i] + x div 10;  {第i位相加并加上次的进位}

c[i] := x mod 10;             {存储第i位的值}

i := i + 1                    {位置指针变量}

   end

end;

通常，读入的两个整数用可用字符串来存储，程序设计如下：

program exam1;

const

max=200;   

var

   a,b,c:array[1..max] of 0..9;

n:string;

   lena,lenb,lenc,i,x:integer;

begin

     write('Input augend:'); readln(n);

     lena:=length(n);       {加数放入a数组}

     for i:=1 to lena do a[lena-i+1]:=ord(n[i])-ord('0');

     write('Input addend:'); readln(n);

     lenb:=length(n);       {被加数放入b数组}

     for i:=1 to lenb do b[lenb-i+1]:=ord(n[i])-ord('0');

     i:=1;

     while (i<=lena) or(i<=lenb) do begin

         x := a[i] + b[i] + x div 10;   {两数相加，然后加前次进位}

         c[i] := x mod 10;          {保存第i位的值}

         i := i + 1

    end;

    if x>=10 then                   {处理最高进位}

begin lenc:=i;c[i]:=1 end  

    else lenc:=i-1;

    for i:=lenc downto 1 do write(c[i]);   {输出结果}

    writeln

end.

 

例2 高精度减法。

从键盘读入两个正整数，求它们的差。

    分析：类似加法，可以用竖式求减法。在做减法运算时，需要注意的是：被减数必须比减数大，同时需要处理借位。

因此，可以写出如下关系式

if a[i]<b[i] then begin a[i+1]:=a[i+1]-1;a[i]:=a[i]+10 end

c[i]:=a[i]-b[i]

类似，高精度减法的参考程序：

program exam2;

const

max=200;   

var

   a,b,c:array[1..max] of 0..9;

   n,n1,n2:string;

   lena,lenb,lenc,i,x:integer;

begin

     write('Input minuend:'); readln(n1);

     write('Input subtrahend:'); readln(n2);

     {处理被减数和减数}

     if (length(n1)<length(n2)) or (length(n1)=length(n2)) and (n1<n2) then

        begin

          n:=n1;n1:=n2;n2:=n;

          write('-')             {n1<n2,结果为负数}

        end;

     lena:=length(n1); lenb:=length(n2);

     for i:=1 to lena do a[lena-i+1]:=ord(n1[i])-ord('0');

     for i:=1 to lenb do b[lenb-i+1]:=ord(n2[i])-ord('0');

     i:=1;

     while (i<=lena) or(i<=lenb) do begin

         x := a[i] - b[i] + 10 + x;   {不考虑大小问题，先往高位借10}

         c[i] := x mod 10 ;        {保存第i位的值}

         x := x div 10 - 1;        {将高位借掉的1减去}

         i := i + 1

    end;

    lenc:=i;

  while (c[lenc]=0) and (lenc>1) do dec(lenc);  {最高位的0不输出}

  for i:=lenc downto 1 do write(c[i]);

    writeln

end.

 

例3 高精度乘法。

从键盘读入两个正整数，求它们的积。

    分析：类似加法，可以用竖式求乘法。在做乘法运算时，同样也有进位，同时对每一位进乘法运算时，必须进行错位相加，如图3, 图4。

分析C数组下标的变化规律，可以写出如下关系式

C _i = C^’ _i +C ^”_i +…

由此可见，C _i跟A[i]*B[j]乘积有关，跟上次的进位有关，还跟原C _i的值有关，分析下标规律，有

x:= A[i]*B[j]+ x DIV 10+ C[i+j-1];

C[i+j-1] := x mod 10;

类似，高精度乘法的参考程序：

program exam3;

const

   max=200;

var

   a,b,c:array[1..max] 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[i])-ord('0');

     for i:=1 to lenb do b[lenb-i+1]:=ord(n2[i])-ord('0');

     for i:=1 to lena do begin              

       x:=0;                       

       for j:=1 to lenb do begin           {对乘数的每一位进行处理}

         x := a[i]*b[j] + x div 10 + c[i+j-1]; {当前乘积+上次乘积进位+原数}  

         c[i+j-1] :=  x mod 10;

       end;

       c[i+j]:= x div 10;       　　　  {进位}

     end;

     lenc:=i+j;

     while (c[lenc]=0) and (lenc>1) do dec(lenc);

     for i:=lenc downto 1 do write(c[i]);

     writeln

end.

 

例４ 高精度除法。

从键盘读入两个正整数，求它们的商（做整除）。

    分析：做除法时，每一次上商的值都在０～９，每次求得的余数连接以后的若干位得到新的被除数，继续做除法。因此，在做高精度除法时，要涉及到乘法运算和减法运算，还有移位处理。当然，为了程序简洁，可以避免高精度乘法，用0～9次循环减法取代得到商的值。这里，我们讨论一下高精度数除以单精度数的结果，采取的方法是按位相除法。

    参考程序： 

program exam4;

const

   max=200;

var

   a,c:array[1..max] of 0..9;

   x,b:longint;

   n1,n2:string;

   lena:integer;

   code,i,j:integer;

begin

     write('Input dividend:'); readln(n1);

     write('Input divisor:'); readln(n2);

     lena:=length(n1);

     for i:=1 to lena do  a[i] := ord(n1[i]) - ord('0');

     val(n2,b,code);

        {按位相除}

     x:=0;

     for i:=1 to lena do begin

         c[i]:=(x*10+a[i]) div b;

         x:=(x*10+a[i]) mod b;

     end;

     {显示商}

     j:=1;

     while (c[j]=0) and (j<lena) do inc(j);    {去除高位的0}

     for i:=j to lena do write(c[i]) ;

     writeln

end.

实质上，在做两个高精度运算时候，存储高精度数的数组元素可以不仅仅只保留一个数字，而采取保留多位数（例如一个整型或长整型数据等），这样，在做运算（特别是乘法运算）时，可以减少很多操作次数。例如图5就是采用4位保存的除法运算，其他运算也类似。具体程序可以修改上述例题予以解决，程序请读者完成。