How to multiply a 64 bit integer by a fraction in

问题:

This question already has answers here:

Most accurate way to do a combined multiply-and-divide operation in 64-bit? (10 answers)

Closed 5 years ago.

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?

Three simple sketches:

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;

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

回答1:

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.

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/)

回答2:

You may use the following:

const int64_t q = x / denominator;
const int64_t r = x - q * denominator;
// x = q * denominator + r;
const int64_t result = q * numerator + ((r * numerator) / denominator);

Note: you may get both the quotient and the remainder at once with std::div family.

Note: As pointed by Sander De Dycker, there are still problems when
r * numerator / denominator overflows
and with the special case x = INT64_MIN, denominator = -1 where x / denominator overflows.

回答3:

More or less copied from here, this seems to make the most sense to me:

int64_t muldiv64(const int64_t x, const int64_t n, const int64_t d)
{
    /* find the integer and remainder portions of x/d */
    const int64_t div = x / d;
    const int64_t mod = x % d;

    return div * n + (mod * n) / d;
}