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

Question

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

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

我已经尝试关注了。让我们有两对这样的 64 位数字，比如 2^64 a + b 和 2^64 x + y。那么乘积可以表示为

2^128 ax + 2^64 (ay + bx) + by

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

就差不多了

ay + bx, by

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

这是针对 'chess engine' 在 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 是否支持任何本机 128 位整数，因为那将是最佳的（尽管不可移植）。

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

Answer 2

想到就借用:
他一心想 100 位，使用 64 位高位和仅 36 位低位误差会更小：
您可以使用 (low >> 4u) * (o.low >> 4u) 计算 "low×low" 的最高 64 位，并将其高 36 位用作溢出到高位。毫不费力地为魔术文字创造名称：

Bits100 &operator*=(const Bits100 &o) {
    high = low        *  o.high +            // ignore high * o.high
           high       *  o.low  + 
          (low >> 4u) * (o.low >> 4u) >> 28; // handles overflow in most cases
    low  = low * o.low & 0xFFFFFFFFF;        // keep low to 100-64 bits
    return *this;
}

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

How do I quickly compute the product of 100bit numbers

c++

overflow

multiplication