Умножение целого числа на рациональное без промежуточного переполнения
У меня есть структура, представляющая неотрицательное рациональное число p / q:
struct rational {
uint64_t p;
uint64_t q; // invariant: always > 0
};
Я хотел бы умножить мой рациональный на uint64 n и получить целочисленный результат, округленный в меньшую сторону. То есть я бы хотел посчитать:
uint64_t m = (n * r.p)/r.q;
избегая промежуточного переполнения в n * r.p, (Конечно, конечный результат может быть переполнен, что является приемлемым.)
Как я могу это сделать? Есть ли способ сделать это без большого умножения?
(Я посмотрел на Boost :: рациональный, но он не предоставляет эту функцию.)
Решение
Ты можешь использовать крестьянское умножение:
// 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;
}
Другие решения
Либо 128-бит, и вы могли бы использовать Карацуба умножение там; или вы можете использовать китайскую теорему об остатках для представления (n * r.p) mod p1, а также mod p2. Второй может быть медленнее.