高速逆平方根アルゴリズムのすべての知識

 (github.com/francisrstokes)
5 ポイント 投稿者 GN⁺ 2024-06-03 | 2件のコメント | WhatsAppで共有

高速逆平方根アルゴリズムのすべて

アルゴリズム

  • 高速逆平方根アルゴリズムは、Quake 3 のソースコードで有名になったアルゴリズムで、John Carmack が使用していた。
  • このアルゴリズムは、浮動小数点のビットを操作して逆平方根を高速に計算する。
  • コード例: 
    float Q_rsqrt(float number) {
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y = number;
  i = *(long*)&y;              // 부동 소수점 비트 수준 해킹
  i = 0x5f3759df - ( i >> 1 ); // 마법의 상수
  y = *(float*)&i;
  y = y * ( threehalfs - ( x2 * y * y ) );  // 1차 반복

  return y;
}

32ビット浮動小数点: 表現

  • IEEE-754 32ビット浮動小数点は、3つの構成要素から成る:
    • 符号: 1ビットで、数値が正か負かを表す。
    • 指数: 8ビットで、数値の範囲を決定する。
    • 仮数: 23ビットで、範囲内での数値の位置を指定する。
  • 実際の値は次のように計算される: 
    N = -1^S * 2^(E-127) * (1 + M/2^23)

32ビット浮動小数点: ビット解釈

  • 浮動小数点の内部表現は、通常はプログラマにとって重要ではない。
  • しかし、この表現をよく理解すれば効率的なアルゴリズム設計が可能になる。
  • 浮動小数点のビットパターンを整数として解釈すると、対数関数の近似値になる。 
    log2(x) ≈ Ix / L - B

ニュートン法

  • 初期近似値を改善するために、ニュートン法 (Newton's method) を使用する。
  • ニュートン法は、与えられた関数の近似値を反復的に改善するアルゴリズムである。
  • コード例: 
    y = y * ( threehalfs - ( x2 * y * y ) ); // 1차 반복

結論

  • このアルゴリズムは、浮動小数点システムの内部にある数学的な詳細を深く理解し、コンピュータ上で高速に実行できる演算を活用して設計されている。
  • アルゴリズムの起源は定かではないが、非常に効率的でよく設計されたエンジニアリングの一例である。

GN⁺の意見

  • 歴史的重要性: このアルゴリズムは、当時のハードウェア制約を克服するために考案された革新的な方法である。
  • 教育的価値: 浮動小数点の内部構造と数学的原理を理解するうえで大いに役立つ。
  • 現代的な適用: 現代のハードウェアでは必要性が低いかもしれないが、アルゴリズムの原理は今なお有用である。
  • 最適化の可能性: アルゴリズムの定数値は最適化できる可能性があり、さらなる研究の余地がある。
  • 批判的視点: 現代のハードウェアではより良い方法があるかもしれないため、常に最新技術と比較してみることが重要である。

関連記事

2件のコメント

 
joyfui 2024-06-03

忘れた頃にまた上がってくる不思議なコード…w
 
GN⁺ 2024-06-03
Hacker Newsのコメント

  • SSE命令のサポート: 1999年以降に製造されたコンピューターはSSE命令セットをサポートしており、_mm_rsqrt_ps 命令によって高速に逆平方根を計算できる。

  • 現代ハードウェアの進歩: 現代のハードウェアでは逆平方根の計算はCPU上で高速に実行でき、すべての浮動小数点演算をGPUにオフロードしているというのは誤解である。

  • MMIX実装: MMIX言語で逆平方根計算を実装したサンプルコードがある。このコードは元の数値が 2^-1021 より大きいと仮定している。

  • 式の誤植: 浮動小数点の式に誤植がある。(-1)^S に修正すべきである。

  • 対数の解釈: 生のビットパターンを解釈することは、対数の区分線形近似ではない。データポイント間の線は実際には存在しない。

  • Wikipedia参照: この関数とその歴史についての良い議論がWikipediaにある。Wikipediaリンク

  • GitHubコード集: 関連するいくつかのコードをGitHubにまとめてある。GitHubリンク

  • StackOverflow参照: 最適化された低精度近似についてのStackOverflowの質問も参考になる。StackOverflowリンク

  • 3Dエンジン最適化の経験: Quake以前に3Dエンジンを構築しながら最適化の経験を積み、アルゴリズム最適化が常に勝つことを学んだ。

  • YouTube動画のおすすめ: このテーマに関する興味深い動画がある。YouTubeリンク

  • 生産性を奪う時間泥棒: このテーマにハマってしまい、生産的な時間をかなり奪われた。

  • 最適なマジックナンバー: 有名なコードスニペットのマジックナンバーは最適な定数ではない。より良い定数を見つけることが可能で、Jupyter Notebookを使って最適なマジックナンバーを探せる。