如何在不求助于 BigInteger 的情况下处理 Java 中的 128 位小字节序乘法

Question

我需要以最快的方式将两个 8 字节（64 位）数组相乘。字节数组是小端。数组可以包装在 ByteBuffer 中并被视为小端字节序以轻松解析正确表示字节的 java "long" 值（但不是真正的标称值，因为 java 长是 2s 补码).

Java 处理大型数学的标准方法是 BigInteger。但是这个实现很慢而且没有必要，因为我非常严格地使用 64 位 x 64 位。另外，你不能把"long"的值丢成一个，因为标称值不对，我也不能直接用byte数组，因为是little endian。我需要能够做到这一点，而不必耗尽更多内存/CPU 来反转数组。这种类型的乘法应该能够每秒执行 1m+ 次。无论如何，BigInteger 并没有真正接近满足该要求，所以我试图通过将高位与低位分开来做到这一点，但我无法让它始终如一地工作。

仅高阶位代码仅适用于 long 的子集，因为即使是中间加法也可能溢出。我从这个答案中得到了我当前的代码....

high bits of long multiplication in Java?

是否有更通用的模式来从 128 位乘法中获取 hi/lo 次序位？这适用于最大的 long 值吗？

编辑：

FWIW 我已经准备好答案是.. "cant do that in java, do it in c++ and call via JNI"。虽然我希望有人能在此之前提供 java 解决方案。

Answer 1

可以在没有 BigInteger 的情况下手动完成，方法是将多头分成两半，创建部分产品，然后将它们相加。自然可以去掉和的低半部分。

部分产品重叠，如下所示：

  LL
 LH
 HL
HH

因此必须将LH和HL的高半部分加到结果的高位上，而且LH和HL的低半部分连同LL的高半部分可以进位结果的高半部分。 LL的低半部分没有用到。

所以像这样（只是稍微测试了一下）：

static long hmul(long x, long y) {
    long m32 = 0xffffffffL;
    // split
    long xl = x & m32;
    long xh = x >>> 32;
    long yl = y & m32;
    long yh = y >>> 32;
    // partial products
    long t00 = xl * yl;
    long t01 = xh * yl;
    long t10 = xl * yh;
    long t11 = xh * yh;
    // resolve sum and carries
    // high halves of t10 and t01 overlap with the low half of t11
    t11 += (t10 >>> 32) + (t01 >>> 32);
    // the sum of the low halves of t10 + t01 plus
    // the high half of t00 may carry into the high half of the result
    long tc = (t10 & m32) + (t01 & m32) + (t00 >>> 32);
    t11 += tc >>> 32;
    return t11;
}

这当然将输入视为 unsigned，这并不意味着它们必须是正数，因为 Java 会将它们视为正数，您可以绝对输入 -1501598000831384712L 和 -735932670715772870L 和 right answer comes out, as confirmed by wolfram alpha.

如果您准备好与本机代码交互，在 C++ 和 MSVC 中您可以使用 __umulh, and with GCC/Clang you can make the product as an __uint128_t and just shift it right, the codegen for that is actually fine，它不会导致完整的 128x128 乘法。

如何在不求助于 BigInteger 的情况下处理 Java 中的 128 位小字节序乘法

How can I handle 128 bit little endian multiplication in Java without resorting to BigInteger

java

64-bit

bit-manipulation

biginteger

multiplication