高精度計算

高精度計算是一種程式設計演算法。由於中央處理器字長限制,如32位元CPU中一個整數最大只能取值4,294,967,295(=232-1)。因此在進行更大範圍的數值計算中,往往要採取類比手段。通常通過分離字元的方法通過數字陣列進行輸入、通過陣列倒序輸出、通過類比豎式計算進行計算。一般而言,主要類比的是按位元運算,可以用不同的進位制達成不同的目的。

有許多程式庫支援高精度計算,最著名的是GNU多重精度運算庫。另外,JavaPythonPascal也有原生的高精度運算支援。

應用

高精度計算的一個常見應用是公開金鑰加密,這些演算法經常對長度上百位的整數進行運算。[1][2]高精度計算的另一個應用是在需要沒有人為限制位數和沒有算術溢位的情況下使用。在檢查固定精度計算的結果以及確定公式中係數的精確值或近似值時,高精度計算也很有用。比如,在高斯求積中,我們需要確定 的值。[3]

實現

高精度加法

簡介

高精度加法是資訊學的一種重要演算法。這種演算法使用多個儲存單位進行計算,因此它的計算範圍超過一般使用一個儲存單位的演算法。也是一些資訊學競賽的常考題目。

基本演算法

以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:

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.

c++:

#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;
}

參見

參考文獻

  1. ^ Jacqui Cheng. Researchers: 307-digit key crack endangers 1024-bit RSA. May 23, 2007 [2020-07-09]. (原始內容存檔於2009-01-22). 
  2. ^ Archived copy. [2012-03-31]. (原始內容存檔於2012-04-01).  recommends important RSA keys be 2048 bits (roughly 600 digits).
  3. ^ Laurent Fousse. Intégration numérique avec erreur bornée en précision arbitraire. Modélisation et simulation (報告). Université Henri Poincaré - Nancy I. 2006 [2020-07-09]. (原始內容存檔於2019-08-31) (法語).