您的位置:

使用int128数据类型进行高精度计算的方法

一、什么是int128数据类型

在C++中,int是用来表示整数的数据类型,int类型占用4个字节(32位),最多能够表示2的31次方-1(即2147483647)。如果需要进行更大的整数计算,可以使用long long类型,其占用8个字节(64位),最多能够表示2的63次方-1(即9223372036854775807)。但是,这依然不能满足高精度计算的需要。

int128数据类型是在uint128_t(128位无符号整数)的基础上,进行了带符号的扩展(signed extension)得到的数据类型。它占用16个字节(128位),最多能够表示2的127次方-1(即170141183460469231731687303715884105727)的整数范围,可以支持高精度计算。

signed __int128 a = 123456789101112131415; // 定义一个int128类型整数变量
std::cout << a << std::endl; // 输出:123456789101112131415

二、int128类型的运算

与普通整数类型相比,int128类型也支持加减乘除等基本运算操作,只需要使用对应的运算符即可。

对于复杂的高精度计算,可以使用字符串读入整数,然后将字符串转换为int128类型进行计算。计算结果再转换为字符串进行输出,这样既保证了计算精确度,又避免了溢出的问题。

// 将字符串转换为int128类型
signed __int128 str2int128(std::string str) {
  signed __int128 x = 0;
  for (auto c : str) {
    if (isdigit(c)) {
      x = x * 10 + (c - '0');
    }
  }
  return x;
}

// 将int128类型转换为字符串
std::string int1282str(signed __int128 x) {
  std::string str;
  if (x < 0) {
    str += "-";
    x = -x;
  }
  while (x) {
    str += static_cast('0' + x % 10);
    x /= 10;
  }
  if (str.empty()) {
    str = "0";
  } else if (str.front() == '-') {
    std::reverse(str.begin() + 1, str.end());
  } else {
    std::reverse(str.begin(), str.end());
  }
  return str;
}

signed __int128 a = str2int128("123456789101112131415");
signed __int128 b = str2int128("987654321012345678901");
signed __int128 c = a * b;
std::cout << int1282str(c) << std::endl; // 输出:1219326311370217951467806858647467256758347028815277915

  

三、使用int128类型实现高精度计算

下面提供一个使用int128类型实现高精度计算加法和乘法的示例程序。

Addition

std::string int128_add(std::string str1, std::string str2) {
  signed __int128 x = str2int128(str1);
  signed __int128 y = str2int128(str2);
  return int1282str(x + y);
}

Multiplication

std::string int128_mul(std::string str1, std::string str2) {
  signed __int128 x = str2int128(str1);
  signed __int128 y = str2int128(str2);
  signed __int128 z = x * y;
  return int1282str(z);
}

使用int128类型进行加法和乘法计算,其时间复杂度都是O(n),其中n表示两个数的位数之和。使用这种方式实现高精度计算,不需要担心溢出的问题,而且比使用数组实现要简单一些。但是,对于除法和取模运算,就需要使用其它的算法实现了。