Menu
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.)
513
Ideally the safest approach is to avoid signed integer overflow entirely. For example, instead of multiplying two signed integers, you can convert them to unsigned integers, multiply the unsigned values, then test whether the result is in signed range.
So overflow can be detected by checking Most Significant Bit(MSB) of two operands and answer. But Instead of using 3-bit Comparator Overflow can also be detected using 2 Bit Comparator just by checking Carry-in(C-in) and Carry-Out(C-out) from MSB's.
Use 64-bits integers. One very good way to prevent integer overflows is to use int64_t to implement integers. In most case, 64-bits ints will not commit overflow, unlike their 32-bits counterparts. There is actually very few downsides in using int64_t instead of int32_t .
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;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
