sqrt(x)と1/sqrt(x)の高速な実装を考えてみます.
sqrt(x)はニュートン法を用いて求めることが多いようです. ニュートン法はf(x) = 0の解を
求めるためのアルゴリズムです. 問題になるのはニュートン法を実行するときの初期値でしょう.
これはテーブルを用いたりいろいろな方法で見つけます. しかし, 今回は1/sqrt(x)の高速実装を用いてsqrt(x)を計算するコードを紹介します.
まずは1/sqrt(x)のコードを見てみましょう.
一見???ですがこのコードで1/sqrt(x)が計算できます. wikipediaのhttps://en.wikipedia.org/wiki/Fast_inverse_square_root に詳細はあります.
このコードは前半でbit演算のみで1/sqrt(x)の大体の値を求め, 後半でニュートン法を行い計算の精度を上げています.
1/sqrt(x)が求まればあとはx*1/sqrt(x)でsqrt(x)が得られます.
mySqrt(x),invSqrt(x)いずれも精度と速度はニュートン法の回数で調整できます.
invSqrt(x)はベクトルの正規化の際等に使えます.
たぶん, mathf.hのsqrt(x)を使うよりかは高速だと思います.
0 件のコメント:
コメントを投稿