高精度算法大全.doc

此文档收集于网络，如有侵权，请联系网站删除高精度算法大全在一般的科学计算中,会经常算到小数点后几百位或者更多,当然也可能是几千亿几百亿的大数字.一般这类数字我们统称为高精度数,高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除,乘方,阶乘,开放等运算.譬如一个很大的数字N = 10 100, 很显然这样的数字无法在计算机中正常存储.于是, 我们想到了办法,将这个数字拆开,拆成一位一位的 或者是四位四位的存储到一个数组中, 用一个数组去表示一个数字.这样这个数字就被称谓是高精度数.对于高精度数,也要像平常数一样做加减乘除以及乘方的运算,于是就有了高精度算法: 由于计算机输入计算结果的精度通常受到计算机的限制，如：在双精度方式下，计算机最多只能输出16位有效数字，如果超过16位，则只能按浮点形式输出，另外，一般计算机实数表示的范围为1038，如果超过这个范围，计算机就无法表示了。但是我们可以通过一些简单的办法来解决这个问题。这就是我们要说的高精度计算机。一、基本方法： 在计算机上进行高精度计算，首先要处理好以下几个基本问题： 1、数据的接收与存储； 2、计算结果位数的确定；3、进位处理和借位处理； 4、商和余数的求法；下面我们逐一介绍一下这几个问题的解决方法。1、数据的接收与存储：要在计算机上进行高精度计算，首先就应该有精确的输入，即计算机要精确地接收和存储数据。通常：、当输入的数值在计算机允许的范围内时，可以用数值型变量来接收数据。、当输入的数据超过计算机允许显示的精度范围时，采用字符来接收数据。、分离各位数字。接收数据子模块(字符型变量接收数据)：prucedure readdata(var in:array1.100 of integer);var ch:char;i,k:integer;beginread(ch);k:=0;while ch in0.9 do begininc(k);intk:=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(ab)+1=trunc(b*lg a )+1=trunc(b*ln a / ln10)+13、进位处理和借位处理、加法的进位处理进行加法处理时，先设置一个加法进位标志 T，并将 T 的初值设为 0。当两数相加时，从低位到高位，各位数字分别相加，如果相加后某个单元中的数大于 10，则将该单元中的数减去10，并将进位标志 T 设为 1，当对下一单元进行相加时，还要再加上前一个单元的进位标志 T。同时将 T 再次置为 0，不断重复，直到最高位为止。具体算法为：T:=0;对变量 I 从 1 到 N，重复下列步骤：Ci:=Ai+Bi+T;T:=0;IF Ci=10 THEN BEGIN Ci:=Ci-10;T:=1;END;、乘法的进位处理Y:=Ai*Bi+C;C:=Y div 10;CI+J-1:=Y-C*10、减法的借位处理IF Ai AI+1:=AI+1-1;Ai:=Ai+10END IFCi:=Ai-Bi;4、商和余数的求法设A，B分别为不大于9位的整数，则：C:=A DIV B为商的整数部分X:=A MOD B为余数二、算法与实例：1、求任意位数的加法运算【问题分析】：、数据的接收和存储采用字符串输入的方式，设参与运算的两个数分别为A和B，利用字符串函数把字符串转化为数值，将A、B中的每一位数字分别存储在A、B两个数组中，最低位在第一个单元中。(PASCAL语言中可以直接采用字符读取的方式来接收数据，而后通过ORD(x)-48的方式转化成数值。)、确定和的位数设LA为A的位数，LB为B的位数，则两数之和的位数最大为较大加数位数加1，即如果LALB，则和的位数最大为LA+1。、进位处理进行加法处理时，先设置一个加法进位标志 T，并将 T 的初值设为 0。当两数相加时，从低位到高位，各位数字分别相加，如果相加后某个单元中的数大于 10，则将该单元中的数减去10，并将进位标志 T 设为 1，当对下一单元进行相加时，还要再加上前一个单元的进位标志 T。同时将 T 再次置为 0，不断重复，直到最高位为止。 程序清单：program gjdjs;const n=100;type arrtype=array1.n of integer;vara,b:arrtype;t,s,j,l:integer;procedure readdata(var int:arrtype);varch:char;i,k:integer;beginwriteln(Input a number:);read(ch);k:=0;while ch in0.9 do begininc(k);intk:=ord(ch)-48;read(ch);end;for i:=k downto 1 do beginintn+i-k:=inti;inti:=0;end;end;beginreaddata(a);readln;readdata(b);writeln;t:=0;for j:=n downto 1 do begins:=aj+bj+t;aj:=s mod 10;t:=s div 10;end;j:=1;writeln(output:);while aj=0 do j:=j+1;while jz2 then 整数部分对齐 for k:=1 to z1-z2 do s2:=0+s2 else for k:=1 to z2-z1 do s1:=0+s1; if x1x2 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(s1i)-ord(0)+ord(s2i)-ord(0)+j; if k9 then begin j:=1 ;k:=k-10 end else j:=0; s3i:=chr(ord(0)+k); end; 逐位加法计算 if j=1 then begin s3:=1+s3; 最高位的进位 pointpos:=pointpos+1; end; insert(.,s3,pointpos); 还原小数点 while s3length(s3)=0 do delete (s3,length(s3),1); 删除小数部分末尾的零 if s3length(s3)=. then delete (s3,length(s3),1); 根据条件删除小数点 writeln(s3); end. 2、求任意位数的减法运算、数据的接收和存储采用字符串输入的方式，设参与运算的两个数分别为A和B，利用字符串函数把字符串转化为数值，将A、B中的每一位数字分别存储在A、B两个数组中，最低位在第一个单元中。(PASCAL语言中可以直接采用字符读取的方式来接收数据，而后通过ORD(x)-48的方式转化成数值。)、确定差的位数设LA为A的位数，LB为B的位数，则两数之差的位数最大为较大数的位数，即如果LALB，则差的位数最大为LA。、借位处理做减法运算时，要先判断是否需要借位，如果需要借位，从上一位借过一个10，上一位的数减去1，处理完之后再相减。、负数的处理如果减数大于被减数，则交换A、B的值，并令负数标志 T=-1。当打印计算结果时，先判断 T 的值是否为-1，如果T=-1，则在数值前面先输出一个负号。程序清单：program gjdjs;const n=100;type arrtype=array1.n of integer;vara,b:arrtype;g,t,j,l:integer;s:char;f:boolean;procedure readdata(var int:arrtype);varch:char;i,k:integer;beginwriteln(Input a number:);read(ch);k:=0;while ch in0.9 do begininc(k);intk:=ord(ch)-48;read(ch);end;for i:=k downto 1 do beginintn+i-k:=inti;inti:=0;end;end;beginreaddata(a);readln;readdata(b);writeln;f:=true;j:=1;while (aj=bj) and (j=bj+g then beginaj:=aj-bj-g;g:=0;endelse beginaj:=10+aj-bj-g;g:=1;end;j:=1;writeln(output:);write(s);while (aj=0) and (j4 then bl:=bl+1;for i:=l downto 1 doif bi=10 then beginbi:=bi-10;bi-1:=bi-1+1;endelsei:=1;write(b0,.);for i:=1 to l do write(bi);end;readln;end. 5、求多精度A单精度B的商和余数。、数据的接收和存储采用字符串输入的方式，设参与运算的两个数分别为A和B，利用字符串函数把字符串转化为数值，将A中的每一位数字分别存储在A数组中。(PASCAL语言中可以直接采用字符读取的方式来接收数据，而后通过ORD(x)-48的方式转化成数值。)。B则可以用一般的整数变量来接收和存储。、算法首先，我们知道，在做除法运算时，有一个不变的量和三个变化的量，不变的量是除数，三个变化的量分别是：被除数、商和余数。做除法运算时，每次都是用被除数减去商与除数的积，如果所得余数不为零，则将其扩大10倍再次作为被除数，继续试除，直至余数为零或达到要求的精确度为止。程序清单：program gjdcydjd;type arrtype=array0.100000000 of integer;vara,d:arrtype;g,b,i,j,s,k,l:integer;c:ansistring;beginassign(input,in.txt);reset(input);assign(output,out.txt);rewrite(output);readln(c);l:=length(c);for i:=1 to l do ai:=ord(ci)-48;readln(b);g:=0;k:=0;for i:=1 to l do begins:=ai+g*10;k:=k+1;dk:=s div b;g:=s mod b;end;j:=1;while dj=0 do j:=j+1;for i:=j to k do write(di);if g0 then writeln(.,g);close(input);close(output);end.6、5、求多精度A多精度B的商和余数。、数据的接收和存储采用字符串输入的方式，设参与运算的两个数分别为A和B，利用字符串函数把字符串转化为数值，将A、B中的每一位数字分别存储在A和B数组中。(PASCAL语言中可以直接采用字符读取的方式来接收数据，而后通过ORD(x)-48的方式转化成数值。)。、算法可以用减法代替除法运算：不断比较A1.n与B1.n的大小，如果A1.n=B1.n则商C1.n+1C1.n，然后就是一个减法过程：A1.n-B1.nA1.n。由于简单的减法速度太慢，故必须进行优化。设置一个位置值J，当A1.nB1.n时。B1.n左移B0.n，j:=j+1，即令B1.n增大10倍。这样就减少了减法的次数。当j0且A1.n.n时，B0.n右移B0.n，j:=j-1，即令B1.n缩小10倍。程序清单： Borland PASCAL V7.0 语言源程序program gjdcygjd;const n=100;type arrtype=array1.n of integer;vara,b,c:arrtype;g,s,i,j,k,l:integer;procedure readdata(var int:arrtype);varch:char;i,k:integer;beginwrite(Input a number:);read(ch);k:=0;while ch in0.9 do begininc(k);intk:=ord(ch)-48;read(ch);end;end;function f(a,b:arrtype):boolean;var j:integer;beginf:=true;j:=1;while (aj=bj) and (j=bi+g) dobeginai:=ai-bi-g;g:=0;endelsebeginai:=10+ai-bi-g;g:=1;end;end;procedure ine(n:integer);var i,s:integer;beging:=0;cn:=cn+1;for i:=n downto 1 do begins:=ci+g;ci:=s mod 10;g:=s div 10;end;end;beginreaddata(a);readln;readdata(b);writeln;j:=1;while f(a,b) do beginj:=j+1;for i:=2 to n do bi-1:=bi;bn:=0;end;while j0 do beginwhile f(a,b) do beginine(n-j+1);sub;end;j:=j-1;for i:=n downto 2 do beginbi:=bi-1;bi-1:=0;end;end;j:=1;writeln(output:);while (cj=0) and (j=n do beginwrite(cj);inc(j);end;j:=1;while (aj=0) and (j=n) do j:=j+1;if j=n then write(.);while j0;a-1:=dot-t+1;if t1 thenbeginfor i:=1 to j-t do ai:=ai+t-1;for i:=j-t+1 to j do ai:=0end;end;procedure frmt(var f:intn22);var j,fj,fj1:integer;beginfor j:=n2 downto 2 dobeginfj:=fj;if(fj9) thenbeginfj1:=fj div 10;fj-1:=fj-1+fj1;fj:=fj-(fj1*10)end;endend;procedure multy(d,e:intn22; var f:intn22); d*e f var k,j,dj:integer;beginfor j:=1 to n2 do fj:=0;for j:=1 to n1 dobegindj:=dj;if dj0 thenfor k:=j+1 to n1+j do fk:=fk+dj*ek-j;if (j mod 100 =0) then frmt(f);end;frmt(f); f0:=d0*e0; f-1:=d-1+e-1end;procedure prtc2(var c1:intn22);var t,i,j:integer;beginif c10=-1 then write(-);t:=n2+1;repeat t:=t-1 until c1t0;if c1-10thenbeginj:=1;if c11=0 then j:=2;for i:=j to c1-1 do write(c1i);write(.);for i:=c1-1+1 to t do write(c1i)endelsebeginwrite(0.);if c1-10 thenfor i:=1 to abs(c1-1) do write(0);for i:=1 to t do write(c1i)end;end;begin main for i:=1 to n1 do ch1i:= ;ch2:=ch1; writeln;writeln(输入被乘数 (=250 位):); readln(ch1);writeln(输入乘数 (=250 位):); readln(ch2);chtoint2(ch1,a1); chtoint2(ch2,b1);writeln; writeln(计算结果:);prtc2(a1); writeln(*);if b109 thenbegin c1i:=c1i-10; c1i-1:=c1i-1+1 end;c10:=a10;end;procedure minus(var a1,b1,c1:intn2); 减法运算 var i,max:integer;a2,b2:intn2;beginmax:=1; i:=0;repeati:=i+1;if b1ia1i then max:=2until (b1ia1i) or (i=n2);a2:=a1; b2:=b1;if max=2 then begin a2:=b1; b2:=a1 end;for i:=n2 downto 2 dobeginif a2i0;if tn1 then t:=n1;for i:=t to n1 do write(c1i);write(.);t:=n2+1;repeat t:=t-1 until c1t0;if tn1+1 then t:=n1+1;for i:=n1+1 to t do write(c1i);end;begin main for i:=1 to n1 do ch1i:= ;ch2:=ch1; writeln;writeln(输入被加数 (=250 位):); readln(ch1);repeatwriteln(输入运算符 (+/-):); readln(operch);until (operch=-) or (operch=+);writeln(输入加数 (=250 位):); readln(ch2);chtoint(ch1,a1); chtoint(ch2,b1);writeln; writeln(计算结果:);prtc1(a1); writeln(operch);if b100 do s2:=0+s2; s:=;for i:=1 to (length(s2) div 3) dobegint:=copy(s2,1,3); delete(s2,1,3);j:=-3;repeat j:=j+4 until copy(str2,j,3)=t;s:=s+str8jend;s2to8:=send;procedure minus(a,b:string; var c:string; var flag:boolean);var i,i1,j,lb:integer;beginflag:=true; lb:=length(b);while length(a)lb) and (a1=0) do delete(a,1,1);if (alb then i1:=i+1;if ai1=bi then c:=0+celse if ai1bi then c:=1+celse beginj:=i1;repeataj:=succ(succ(aj);aj-1:=pred(aj-1);j:=j-1;until aj=0;c:=1+cend;end;while (c1=0) and (length(c)1) do delete(c,1,1)end;procedure divid(a,b:string);var c,d,e:string;flag:boolean; lb:integer;beginwhile (b1=0)and(length(b)0) do delete(b,1,1);lb:=length(b);if lb=0 then beginwriteln(数据错: 除数为零 !);exitend;