高精度计算

Published on 2024-4-5

可能需要的头文件：string.h

由于最大的整数类型long long int最大只能存储，而在很多时候我们遇到的数据会远远大于此，因此，我们引入高精度计算来模拟数据的存储和运算，这时候诸如加法、乘法的简单运算需要我们自己写代码来完成。

高精度计算的原理是通过字符串长度与数组长度的任意性，将长数据以字符串的形式输入和以数组的形式存储及运算，进而避免由于整型变量溢出带来的问题。

下面，我们先进行数据输入：

char data_str[501];
scanf("%s",data_str);

现在，我们有了数据，但是它是字符串形式，很难被用于计算，我们需要将它转化为数的形式，为了节约空间，我们需要知道数据的位数，这里也可以使用动态数组进行转化。此处以求出数据长度为例：

int n;
n=strlen(data_str);
int data[n]={},i;
for (i=0;i<=n;i++)
 data[n-i]=data_str[i]-'0';

这样，我们就把得到的数据按位逆序存入了数组。接下来我们要考虑对数据进行加减乘除，这必然要注意进位、退位、大数减小数以及模拟竖式计算。假设，我们有了两个数，分别存在data1和data2中，长度分别为n1和n2。我们先看加法运算：

int n,i;
if (n1>n2)
 n=n1+1;
else
 n=n2+1;
int data[n]={};
if (n1==n2){
 for (i=0;i<n2;i++){
  data[i]=data[i]+data1[i]+data2[i];
  if (data[i]>9){
   data[i+1]=data[i]/10;
   data[i]%=10;
  }
 }
}
else if (n1>n2){
 for (i=0;i<n2;i++){
  data[i]=data[i]+data1[i]+data2[i];
  if (data[i]>9){
   data[i+1]=data[i]/10;
   data[i]%=10;
  }
 }
 data[n2]=data[n2]+data1[n2];
 if (data[n2]>9){
   data[n2+1]=data[n2]/10;
   data[n2]%=10;
 }
 for (i=n2+1;i<n1;i++){
  data[i]=data[i]+data1[i];
 }
}
else{
 for (i=0;i<n1;i++){
  data[i]=data[i]+data1[i]+data2[i];
  if (data[i]>9){
   data[i+1]=data[i]/10;
   data[i]%=10;
  }
 }
 data[n1]=data[n1]+data1[n1];
 if (data[n1]>9){
   data[n1+1]=data[n1]/10;
   data[n1]%=10;
 }
 for (i=n1+1;i<n2;i++){
  data[i]=data[i]+data1[i];
 }
}

但是这样的分类讨论代码过于冗长，这是我们所不希望的，如果我们允许空间占用稍微冗余的话，存储两个数的数组data1和data2长度均为n，就有：

int data[n+1]={};
for (i=0;i<n;i++){
 data[i]=data[i]+data1[i]+data2[i];
 if (data[i]>9){
  data[i+1]=data[i]/10;
  data[i]%=10;
 }
}

我们还以这种方式讨论乘法：

int data[n*2]={};
for (i=0;i<n;i++){
 for (j=0;j<n;j++){
  data[i+j]=data[i+j]+data1[i]*data2[j];
 }
}
for (i=0;i<n*2;i++){
 if (data[i]>9){
  data[i+1]=data[i+1]+data[i]/10;
  data[i]%=10;
 }
}

减法的关键是找到大数和逐位作差逢负借位，如果两数位数不同，则大小易见，如果相同，我们需要先判断：

i=n-1;
while (i>-1){
 if (data1[i]==data2[i]){
  i-=1;
  continue;
 }
 else if (data1[i]<data2[i]){
  int tmp=0;
  for (i=n-1;i>-1;i--){
   tmp=data1[i];
   data1[i]=data2[i];
   data2[i]=tmp;
  }
  break;
 }
 break;
}
for (i=0;i<n;i++){
 data[i]=data[i]+data1[i]-data2[i];
 if (data[i]<0){
  data[i]+=10;
  data[i+1]-=1;
 }
}