高精度计算

维基百科,自由的百科全书
跳到导航 跳到搜索

高精度计算是一种程序设计算法。由于中央處理器字長限制,如32位CPU中一个整数最大只能取值4,294,967,295。因此在进行更大范围的数值计算中,往往要采取模拟手段。通常通过分离字符的方法通过数字数组进行输入。通过数组倒序输出。通过模拟竖式计算进行计算。一般而言,主要模拟的是按位运算,可以用不同的進位制達成不同的目的。

有許多程式庫支援高精度計算,最著名的是GNU多重精度運算庫

種類[编辑]

  • 高精度加法
  • 高精度減法
  • 高精度乘法
  • 高精度除法

高精度加法[编辑]

简介[编辑]

高精度加法是信息学的一种重要算法。这种算法使用多个存储单位进行计算,因此它的计算范围超过一般使用一个存储单位的算法。也是一些信息学竞赛的常考题目。

基本算法[编辑]

以358934760892734899+38960302975237462为例:

1、计算结果的位数

358934760892734899共18位

38960302975237462 共17位

故结果不会超过19位。

2、将要计算的数字分割成多段,按照顺序排列(这里以0-32767作为每一存储单位存储的数的限制):

35 8934 7608 9273 4899
3 8960 3029 7523 7462

(为提高空间利用效率,可以一个存储单位存储多位数。)

3、将两数相加。

35 8934 7608 9273 4899
3 8960 3029 7523 7462
和(不进位) 38 17894 10637 16796 12361
和(进位后) 39 7895 0638 6797 2361

4、输出结果。

从高位到低位依次输出。除最高位以外,其他低位上不足4位的要在前面补上0。

代码实现[编辑]

pascal:

 1 var
 2   a,b,c:array[1..201] of integer; 
 3   n:string; 
 4   lena,lenb,lenc,i,x:integer; 
 5 begin
 6   readln(n); 
 7   lena:=length(n); 
 8   for i:=1 to lena do a[lena-i+1]:=ord(n[i])-ord('0'); 
 9   readln(n); 
10   lenb:=length(n); 
11   for i:=1 to lenb do b[lenb-i+1]:=ord(n[i])-ord('0'); 
12   i:=1; x:=0; 
13   while (i<=lena) or(i<=lenb) do
14   begin
15     c[i]:=a[i]+b[i]+x; 
16     x := c[i] div 10;  
17     c[i] := c[i] mod 10;  
18     i := i + 1; 
19   end; 
20   if x>0 then
21   begin
22     lenc:=i; 
23     c[i]:=x; 
24   end
25   else lenc:=i-1; 
26   for i:=lenc downto 1 do write(c[i]); 
27 end.

c++:

 1 #include <cstdio>
 2 #include <algorithm>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 short a[510],b[510];
 7 char ca[510],cb[510];
 8 short ans[510];
 9 short len;
10 
11 void add(short a[],short b[])
12 {
13     for(int i=0;i<len;++i)
14     {
15         ans[i]+=a[i]+b[i];
16         if(ans[i]>=10)
17         {
18             ans[i+1]+=ans[i]/10;
19             ans[i]%=10;
20         }
21     }
22     if(ans[len])
23         len++;
24     else
25     {
26         while((!ans[len-1])&&len>1)
27         {
28             len--;
29         }
30     }
31     return;
32 }
33 
34 short zhuan(char a)
35 {
36     return a-'0';
37 }
38 
39 int main()
40 {
41     scanf("%s",ca);
42     scanf("%s",cb);//gets有bug(空格的问题),有些题库(如洛谷)不给过。
43     short lena=strlen(ca);
44     short lenb=strlen(cb);
45     len=max(lena,lenb);
46     for(short i=0;i<lena;++i)
47     {
48         a[lena-i-1]=zhuan(ca[i]);
49     }
50     for(short i=0;i<lenb;++i)
51     {
52         b[lenb-i-1]=zhuan(cb[i]);
53     }
54     add(a,b);
55     for(short i=len-1;i>=0;--i)
56     {
57         putchar(ans[i]+'0');
58     }
59     return 0;
60 }

模板题[编辑]

高精度加法:

OpenJudge:http://noi.openjudge.cn/ch0106/10/

洛谷:https://www.luogu.org/problemnew/show/P1601

参见[编辑]

高精度加法

高精度减法