4

平均値を計算するとき、start+(end-start)/2 は (start+end)/2 とは異なり、後者はオーバーフローを引き起こす可能性があると聞きました。最初のオーバーフローが発生しないのに、この 2 番目のオーバーフローが発生する理由がよくわかりません。オーバーフローを回避できる数式を実装するための一般的な規則は何ですか。

4

4 に答える 4

12

最大整数値が 10 のコンピューターを使用していて、5 と 7 の平均を計算したいとします。

最初の方法 (begin + (end-begin)/2) は、

5 + (7-5)/2 == 5 + 2/2 == 6

2 番目のメソッド (begin + end)/2 はオーバーフローを引き起こします。これは、中間の 12 の値が、許容される最大値の 10 を超えており、別のものに「ラップオーバー」するためです (符号なしの数値を使用している場合は、通常はラップバックします)。ゼロですが、数字が署名されている場合は、負の数になる可能性があります!)。

12/2 => overflow occurs => 2/2 == 1

もちろん、実際のコンピューターでは整数は 10 ではなく 2^32 のような大きな値でオーバーフローしますが、考え方は同じです。残念ながら、私が知っているオーバーフローを取り除く「一般的な」方法はなく、使用している特定のアルゴリズムに大きく依存します。そして、イベントはさらに複雑になります。内部で使用している数値型に応じて異なる動作が発生する可能性があり、オーバーフローとアンダーフローに加えて、他の種類の数値エラーについて心配する必要があります。

于 2012-06-04T13:48:51.243 に答える
5

両方の数式がオーバーフローしますが、状況が異なります。

  • 式の(start+end)一部は、とが両方とも範囲の同じ側 (つまり、両方とも正または両方とも負) の整数制限に近い(start+end)/2場合にオーバーフローします。startend
  • が正で負の場合、式の(end-start)一部start+(end-start)/2がオーバーフローし、両方の値が表現可能な整数値のそれぞれの端に近くなります。startend

「一般的な」ルールはありません。ケースバイケースで行います。式の一部を見て、オーバーフローを引き起こす可能性のある状況を考え、それを回避する方法を考え出します。たとえばstart+(end-start)/2、同じ符号で値を平均するときに、オーバーフローを回避するために数式を表示できます。

これは難しい方法です。簡単な方法は、中間結果に大容量の表現を使用することです。たとえば、long long代わりにを使用intして中間計算を行い、int完了時にのみ結果をコピーして戻す場合、最終結果が に収まると仮定してオーバーフローを回避できますint。

于 2012-06-04T13:57:16.623 に答える
1

整数を扱う場合、そのような戦略を採用する場合、おそらく整数オーバーフローが気になります。

式を使用しb+(b-a)/2て確認したいことに注意してくださいa <= b。そうしないと、可能な値の範囲の下限でまったく同じ問題が発生する可能性があります。について考えてみてくださいa/2+b/2。ただし、このアプローチには他にも欠点があります。

浮動小数点数を扱う場合、壊滅的なキャンセルという別の問題が発生します。浮動小数点表現の有効桁数が限られているため、大きな数を加算すると精度が失われます (これが単なる中間ステップであっても)。

この数値安定性の問題に対処するには、たとえば、このアルゴリズムを使用できます ( wikipediaから少し変更):

def online_mean(data):
  n = 0
  mean = 0

  for x in data:
    n = n + 1
    delta = x - mean
    mean = mean + delta/n

  return mean

上で提示された式と何らかの関係があるように感じました...

于 2012-06-04T13:58:42.253 に答える
0

二分探索では、次のコードを書きます。

if(start > end){
   return;
}
int mid = start + (end - start) / 2;

を使用start + (end - start) / 2することで、@dasblinkenlight が指摘する問題を回避できます。

を使用する(start + end) / 2と、dasblinkenlight で示されるようにオーバーフローします

于 2013-08-19T06:00:58.080 に答える