c++ - 如何快速计算 100 位数字的乘积

Question

我正在尝试计算两个 100 位数的乘积。它应该模仿 100 位 CPU 架构原生的无符号整数乘法行为。也就是说，程序必须计算实际产品，模 2^100。

为了快速做到这一点，我选择将 100 位数字实现为 uint64_t[2]，一个 64 位数字的二元数组。更准确地说，x = 2^64 * a + b。我需要快速执行算术和逻辑运算(乘积、位移、位旋转、异或等)。我选择这种表示是因为它允许我对 64 位成分使用快速、 native 的操作。例如，旋转一个 128 位“数字”仅比旋转一个 64 位整数慢两倍。 Boost::128bit 慢得多并且 bitset 和 valarray 没有算术。我可以将数组用于除乘法之外的所有操作，然后将数组转换为 boost:128bit，然后再乘法，但这是最后的手段，而且速度可能非常慢。

我试着跟随。让我们有两对这样的 64 位数字，比如 2^64 a + b 和 2^64 x + y。那么乘积可以表示为

2^128 轴 + 2^64 (ay + bx) + 由

我们可以忽略第一项，因为它太大了。拿一对就差不多了

ay + bx, 通过

作为我们的答案，但更重要的一半是“遗漏”了 b*y 操作的溢出。如果不将数字 b,y 分成四个不同的 32 位，并使用分而治之的方法来确保乘积的扩展项不会溢出，我不知道如何计算这个。

这是用于在 10x10 棋盘上使用魔术乘法散列的“国际象棋引擎”

Answer 1

对于可能产生的溢出，您只关心 b * y 中每个数字的最高 32 位:

struct Num {
   uint64_t low;
   uint64_t high;

   Num &operator*=(const Num &o) {
      high = low          *  o.high + 
             high         *  o.low  + 
             (low >> 32u) * (o.low >> 32u); // <- handles overflow
      low  *= o.low;
      high &= 0xFFFFFFFFF; // keeping number 100 bits
      return *this;
   }
};

查看您的 CPU 是否支持任何 native 128 位整数，因为那将是最佳的(尽管不可移植)。

祝您的国际象棋引擎好运!