Multiplying the whole by the rational without intermediate overflow

Question

I have a structure representing a non-negative rational number p / q:

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

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

 uint64_t m = (n * rp)/rq; 

avoiding intermediate overflow in n * rp . (Of course, the end result may overflow, which is acceptable.)

How can i do this? Is there any way to do this without zooming in?

(I was looking at boost :: rational, but it does not seem to provide this function.)

Answer 1

Or 128 bits, and you can use Karatsuba multiplication; or you can use the Chinese break theorem to represent (n * rp) mod p1 as well as mod p2. The second may be slower.

Answer 2

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