Как умножить 64-битное целое число на дробь в C++ при минимизации ошибок?

Question

Дано 64 бита (подписано) long long или же __int64Как бы вы пошли на умножение его на произвольную дробь при одновременном минимизации ошибки?

Три простых наброска:

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 математически не дает целого числа.

Answer 1

Улучшение предоставленного ответа (это уменьшает переполнение, когда b большой):

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;
}

нет необходимости писать странный код, чтобы избежать использования операции модуля: компилятор может выполнить подстановку, и вы можете получить более читаемый код.

редактировать: любой более сложный код, вероятно, не стоит изучать. Если требуется большая точность, вероятно, хорошая идея - перейти на 128-битную арифметику или использовать целочисленные библиотеки произвольной точности (см. http://sourceforge.net/projects/cpp-bigint/).

Answer 2

Вы можете использовать следующее:

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

Примечание: вы можете получить как частное, так и остаток одновременно с std::div семьи.

Примечание: как отметил Сандер Де Дайкер, проблемы все еще
r * numerator / denominator переполнение
и с особым случаем x = INT64_MIN, denominator = -1 где x / denominator переполняется.

Answer 3

Более или менее скопированный отсюда, мне кажется, это имеет смысл:

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;
}