忍者ブログ

Memeplexes

プログラミング、3DCGとその他いろいろについて

バイナリサーチで√2を計算する

バイナリサーチで√2を計算するアニメーションプログラムを作りました。計算の様子が目で見てわかるのは楽しいですね。


デモプログラム

操作方法

Startボタン:シミュレーションをスタートします。もう一度押すと一時停止します。

Resetボタン:シミュレーションをリセットします。

解説

これは√2を計算するプログラムです。初めの値は0なのですが、次に1、1.5、1.25と√2(=1.414213...)に近づいていきます。初めは大胆に動き、時間がたつにつれて動きが慎重になっていくのです(1ステップごとに動きが半分になっていきます。バイナリサーチというやつです)。

どうしてこのように何ステップもかけて計算するのかというと、√2という数字は「2乗すると2になる」という間接的に定義されており直接求めるのが難しいからです。よって、毎ステップごとに数字を2乗して2より大きいか小さいかを判定して、大きければ小さくし小さければ大きくして、値を√2に近づけていくのです。

このやり方は数字をあてずっぽうに2乗して比べるのとはわけが違います。範囲を毎回半分に絞っているため、ねずみ算的に精度がよくなっていくのです。今回は√2でしたが、もっと複雑な数字の√も大して必要な計算が増えません。これがバイナリサーチの素晴らしいところです。

人間の場合はどうか?

この計算方法は広い範囲の中から急速に回答を見つける効率の良いアルゴリズムです。なら自然淘汰によってある程度最適化された人間も似たようなことをしているかもしれません。

人間の場合、子供の頃の行動が大胆で変なものが多いのに対し、大人になると行動のブレが減るというのが今回のアルゴリズムに似ていると言えるかもしれません。子供のめちゃくちゃな行動は良い結果をもたらす行動の探索であり、これなしには良い解にたどり着けないのかもしれません。そして大人になると、どのような行動をすればよい結果が出るのかわかっているため、遊ぶことが少なくなるというわけです。

あるいは文明全体についても同じようなことが言えそうです。新しい技術が開発されると、たいていめちゃくちゃな使われ方がするのですが、次第に落ち着いて最適な使われ方のみが残ります。

ただしこれは必ずしも良いことではないかもしれません。つまり、頭を使わなくても物事が上手くいってしまうため、頭が悪くなってしまうかもしれません(実際、良い条件にたどり着くと脳が退化して消えてしまうホヤがいたはずです)。私としては最適に見える方法が発見されたとしても、めちゃくちゃなやり方を検証する機運が残ってほしいと思います。

拍手[0回]

PR