有没有办法得到二的乘法的高半部分 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中是可能的吗?如果可能,如何实现?
7条答案
按热度按时间xzlaal3s1#
Java9有math.multiplyhigh,根据javadocs的说法,它“返回两个64位因子的128位乘积中最重要的64位。”
vybvopom2#
如果x或y可以是负数,你应该使用hacker's delight函数(henry s。沃伦,《黑客的喜悦》,艾迪生·韦斯利,第2版,图8.2):
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;
}
}
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位可以如下计算:
uqjltbpv5#
虽然误差是有界的(它最多可以比精确结果小2倍,而且永远不会比精确结果大),但大多数情况下(66%)可接受的解决方案是错误的。这个来自
忽略
x_lo * y_lo
产品先移后加
x_hi * y_lo
以及x_lo * y_hi
我的解决方案似乎总是适用于非负操作数。测试了十亿个随机操作数。应该有一个特殊的测试拐角情况和一些分析。
处理负操作数会更复杂,因为它会禁止使用无符号移位,并强制我们处理中间结果溢出。
如果速度不重要(而且很少),我会选择
bsxbgnwa6#
上面描述的一些案例是错误的。首先你要问自己你处理什么类型的操作数(有符号/无符号)。
上面的示例中有一个修改后的代码固定为进位标志(将x&y视为无符号64位值):
56lgkhnf7#
您应该看看如何使用biginteger。