如何在C ++中将64位整数乘以分数，同时最大程度地减少错误? [英] How to multiply a 64 bit integer by a fraction in C++ while minimizing error?

问题描述

给出一个64位(带符号)long long或__int64，您如何将它乘以任意分数，同时又将错误最小化?

Given a 64 bit (signed) long long or __int64, how would you go about multiplying it by an arbitrary fraction while at the same time minimizing error?

三个简单的草图:

int64_t numerator = ...;
int64_t denominator = ...;
int64_t x = ...;

// a, lossy double conversion for large values
double fraction = static_cast<double>(numerator) / static_cast<double>(denominator);
int64_t result = x * fraction;

// b, divide first, problem if denominator value near (or even larger) x
int64_t result = x / denominator;
result *= numerator;

// c, multiply first, problem if multiplication overflows
int64_t result = x * numerator;
result /= denominator;

如果x * n / d在数学上不产生整数，我可以将结果截断为最接近的整数.

I would be fine with truncating the result to the nearest integer if x * n / d mathematically doesn't yield a whole number.

推荐答案

改进提供的答案(这会减少b大时的溢出):

Improving on provided answer (this reduces overflow when b is big):

int64_t muldiv64(const int64_t a, const int64_t b, const int64_t d)
{
    /* find the integer and remainder portions of x/d */
    const int64_t diva = a / d;
    const int64_t moda = a % d;
    const int64_t divb = b / d;
    const int64_t modb = b % d;

    return diva * b + moda * divb + moda * modb / d;
}

无需编写奇怪的代码来避免使用模数运算:编译器可以进行替换，并且您可以拥有更具可读性的代码.

there is no need to write weird code to avoid using the modulus operation: the compiler can do the substitution and you can have a more readable code.

修改: 任何更复杂的代码可能都不值得研究.如果需要更高的精度，可能的好主意是转向128位算术或使用任意精度的整数库(请参见 http ://sourceforge.net/projects/cpp-bigint/)

edit: Any more complicated code is probably not worth to look into. If more precision is needed probably the good idea is moving to 128 bit arithmetic or use arbitrary precision integer libraries (see http://sourceforge.net/projects/cpp-bigint/)

这篇关于如何在C ++中将64位整数乘以分数，同时最大程度地减少错误?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！