c++ - 中間オーバーフローなしで整数を有理数で乗算する

Question

非負の有理数 p/q を表す構造体があります。

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

n有理数に uint64 を掛けて、切り捨てられた整数の結果を得たいと思います。つまり、次のように計算したいと思います。

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

での中間オーバーフローを回避しながらn * r.p。(もちろん、最終結果はオーバーフローする可能性がありますが、これは許容範囲です。)

これどうやってするの？高倍率なしでそれを行う方法はありますか？

(boost::rational を見ましたが、この機能を提供しているようには見えません。)

Answer 1

農民の乗算を使用できます：

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

Answer 2

128 ビットの場合は、カラツバ乗算を使用できます。または、中国剰余定理を使用して (n * rp) mod p1 および mod p2 を表すこともできます。2番目は遅くなる可能性があります。