java中长乘法的高位?

ktecyv1j  于 2021-07-03  发布在  Java
关注(0)|答案(7)|浏览(322)

有没有办法得到二的乘法的高半部分 long 什么是 java 语?i、 因溢流而消失的部分(所以128位结果的上64位)
我习惯于在命令 mul_hi 确实是这样的:http://www.khronos.org/registry/cl/sdk/1.0/docs/man/xhtml/mul_hi.html
既然opencl可以在我的cpu上高效地完成这项工作,java也应该能够做到,但是我找不到在java中应该如何做到这一点(甚至不能有效地模仿它的行为)。这在java中是可能的吗?如果可能,如何实现?

xzlaal3s

xzlaal3s1#

Java9有math.multiplyhigh,根据javadocs的说法,它“返回两个64位因子的128位乘积中最重要的64位。”

vybvopom

vybvopom2#

如果x或y可以是负数,你应该使用hacker's delight函数(henry s。沃伦,《黑客的喜悦》,艾迪生·韦斯利,第2版,图8.2):

long x_high = x >>> 32;
long x_low = x & 0xFFFFFFFFL;
long y_high = y >>> 32;
long y_low = y & 0xFFFFFFFFL;
long z2 = x_low * y_low;
long t = x_high * y_low + (z2 >>> 32);
long z1 = t & 0xFFFFFFFFL;
long z0 = t >>> 32;
z1 += x_low * y_high;
return x_high * y_high + z0 + (z1 >>> 32);
js81xvg6

js81xvg63#

下面是来自java的 Math.multiplyHigh(long,long) ```
public static long multiplyHigh(long x, long y) {
if (x < 0 || y < 0) {
// Use technique from section 8-2 of Henry S. Warren, Jr.,
// Hacker's Delight (2nd ed.) (Addison Wesley, 2013), 173-174.
long x1 = x >> 32;
long x2 = x & 0xFFFFFFFFL;
long y1 = y >> 32;
long y2 = y & 0xFFFFFFFFL;
long z2 = x2 * y2;
long t = x1 * y2 + (z2 >>> 32);
long z1 = t & 0xFFFFFFFFL;
long z0 = t >> 32;
z1 += x2 * y1;
return x1 * y1 + z0 + (z1 >> 32);
} else {
// Use Karatsuba technique with two base 2^32 digits.
long x1 = x >>> 32;
long y1 = y >>> 32;
long x2 = x & 0xFFFFFFFFL;
long y2 = y & 0xFFFFFFFFL;
long A = x1 * y1;
long B = x2 * y2;
long C = (x1 + x2) * (y1 + y2);
long K = C - A - B;
return (((B >>> 32) + K) >>> 32) + A;
}
}

从Java9开始,它包含在java.lang.math中,可能应该直接调用它。发布源代码只是为了显示“引擎盖下”发生了什么。
isr3a4wc

isr3a4wc4#

假设你有两个龙, x 以及 y ,和 x = x_hi * 2^32 + x_lo ,和 y = y_hi * 2^32 + y_lo .
那么 x * y == (x_hi * y_hi) * 2^64 + (x_hi * y_lo + x_lo * y_hi) * 2^32 + (x_lo * y_lo) .
因此,该乘积的高64位可以如下计算:

long x_hi = x >>> 32;
long y_hi = y >>> 32;
long x_lo = x & 0xFFFFFFFFL;
long y_lo = y & 0xFFFFFFFFL;
long prod_hi = (x_hi * y_hi) + ((x_ hi * y_lo) >>> 32) + ((x_lo * y_hi) >>> 32);
uqjltbpv

uqjltbpv5#

虽然误差是有界的(它最多可以比精确结果小2倍,而且永远不会比精确结果大),但大多数情况下(66%)可接受的解决方案是错误的。这个来自
忽略 x_lo * y_lo 产品
先移后加 x_hi * y_lo 以及 x_lo * y_hi 我的解决方案似乎总是适用于非负操作数。

final long x_hi = x >>> 32;
final long y_hi = y >>> 32;
final long x_lo = x & 0xFFFFFFFFL;
final long y_lo = y & 0xFFFFFFFFL;
long result = x_lo * y_lo;
result >>>= 32;

result += x_hi * y_lo + x_lo * y_hi;
result >>>= 32;
result += x_hi * y_hi;

测试了十亿个随机操作数。应该有一个特殊的测试拐角情况和一些分析。
处理负操作数会更复杂,因为它会禁止使用无符号移位,并强制我们处理中间结果溢出。
如果速度不重要(而且很少),我会选择

BigInteger.valueOf(x).multiply(BigInteger.valueOf(y))
     .shiftRight(64).longValue();
bsxbgnwa

bsxbgnwa6#

上面描述的一些案例是错误的。首先你要问自己你处理什么类型的操作数(有符号/无符号)。
上面的示例中有一个修改后的代码固定为进位标志(将x&y视为无符号64位值):

public static long productHi(long x, long y) {
    final long x_hi = x >>> 32;
    final long y_hi = y >>> 32;
    final long x_lo = x & 0xFFFFFFFFL;
    final long y_lo = y & 0xFFFFFFFFL;
    long result = (x_lo * y_lo) >>> 32;
    long a = x_hi * y_lo;
    long b = x_lo * y_hi;
    long sum = a + b + result;
    long carry = ((a & b) | (~sum & (a ^ b))) >>> 63;
    result = (sum >>> 32) + x_hi * y_hi + (carry << 32);
    return result;
}
56lgkhnf

56lgkhnf7#

您应该看看如何使用biginteger。

相关问题