将整数乘以有理数而没有中间溢出

Question

我有一个表示非负有理数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 :: rational但它似乎没有提供此功能.)

Answer 1

要么是 128 位，你就可以在那里使用Karatsuba乘法；或者您可以使用中国余数定理来表示 (n * rp) mod p1 和 mod p2。第二个可能会慢一些。