高精度计算
此条目包含指南或教学内容。 (2016年7月7日) |
高精度计算是一种程序设计的算法。由于中央处理器的字长限制,如32位CPU中一个整数最大只能取值4,294,967,295(=232-1)。因此在进行更大范围的数值计算中,往往要采取模拟手段。通常通过分离字符的方法通过数字数组进行输入、通过数组倒序输出、通过模拟竖式计算进行计算。一般而言,主要模拟的是按位运算,可以用不同的进位制达成不同的目的。
有许多程式库支援高精度计算,最著名的是GNU多重精度运算库。另外,Java,Python和Pascal也有原生的高精度运算支持。
应用
编辑高精度计算的一个常见应用是公开密钥加密,这些算法经常对长度上百位的整数进行运算。[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;
}
参见
编辑参考文献
编辑- ^ Jacqui Cheng. Researchers: 307-digit key crack endangers 1024-bit RSA. May 23, 2007 [2020-07-09]. (原始内容存档于2009-01-22).
- ^ Archived copy. [2012-03-31]. (原始内容存档于2012-04-01). recommends important RSA keys be 2048 bits (roughly 600 digits).
- ^ 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) (法语).