（a * b）/ c MulDiv并处理中间乘法的溢出 [英] (a * b) / c MulDiv and dealing with overflow from intermediate multiplication
问题描述
我需要做以下算术运算：
I need to do the following arithmetic:
long a,b,c;
long result = a*b/c;
虽然结果保证适合 long
While the result is guaranteed to fit in long, the multiplication is not, so it can overflow.
我尝试逐步（先乘后除），然后通过拆分来处理溢出。 a * b 转换为最大大小为4的int数组的中间结果（就像BigInteger使用其 int [] mag 变量）。
I tried to do it step by step (first multiply and then divide) while dealing with the overflow by splitting the intermediate result of a*b into an int array in size of max 4 ( much like the BigInteger is using its int[] mag variable).
在这里，我陷入了分裂。我无法理解进行精确除法所需的按位移位。我需要的只是商数（不需要余数）。
Here I got stuck with the division. I cannot get my head around the bitwise shifts required to do a precise division. All I need is the quotient (don't need the remainder).
假设的方法是：
public static long divide(int[] dividend, long divisor)
此外，我不考虑使用 BigInteger ，因为这部分代码需要快速运行（我想坚持使用基本体和基本体数组）。
Also, I am not considering using BigInteger as this part of the code needs to be fast ( I would like to stick to using primitives and primitive arrays).
任何帮助将不胜感激！
编辑：
我不打算实现整个 BigInteger 我自己。我正在尝试解决一个特定的问题（ a * b / c ，其中 a * b 可以溢出）比使用通用 BigInteger 更快。
I am not trying to implement the whole BigInteger myself. What I am trying to do is to solve a specific problem (a*b/c, where a*b can overflow) faster than using the generic BigInteger.
Edit2：如果可以在聪明的方式是，一点都没有溢出，评论中出现了一些技巧，但我仍然在寻找正确的技巧。
It would be ideal if it could be done in a clever way, by not getting overflow at all, some tips surfaced in the comments, but I am still looking for one that is correct.
更新：
我尝试将BigInteger代码移植到我的特定需求，而没有创建对象，并且在第一次迭代中，与使用BigInteger相比，我的速度提高了约46％（在我的开发中
Update: I tried to port BigInteger code to my specific needs, without object creation, and in the first iteration, I got ~46% improvement in speed comparing to using BigInteger (on my development pc).
然后我尝试了一些修改过的@David Eisenstat解决方案，这给了我约56％的费用（我从 Long中随机运行了100_000_000_000个输入。 MIN_VALUE 到 Long.MAX_VALUE ）与BigInteger相比，运行时间减少了2倍以上（与我使用的BigInteger算法相比，减少了18％）
Then I tried a bit modified @David Eisenstat solution, which gave me ~56 % (I ran 100_000_000_000 random inputs from Long.MIN_VALUE to Long.MAX_VALUE) reduced run times(more than 2x) comparing to BigInteger (that is ~18% compared to my adapted BigInteger algo).
关于优化和测试的迭代将会更多，但是在这一点上，我认为我必须接受这个答案是最好的。
There will be more iterations on optimization and testing, but at this point, I think I must accept this answer as the best.
推荐答案
我一直在修补一种方法（ 1）将 a 和 b 乘以21位肢的学校算法（2）进行长除法 c ，使用 long 存储低位。我不知道它是否可以与标准的长距离比赛竞争，但是为了您的享受，
I've been tinkering with an approach that (1) multiplies a and b with the school algorithm on 21-bit limbs (2) proceeds to do long division by c, with an unusual representation of the residual a*b - c*q that uses a double to store the high-order bits and a long to store the low-order bits. I don't know if it can be made to be competitive with standard long division, but for your enjoyment,
public class MulDiv {
public static void main(String[] args) {
java.util.Random r = new java.util.Random();
for (long i = 0; true; i++) {
if (i % 1000000 == 0) {
System.err.println(i);
}
long a = r.nextLong() >> (r.nextInt(8) * 8);
long b = r.nextLong() >> (r.nextInt(8) * 8);
long c = r.nextLong() >> (r.nextInt(8) * 8);
if (c == 0) {
continue;
}
long x = mulDiv(a, b, c);
java.math.BigInteger aa = java.math.BigInteger.valueOf(a);
java.math.BigInteger bb = java.math.BigInteger.valueOf(b);
java.math.BigInteger cc = java.math.BigInteger.valueOf(c);
java.math.BigInteger xx = aa.multiply(bb).divide(cc);
if (java.math.BigInteger.valueOf(xx.longValue()).equals(xx) && x != xx.longValue()) {
System.out.printf("a=%d b=%d c=%d: %d != %s\n", a, b, c, x, xx);
}
}
}
// Returns truncate(a b/c), subject to the precondition that the result is
// defined and can be represented as a long.
private static long mulDiv(long a, long b, long c) {
// Decompose a.
long a2 = a >> 42;
long a10 = a - (a2 << 42);
long a1 = a10 >> 21;
long a0 = a10 - (a1 << 21);
assert a == (((a2 << 21) + a1) << 21) + a0;
// Decompose b.
long b2 = b >> 42;
long b10 = b - (b2 << 42);
long b1 = b10 >> 21;
long b0 = b10 - (b1 << 21);
assert b == (((b2 << 21) + b1) << 21) + b0;
// Compute a b.
long ab4 = a2 * b2;
long ab3 = a2 * b1 + a1 * b2;
long ab2 = a2 * b0 + a1 * b1 + a0 * b2;
long ab1 = a1 * b0 + a0 * b1;
long ab0 = a0 * b0;
// Compute a b/c.
DivBy d = new DivBy(c);
d.shift21Add(ab4);
d.shift21Add(ab3);
d.shift21Add(ab2);
d.shift21Add(ab1);
d.shift21Add(ab0);
return d.getQuotient();
}
}
public strictfp class DivBy {
// Initializes n <- 0.
public DivBy(long d) {
di = d;
df = (double) d;
oneOverD = 1.0 / df;
}
// Updates n <- 2^21 n + i. Assumes |i| <= 3 (2^42).
public void shift21Add(long i) {
// Update the quotient and remainder.
q <<= 21;
ri = (ri << 21) + i;
rf = rf * (double) (1 << 21) + (double) i;
reduce();
}
// Returns truncate(n/d).
public long getQuotient() {
while (rf != (double) ri) {
reduce();
}
// Round toward zero.
if (q > 0) {
if ((di > 0 && ri < 0) || (di < 0 && ri > 0)) {
return q - 1;
}
} else if (q < 0) {
if ((di > 0 && ri > 0) || (di < 0 && ri < 0)) {
return q + 1;
}
}
return q;
}
private void reduce() {
// x is approximately r/d.
long x = Math.round(rf * oneOverD);
q += x;
ri -= di * x;
rf = repairLowOrderBits(rf - df * (double) x, ri);
}
private static double repairLowOrderBits(double f, long i) {
int e = Math.getExponent(f);
if (e < 64) {
return (double) i;
}
long rawBits = Double.doubleToRawLongBits(f);
long lowOrderBits = (rawBits >> 63) ^ (rawBits << (e - 52));
return f + (double) (i - lowOrderBits);
}
private final long di;
private final double df;
private final double oneOverD;
private long q = 0;
private long ri = 0;
private double rf = 0;
}
这篇关于（a * b）/ c MulDiv并处理中间乘法的溢出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
