Java 中 (a*b)/c 的高效 63 位长计算

Question

我想以最有效的方式在Java中计算

(a*b)/c

，其中：

• a

  、

  b

  和

  c

  是无符号

  long

  值（保证适合 63 位，即符号位为零）
• 结果也保证适合 63 位
• 乘积

  (a*b)

  很可能会因常规

  long

  乘法而溢出

最有效的计算方法是什么？我有一个具有

BigInteger

转换的工作解决方案，但我正在寻找更快的东西（最小时钟周期，最好是零内存分配）

Answer 1

在数学上，

(a*b)/c

等于

(a/c)*b

和

(b/c)*a

。仅使用整数除法最准确的结果是将

a

和

b

中较大的一个除以

c

，然后乘以另一个：

long result = a > b ? (a / c * b) : (b / c * a);

虽然这将尽可能快地得到它，但它的准确性受到除法其余部分截断的限制。您可以通过在除法之前添加

c

的一半来模拟舍入，从而以很小的性能成本提高精度：

long result = a > b ? ((a + c/2) / c * b) : ((b + c/2) / c * a);