Multiplying integer by rational without intermediate overflow

Question

I have a struct representing a nonnegative rational number p/q:

struct rational {
    uint64_t p;
    uint64_t q; // invariant: always > 0
};

I would like to multiply my rational by a uint64 n and get an integer result, rounded down. That is, I would like to calculate:

uint64_t m = (n * r.p)/r.q;

while avoiding intermediate overflow in n * r.p. (Of course the final result may overflow, which is acceptable.)

How can I do this? Is there a way to do it without a high-multiply?

(I looked at boost::rational but it does not appear to provide this feature.)

Calculate the rational number `n / r.q`, and reduce it to its lowest form, then multiply that by `r.p`. — Barmar, Aug 12 '16 at 19:57
@DanielG, Barmar: Neither of these help if `p == n` and `p < q` but `n * p > q`. — lorro, Aug 12 '16 at 20:00
This problem annoys me, it's so simple in x64 assembly but there's no reasonable way to write it down in C. — harold, Aug 12 '16 at 20:04
Related: http://www.codeproject.com/Articles/9670/Scaling-bit-integers — Ben Voigt, Aug 12 '16 at 20:08
@harold Most compilers now have the high-multiply intrinsic. But not for the double-width divide. — Mysticial, Aug 12 '16 at 20:15

score 1 · Answer 1 · answered Aug 12 '16 at 20:31

You can use peasant multiplication:

// requires 0 < c < 2^63
// returns (a * b) / c.
uint64_t multDiv(uint64_t a, uint64_t b, uint64_t c) {
  uint64_t rem = 0;
  uint64_t res = (a / c) * b;
  a = a % c;
  // invariant: a_orig * b_orig = (res * c + rem) + a * b
  // a < c, rem < c.
  while (b != 0) {
    if (b & 1) {
      rem += a;
      if (rem >= c) {
        rem -= c;
        res++;
      }
    }
    b /= 2;
    a *= 2;
    if (a >= c) {
      a -= c;
      res += b;
    }
  }
  return res;
}

score 0 · Answer 2 · answered Aug 12 '16 at 19:57

0

Either 128-bits and you might use Karatsuba multiplication there; or you might use the Chinese Remainder Theorem to represent (n * r.p) mod p1 and also mod p2. The second might be slower.

answered Aug 12 '16 at 19:57

lorro

10,687
23
36

Multiplying integer by rational without intermediate overflow

2 Answers2