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

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.

You may alternatively use a *BigInt* library and then manage the overflow manually to fit in your `int64_t`. — Jarod42, Aug 07 '14 at 12:34
@jbutler483 - Title is a dup. Question body not so, I'd say. — Martin Ba, Aug 07 '14 at 12:36
see http://stackoverflow.com/questions/8733178/most-accurate-way-to-do-a-combined-multiply-and-divide-operation-in-64-bit — Sander De Dycker, Aug 07 '14 at 12:45

Jarod42 · Answer 1 · 2014-08-07T13:39:24.937

4

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.

edited Aug 07 '14 at 13:39

answered Aug 07 '14 at 12:43

Jarod42

203,559
14
181
302

better still make it an inline function `int64_t muldiv64(int64_t x, int64_t numerator, int64_t denominator)` – Ben Aug 07 '14 at 12:47
Interesting. What'd you say: Better `r = x%d` or your `r = x - q * d`? – Martin Ba Aug 07 '14 at 12:48
2

Are the semantics of `%` standardised for negative numbers yet? – Ben Aug 07 '14 at 12:50
@Ben - [Seems](http://stackoverflow.com/questions/7594508/modulo-operator-with-negative-values) C++11 has defined it. – Martin Ba Aug 07 '14 at 12:54
@MartinBa: It should be identical. (Maybe one is more efficient than the other). – Jarod42 Aug 07 '14 at 12:59
how about input like `x = INT64_MAX - 1`, `numerator = 2`, `denominator = INT64_MAX` ? Your code will set `result` to `0`, while it should be `1`. – Sander De Dycker Aug 07 '14 at 13:04
or better yet, input like `x = INT64_MIN`, `numerator = -1`, `denominator = -1` will generate a core dump. – Sander De Dycker Aug 07 '14 at 13:13

score 2 · Answer 2 · edited May 23 '17 at 12:32

2

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

edited May 23 '17 at 12:32

Community

1
1

answered Aug 07 '14 at 12:46

Martin Ba

37,187
33
183
337

Tested it on `int8_t` for simplicity, it overflows on `x=3, n=86, d=87`. So I believe you can find 64-bit equivalence. – goodvibration Jul 26 '20 at 08:06

pqnet · Accepted Answer · 2014-08-08T17:05:06.440

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

edited Aug 08 '14 at 17:05

answered Aug 07 '14 at 13:06

pqnet

6,070
1
30
51

2

Note that there are the same issues than the previous answer for cases where `a < d`, `b < d` but `a * d` overflows. It just solves issues of other answer when `b >= d`. – Jarod42 Aug 07 '14 at 13:53
@Jarod42 yes, i didn't mean for it to be the best possibility, just an improvement over the previous solutions. If a more accurate solution is needed probably it is a good idea to use an arbitrary precision integer library such as http://sourceforge.net/projects/cpp-bigint/ – pqnet Aug 07 '14 at 14:35

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

3 Answers3

Linked