高速逆平方根計算アルゴリズム
Fast inverse square root (高速逆平方根計算アルゴリズム)は、コンピュータのゲームや各種の高速の３次元グラフィックスで用いられているアルゴリズムで、 与えられたXに対する1/√X の近似値を高速計算します。1999年、 Quake III Arena というゲームソフトウエアで、プログラマーの John Carmackらが、相手を狙って撃つ際の入射角、反射角やその光路や影を計算する際に初めて採用したということです。ゲームに限らず、数値計算のプログラミングをなさっている方には興味あるテクニックです。おなじみのニュートン法を使っています。Quake III Arena のソースコードが明らかになったのは、だいぶ後になってからのことですが、現在では、広く利用されています。
ごく最近、Facebook の Delphi developer ページで、このアルゴリズムが話題になりました。そこで紹介されていたのは、以下の約20分のYoutube動画です。 ほぼこれで、全貌がわかります。興味深いです。
https://www.youtube.com/watch?v=p8u_k2LIZyo
このコードを Delphi のPascalコードで書いたら.... というのが、Facebook ページのメンバーの主要な問題意識です。この話題は、ちょうど、Emcarderoのブログに出ました。
https://blogs.embarcadero.com/fast-inverse-square-root-in-delphis-object-pascal/
この記事のなかにソースコードも出ています。すごく簡単です。これを見れば誰でもすぐ作れるでしょう。マガジンご購読の皆様には、Windows 用のアプリケーションをプレゼントいたします。
使い方は簡単。画面の左の白いところに数字を入れて、Calculate!ボタンを押すと、その平方根の逆数が右のボックスに表示されます。そもそもがコンピュータが速い時代なので、アルゴリズムの速さは体感にしくいかも。大量のデータを一気に計算して、グラフとか画像にしてみるようなことをすれば、スピード感、感じられるかも。
ダウンロード
以下をクリックしてダウンロードできます。
ここから先は
月刊「群盲評象」（試読ご希望の方向け）
現代は科学が進歩した時代だとよく言われます。知識を獲得するほど新たな謎が深まり、広大な未知の世界が広がります。知は無知とセットになっていま…
いつもお読みくださり、ありがとうございます。もし私の記事にご興味をお持ちいただけるようでしたら、ぜひマガジンをご検討いただけないでしょうか。毎日書いております。見本は「群盲評象ショーケース（無料）」をご覧になってください。