如何在不使用BigInteger的情况下处理Java中的128位小尾数乘法

Question

我需要以尽可能最快的方式将两个8字节（64位）数组相乘。字节数组是小端。这些数组可以包装在ByteBuffer中并作为little endian处理，以便轻松解析正确表示字节的java“long”值（但不是真正的名义值，因为java longs是2s compliment）。

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

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

high bits of long multiplication in Java?

是否有更通用的模式可以从128位乘法获得高/低阶位？这适用于最大的长值？

编辑：

FWIW我已经准备好答案了。“不能在java中这样做，用c ++做，并通过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;
}

这当然将输入视为无符号，这并不意味着它们必须是积极的，因为Java会将它们视为正数，你绝对可以输入-1501598000831384712L和-735932670715772870L并且right answer出来，正如wolfram alpha所证实的那样。

如果您准备与本机代码接口，在C ++中使用MSVC可以使用__umulh，而使用GCC / Clang可以将产品设置为__uint128_t并将其正确移位，其代码是actually fine，它不会导致一个完整的128x128乘法。