查看“︁高精度计算”︁的源代码

{{NoteTA|
|G1=IT
}}
{{howto|time=2016-07-07T05:23:55+00:00}}
{{Floating-point}}

'''高精度计算'''是一种[[程序设计]]的[[算法]]。由于[[中央處理器]]的[[字 (計算機)|字長]]限制，如[[中央处理器#整数范围|32位CPU]]中一个[[整数_(计算机科学)|整数]]最大只能取值[[4294967295|4,294,967,295]]（=2<sup>32</sup>-1）。因此在进行更大范围的数值计算中，往往要采取模拟手段。通常通过分离字符的方法通过数字[[数组]]进行输入、通过数组倒序输出、通过模拟[[竖式]]计算进行计算。一般而言，主要模拟的是按位运算，可以用不同的[[進位制]]達成不同的目的。

有許多程式庫支援高精度計算，最著名的是[[GNU多重精度運算庫]]。另外，[[Java]]，[[Python]]和[[Pascal_(程式語言)|Pascal]]也有原生的高精度运算支持。

== 应用 ==

高精度计算的一个常见应用是[[公开密钥加密]]，这些算法经常对长度上百位的整数进行运算。<ref>{{cite web |url=https://arstechnica.com/news.ars/post/20070523-researchers-307-digit-key-crack-endangers-1024-bit-rsa.html |title=Researchers: 307-digit key crack endangers 1024-bit RSA |author=Jacqui Cheng |date=May 23, 2007 |accessdate=2020-07-09 |archive-date=2009-01-22 |archive-url=https://web.archive.org/web/20090122110753/http://arstechnica.com/news.ars/post/20070523-researchers-307-digit-key-crack-endangers-1024-bit-rsa.html |dead-url=no }}</ref><ref>{{cite web|url=http://www.rsa.com/rsalabs/node.asp?id%3D2218 |title=Archived copy |accessdate=2012-03-31 |url-status=dead |archiveurl=https://web.archive.org/web/20120401144624/http://www.rsa.com/rsalabs/node.asp?id=2218 |archivedate=2012-04-01 }} recommends important RSA keys be 2048 bits (roughly 600 digits).</ref>高精度计算的另一个应用是在需要没有人为限制位数和没有算术溢出的情况下使用。在检查固定精度计算的结果以及确定公式中系数的精确值或近似值时，高精度计算也很有用。比如，在[[高斯求积]]中，我们需要确定<math> \sqrt{1 / 3} </math>的值。<ref>{{cite report | url=https://tel.archives-ouvertes.fr/tel-00477243/en | title=Intégration numérique avec erreur bornée en précision arbitraire. Modélisation et simulation | author=Laurent Fousse | publisher=Université Henri Poincaré - Nancy I | language=fr | date=2006 | access-date=2020-07-09 | archive-date=2019-08-31 | archive-url=https://web.archive.org/web/20190831223923/https://tel.archives-ouvertes.fr/tel-00477243/en | dead-url=no }}</ref>

== 实现 ==

=== 高精度加法 ===

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

==== 基本算法 ====
以358934760892734899+38960302975237462为例：

1、计算结果的位数

358934760892734899共18位

38960302975237462  共17位

故结果不会超过19位。

2、将要计算的数字分割成多段，按照顺序排列（这里以0-32767作为每一存储单位存储的数的限制）：
{| class="wikitable"
|35
|8934
|7608
|9273
|4899
|-
|3
|8960
|3029
|7523
|7462
|}
（为提高空间利用效率，可以一个存储单位存储多位数。）

3、将两数相加。
{| class="wikitable"
!
|35
|8934
|7608
|9273
|4899
|-
!
|3
|8960
|3029
|7523
|7462
|- style="background:silver;"
!和（不进位）
|38
|17894
|10637
|16796
|12361
|- style="background:silver; "
!和（进位后）
|39
|7895
|0638
|6797
|2361
|}
4、输出结果。

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

=== 代码实现 ===
pascal：
<syntaxhighlight lang="pascal" line="1">
var
  a,b,c:array[1..201] of integer; 
  n:string; 
  lena,lenb,lenc,i,x:integer; 
begin
  readln(n); 
  lena:=length(n); 
  for i:=1 to lena do a[lena-i+1]:=ord(n[i])-ord('0'); 
  readln(n); 
  lenb:=length(n); 
  for i:=1 to lenb do b[lenb-i+1]:=ord(n[i])-ord('0'); 
  i:=1; x:=0; 
  while (i<=lena) or(i<=lenb) do
  begin
    c[i]:=a[i]+b[i]+x; 
    x := c[i] div 10;  
    c[i] := c[i] mod 10;  
    i := i + 1; 
  end; 
  if x>0 then
  begin
    lenc:=i; 
    c[i]:=x; 
  end
  else lenc:=i-1; 
  for i:=lenc downto 1 do write(c[i]); 
end. 

</syntaxhighlight>c++：<syntaxhighlight lang="c++" line="1">
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

short a[510],b[510];
char ca[510],cb[510];
short ans[510];
short len;

void add(short a[],short b[])
{
    for(int i=0;i<len;++i)
    {
        ans[i]+=a[i]+b[i];
        if(ans[i]>=10)
        {
            ans[i+1]+=ans[i]/10;
            ans[i]%=10;
        }
    }
    if(ans[len])
        len++;
    else
        while((!ans[len-1])&&len>1)len--;
    return;
}
int main()
{
    scanf("%s",ca);
    scanf("%s",cb);
    short lena=strlen(ca);
    short lenb=strlen(cb);
    len=max(lena,lenb);
    for(short i=0;i<lena;++i)
        a[lena-i-1]=ca[i]&15;
    for(short i=0;i<lenb;++i)
        b[lenb-i-1]=cb[i]&15;
    add(a,b);
    for(short i=len-1;i>=0;--i)
        putchar(ans[i]|'0');
    return 0;
}
</syntaxhighlight>

== 参见 ==
* {{section|乘法算法|大數字的快速乘法演算法}}
** [[卡拉楚巴算法]]
** [[图姆-库克算法]]
** [[頌哈吉-施特拉森演算法]]

==参考文献==
{{reflist}}

[[Category:計算機算術]]