高速逆平方根(fast inverse square root)のアルゴリズム解説 - 滴了庵日録

高速逆平方根とは？ C言語のコード 検証 アルゴリズムの要点 [1] 逆平方根の計算を対数・指数の計算に置き換える [2] 浮動小数点型の内部表現を利用した対数・指数の近似計算 [2.1] 対数の近似 [2.2] σの最適値 [2.3] 整数型での解釈 [2.4] 逆平方根の計算とマジックナンバー0x5F3759DF [3] ニュートン法による収束で精度アップ 感想 高速逆平方根とは？ 高速逆平方根(fast inverse square root)とは、平方根の逆数 を高速に計算するアルゴリズムです。平方根の逆数は逆平方根とも呼ばれます。逆平方根はベクトルの正規化などに用いられるので、これを高速に計算できるアルゴリズムには大きなご利益があります。 参照： Fast inverse square root - Wikipedia C言語のコード 高速逆平方根の関数を示します。0x5F375

[boxshiitake]

謎の数字が決め打ちされてるアルゴリズムすき

[sqrt]

謎のマジックナンバーが入ってる変態アルゴリズム大好きなんだけど、そういうのばかり集めたデータベース誰か作ってないかな…

[kazkaz03]

この辺も参考　https://mrob.com/pub/math/numbers-16.html#le009_16

[swdrsker]

0.175％の誤差を精度良いと捉えるかどうかというポイントはある グラフィックにはめちゃくちゃ有用そう

[RySa]

こういうアルゴリズム解説は面白い。最後にニュートン法で精度を上げてるので、マジックナンバーは多少ずれてても似た結果が得られるはず。

[knok]

浮動小数点の内部表現が2進数ベースだからこそできる技か

[sgo2]

こうした変態実装な標準関数を使わず、オレオレ実装して却って遅くなってるケースは時々良く見かける。

[lp008962]

その差は「ニュートン法を一ステップ回した後のエラーが小さくなる」かららしい

[hiromo2]

ちょくちょくあるアプローチ

[tanakaBox]

除算は基本吐く。

[xjack]

0x5F3759DF vs 0x5F37BCB6

[Helfard]

へー、ほー。

[rin51]

よく思いつくな...

[mohno]

↓うん、二乗かと思うよね。/ニュートン法を収束するまで繰り返さない、ということか。除算を使わないから速いと。/Z80時代に開平計算で平方根作ったな。

[toge]

許容できる誤差で高速なアルゴリズム考えるの素敵。 精度の高い演算は標準ライブラリにお任せすればよい。

[tagomoris]

しびれる、かっこいい

[snow8-yuki]

計算したマジックナンバーに合わせた時の誤差は狭まるのかな / wikipedia_KRに、0x5F37BCB6-n_x/2 　と書かれていた。なるほど？

[masaru_al]

ニュートン法は一回繰り返すごとに有効桁数がほぼ倍になる。必要な精度が見積もれるなら必ずしも繰り返す必要はない

[nmcli]

Wikipedia 見ても https://mrob.com/pub/math/numbers-16.html#le009_16 見てもちゃんと理解し切れてない。発見者すごいな。

[yujiorama]

float を long で解釈すると log_2(x) が出てくるのすごかった

[itochan]

https://community.wolfram.com/groups/-/m/t/1108896 　／　「[2.2] σの最適値σ　σの最適値として、ここでは誤差の絶対値の最大値が最小となる値を考える。」のところが違うんでしょ

[zu2]

“平方根の逆数 1x√1x \frac{1}{\sqrt x} を高速に計算するアルゴリズムです。平方根の逆数は逆平方根とも呼ばれます。逆平方根はベクトルの正規化などに用いられるので、これを高速に計算できるアルゴリズムには大きなご利

[ustar]

楽しい

[hase0510]

「逆平方根」って言われると2乗っぽさを感じる／「逆数平方根」という言い方もあるみたい

[gorodoku]

すごい（すごい（語彙

[cj3029412]

すきすきー🐈💕

[hasiduki]

すごい

[rawwell]

“ただし、(5) で求めた σσ\sigma の値から計算すると 0x5F37BCB6 となり、一般的に知られているマジックナンバー 0x5F3759DF と微妙に食い違います。この理由はよく分かりません。”

[aya_momo]

懐かしい。GPU関係でこれを使っていたと思う。/なんでこんな甘い近似でいいのかと思ったら、最後に補正するのね。

[tettekete37564]

ニュートン法って中学生くらいの時に実装した気がするが全く覚えてないな。CG・ゲーム方面から離れて10年以上経つもんな。大学の卒業研究で3Dレンダラ書いたのになんでワンオペフルスタッフエンジニアやってるのか謎

[tattyu]

20年位前にIBM出身の天才エンジニアのコードにこれと似たような計算があって大層驚いた。当時はfloatが2の指数表現になってるのを利用してるんだなぁ位しか分からんかった。

[stealthinu]

これすげえ。よくこんなの思いつくな。ブコメよりQuakeの3D演算のために考え出されたらしい。