【小ネタ】あなたの平均値の計算、本当にできていますか？

免責事項

本記事で扱っているのはあくまでかなり極端的なケースであって、普段の開発ではそこまで神経質になる必要はないと思います；そのため「こう言うこともあるね」とどこか頭の中に入れて、実際このようなバグが発生したとき思い出していただければと思いますので「小ネタ」として書かせていただきます。

うわっ…私の平均値、膨らみすぎ…？

安心してください、私は別にこの記事で平均値と中央値の違いとかみたいなセコいことを言うつもりはありません、あくまで我々が日常で使ってる「平均値」のことです。$(x + y) \div 2$ のことです。

ところで上記の数式の通り、我々は平均値の定義¹を、二つの数字を足して 2 で割る、という風に教わったはずかと思います。そのため我々は基本このように平均値メソッドを書くことがほとんどかと思いますね。筆者は iOS エンジニアなので、ここは Swift のプログラム²を書きますが他の言語も似たような実装になるかと思います：

func average(x: Int, y: Int) -> Int {
    return (x + y) / 2
}

実際このプログラムを回してみて、例えば 1 と 3 の平均値をこれで回してみれば、確かに正しい平均値の 2 が得られます：

average(x: 1, y: 3) // 2

何も問題ないじゃん？と思いますよね。

では、4611686018427387903 と 4611686018427387905 の平均値はどうでしょう？実際回してみましょうか

average(x: 4611686018427387903, y: 4611686018427387905) // ???

さて、ここは言語や処理系によって違いが出るところですかね？例えば Swift ならここではプログラムが EXC_BAD_INSTRUCTION エラーで落ちます；C ならここで 0 が出るかもしれませんし、他に -4611686018427387904 が出る言語もあるかもしれません。どのみち、64 bit の処理系なら、おそらくここで正解の 4611686018427387904 が出る言語はそうそうないでしょう。

お気づきでしょうか？そうです。プログラミングの計算と、実際の数学の計算と大きな違いがあります：数字自体の制限です。

64 bit の処理系なら、Int の最大値は 9223372036854775807 です。ところで 4611686018427387903 と 4611686018427387905 を愚直に足してしまうと 9223372036854775808 になり、Int の極限を超えちゃってオーバーフローになります。そのため結果が Int で正しく表現できず、Swift ならここで落ちますし、C 言語ならここで 0 になってしまいます。

ちなみに記憶が曖昧ですが、確か Java が長い間このバグが潜んでいたことがあったはずです³。

では平均値をどう求めればいいか

平均値をグラフの考え方で考えてみれば、低い方の数字に、両方の数字の差の半分を足す、という考え方もできます。つまりコードにするとこんな感じです：

func average(x: Int, y: Int) -> Int {
    return x + ((y - x) / 2)
}

上記のコードは暗黙的に x が y より小さい、という前提条件が入ってるように見えますが、実際は符号が着くおかげで、y の方が小さかったら y - x もマイナスになって結果正しい平均値が得られます⁴。

average(x: 3, y: 1) // 2

そしてこの方法の一番のメリットは、途中の計算結果が x と y を超えることがないので、x と y さえ制限を超えなければ正しい平均値が求められます。実際先ほどの Java のバグの件も、このように修正を入れてたはずです。ですので今後は平均値を求めるときは

(x + y) \div 2

ではなく、

x + ((y - x) \div 2)

で求めましょう！

ちょっと待って…本当にそれでいいの？？

先ほど私

途中の計算結果が x と y を超えることがない

と言いましたよね？あれは嘘です。超えることがあるんです。

これまで私が挙げてきた例は全て符号付き整数型を使っていましいたが、具体的な数字は全て正数です。ところが負数が入ってきたらどうなるのかな？

答えは、両方とも正数もしくは両方とも負数の場合、確かに $x - y$ の差（の絶対値）が x と y を超えることはないが、逆に片方が正数で片方が負数の場合、その差は逆に x と y を超えます。例えば：

average(a: 4611686018427387905, b: -4611686018427387905) // ???

上記の場合、逆に $x + ((y - x) \div 2)$ で計算するとオーバーフローが発生します。この場合、むしろ普通の和を 2 で割る方法で求めれば正しい結果が得られます。

まとめると：

	平均値
$x$ と $y$ が同じ符号	$x + ((y - x) \div 2)$
$x$ と $y$ が違う符号	$(x + y) \div 2$

です。

後書き

免責事項で書きましたとおり、本記事はあくまでかなり極端的なケースであって、普段の開発ではそこまで神経質になる必要はないと思います。

---

1. 数字が三つ以上出ると話がややこしくなるので、ここはひとまず二つの数字の平均値を扱います。 ↩

2. 本当は割り算があるので整数はあまりよくないですが、本記事もひとまず理解がしやすいためにあえて整数を選びました ↩

3. 以前どこかで Java かなんかのシステムがずっとこの実装で平均値を求めていて、どこかでバグって多くのデバイスに影響を及ぼした的な記事を読んだ記憶がありますが、はっきりと出自が思い出せないので、知ってる方がいらっしゃいましたら補足できると嬉しいです。 @naskya さんと @fujitanozomu さんのおかげで、そのバグは Java の二分探索の実装にあったことが判明しました。詳しくはコメント欄をご参照ください。 ↩

4. 正確には、x + ((y - x) / 2) の足し算基準値に使われる x が大きい方か小さい方かによって、演算精度の影響による誤差が出て違う結果になることがあり得ます。詳しくはコメント欄をご参照ください。 ↩