我如何在不借助BigInteger的情况下处理Java中的128位小尾数乘法 [英] How can I handle 128 bit little endian multiplication in Java without resorting to BigInteger

问题描述

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

I need to multiply two 8 byte (64 bit) arrays in the fastest way possible. The byte arrays are little endian. The arrays can be wrapped in a ByteBuffer and treated as little endian to easily resolve a java "long" value that correctly represents the bytes (but not the real nominal value since java longs are 2s compliment).

Java处理大型数学运算的标准方法是BigInteger.但是该实现是缓慢且不必要的，因为我非常严格地使用64位x 64位.另外，由于标称值不正确，您不能将"long"值变成一个整数，并且因为字节序很小，所以我不能直接使用字节数组.我需要能够做到这一点，而不必消耗更多的内存/CPU来反转阵列.这种乘法应该能够每秒执行1m +次.无论如何，BigInteger并不能真正满足该要求，因此我正在尝试通过将高阶位与低阶位分开来实现这一点，但是我无法使其始终如一地工作.

Java's standard way to handle large math is BigInteger. But that implementation is slow and unnecessary since im very strictly working with 64 bits x 64 bits. In addition, you can't throw the "long" value into one because the nominal value is incorrect, and I can't use the byte array directly because it's little endian. I need to be able to do this without having to use up more memory / CPU to reverse the array. This type of multiplication should be able to execute 1m+ times per second. BigInteger doesn't really come close to meeting that requirement anyway, so I'm trying to do it via splitting the high order bits from the low order bits, but I can't get it working consistently.

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

The high-order-bits-only code is only working for a subset of longs because even the intermediate addition can overflow. I got my current code from this answer....

Java中长乘法的高位?

是否有更通用的模式可以从128位乘法中获取高/低位?那对最大的长值有效吗?

Is there a more generic pattern for getting hi/lo order bits from 128 bit multiplication? That works for the largest long values?

FWIW我已经为答案做好了准备.不能在Java中做到这一点，而在C ++中做到这一点并通过JNI进行调用".尽管我希望有人能在此之前给出一个Java解决方案.

FWIW I'm prepared for the answer to be.. "cant do that in java, do it in c++ and call via JNI". Though I'm hoping someone can give a java solution before it comes to that.

推荐答案

可以通过将多头分成两半，创建部分乘积，然后求和来在没有BigInteger的情况下手动完成.当然，可以省去总数的下半部分.

It can be done manually without BigInteger by splitting the longs up into two halves, creating the partial products, and then summing them up. Naturally the low half of the sum can be left out.

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

The partial products overlap, like this:

  LL
 LH
 HL
HH

因此，必须将LH和HL的高半部分添加到较高的结果中，此外，LH和HL的低半部分以及LL的高半部分可能会影响结果的高半部分.LL的下半部分未使用.

So the high halves of LH and HL must be added to the high result, and furthermore the low halves of LH and HL together with the high half of LL may carry into the bits of the high half of the result. The low half of LL is not used.

类似这样(仅经过稍微测试):

So something like this (only slightly tested):

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，正确答案出来了，由

This of course treats the input as unsigned, which does not mean they have to be positive in the sense that Java would treat them as positive, you can absolutely input -1501598000831384712L and -735932670715772870L and the right answer comes out, as confirmed by wolfram alpha.

如果您准备与本机代码交互，则可以在带有MSVC的C ++中使用

If you are prepared to interface with native code, in C++ with MSVC you could use __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, it doesn't cause a full 128x128 multiply.

这篇关于我如何在不借助BigInteger的情况下处理Java中的128位小尾数乘法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！