4

一部の計算でsと整数のオーバーフローを回避しようとしているlong longので、計算するために以下の関数を考え出しました(a * b) / c（整数の除算を切り捨てるため、順序は重要です）。

 unsigned muldiv(unsigned a, unsigned b, unsigned c)
 {
      return a * (b / c) + (a * (b % c)) / c;
 }

これが期待どおりに機能しないエッジケースはありますか？

4

3 に答える 3

4

編集済み：これは、元の明白なロジックが正しい値のスーパーセットに対して正しいです。c>bそしておそらく他の条件でそれはまだあなたに何も買わない。おそらくあなたは自分の価値観について何か知っているcかもしれませんが、これはあなたが期待するほどには役に立たないかもしれません。a、、bのいくつかの組み合わせcはまだオーバーフローします。

編集：long long厳密なC ++ 98の移植性の理由で回避していると仮定すると、計算を行うためにたまたま整数値を持つに昇格するunsignedことで、約52ビットの精度を得ることができます。double実際、数学を使用doubleすると、3つの積分除算を実行するよりも高速になる場合があります。

于 2012-04-25T19:19:37.660 に答える
4

これはかなりの数のケースで失敗します。最も明白なのは、aが大きい場合であるため、a * (b % c)オーバーフローします。スワッピングaを試してみてくださいb。その場合、、、、およびがすべて大きい場合は失敗aしbますc。a= b= 2^25-1およびc=2 ^ 24で、32ビットの符号なしを考えます。正しい結果は2^26-4ですが、両方ともa * (b % c)オーバーフローb * (a % c)します。でも(a % c) * (b % c)あふれます。

これを一般的に解決する最も簡単な方法は、乗算を拡大することです。これにより、中間積をより高い精度で取得できます。それがない場合は、小さな乗算と除算から合成する必要があります。これは、独自のbigintegerライブラリを実装するのとほとんど同じです。

c署名されていないものがオーバーフローしないように十分に小さいことを保証できる場合は(c-1)*(c-1)、次を使用できます。

unsigned muldiv(unsigned a, unsigned b, unsigned c) {
    return (a/c)*(b/c)*c + (a%c)*(b/c) + (a/c)*(b%c) + (a%c)*(b%c)/c;
}

これにより、実際にはすべてのaとbの「正しい」答えが得られます-（a * b）/ c％（UINT_MAX + 1）

于 2012-04-25T22:14:05.237 に答える
0

オーバーフローを回避するには、事前に除算してから、何らかの係数で事後乗算する必要があります。

aとbの一方（または両方）がcより大きい限り、使用するのに最適な係数はcです。これは、ChrisDoddの関数が行うことです。これは、（（a％c）*（b％c））の最大の中間体を持ち、Chrisが特定するように、（（c-1）*（c-1））以下です。

aとbの両方がc未満であるが、（a * b）がオーバーフローする可能性がある場合（cがワードサイズの制限に近づいた場合など）、使用するのに最適な要素はaです。 2の大きな累乗、乗算と除算をシフトに変換します。単語サイズの半分だけシフトしてみてください。

事前除算を使用してから事後乗算を使用することは、使用可能な長い単語がない場合に長い単語を使用することと同じであることに注意してください。下位ビットを破棄せずに別の用語として追加すると仮定すると、1つの大きな単語ではなく、複数の単語を使用していることになります。

コードを入力させていただきます。

于 2012-05-04T15:15:36.870 に答える