How to multiply a 64 bit integer by a fraction in C++ while minimizing error? [duplicate]

Question

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.

Answer 1

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.