如何精确地对64位整数进行乘除运算? [英] How can I multiply and divide 64-bit ints accurately?

问题描述

我有一个C函数:

int64_t fn(int64_t a, int32_t b, int32_t c, int32_t d)
{
    /* should return (a * b * c)/d */   
}

a可能接近INT64_MAX，但最终结果不会溢出，例如，如果b = 1，c = d =40.但是，我在弄清楚如何计算该值时遇到了麻烦，因此我永远不会丢失要舍入的数据(首先进行除法)或中间结果溢出.

It is possible for a to be near INT64_MAX, but for the final result not to overflow, for instance if b = 1, c = d = 40. However, I am having trouble figuring out how to compute this so that I never lose data to rounding (by doing the division first) or have an intermediate result overflow.

如果我可以访问足够大的数据类型以适合a，b和c的整个乘积，那么我只需要对该类型进行数学运算然后截断即可，但是有某种方法我可以不用大整数来做到这一点?

If I had access to a large enough datatype to fit the whole product of a, b, and c, I would just do the math in that type and then truncate, but is there some way I can do this without big integers?

推荐答案

用|r| < |d|编写a = q*d + r(我假设d != 0，否则计算毫无意义).然后(a*b*c)/d = q*b*c + (r*b*c)/d.如果q*b*c溢出，无论如何整个计算都会溢出，因此您不在乎，或者您必须检查溢出. r*b*c可能仍然会溢出，因此我们再次使用相同的方法来避免溢出，

Write a = q*d + r with |r| < |d| (I'm assuming d != 0, otherwise the computation is meaningless anyway). Then (a*b*c)/d = q*b*c + (r*b*c)/d. If q*b*c overflows, the entire computation would overflow anyway, so either you don't care, or you have to check for overflow. r*b*c might still overflow, so we again use the same method to avoid overflow,

int64_t q = a/d, r = a%d;
int64_t part1 = q*b*c;
int64_t q1 = (r*b)/d, r1 = (r*b)%d;
return part1 + q1*c + (r1*c)/d;

这篇关于如何精确地对64位整数进行乘除运算?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！