平方根の計算で怒鳴られる事
もちろんその方面の分野の人たちはそんな事は常識でそれなりの工夫をしている。
もっとも初歩レベルでは
もっとも初歩レベルでは
点p1から一番近いのはp2かp3なのか？を計算するのに当然だがお互いの距離を計算して
float dist1 = sqrt((p1-p2)^2);
float dist2 = sqrt((p1-p3)^2);
float dist1 = sqrt((p1-p2)^2);
float dist2 = sqrt((p1-p3)^2);
dist1 < dist2 なら p2 の方が近いと判断する。
※ (p1-p2) は (p1.x-p2.x)^2+(p1.y-p2.y)^2+(p1.z-p2.z)^2 の略。（擬似コード）
※ (p1-p2) は (p1.x-p2.x)^2+(p1.y-p2.y)^2+(p1.z-p2.z)^2 の略。（擬似コード）
こんな事をやらかしたらSEや上司から罵倒されるのは間違いない。
なにが問題なのか？それは距離が近い方を見つけるのに平方根を計算しているからだ。
もちろん中学校で学ぶピタゴラスの定理で２点間の距離（対角線の長さ）を計算するのに平方根を叩き込まれたからといういい訳もあるだろうが問題は距離を計算する事ではなく距離を比較する事だから
「dist1 < dist2 なら p2 の方が近いと判断する。」
というのは別に二乗のまま、
「dist1^2 < dist2^2 なら p2 の方が近いと判断する。」
となって一切平方根を計算せずに近い方を知る事が出来る。
あ、そうそう。なんでそんなに平方根を使うのがそんなにいけないのか？
それは一言では難しいがコンピュータが計算するときに物凄く時間を費やして計算される点にある。
だから無闇に使うと技術計算等ではバカに出来ない処理時間を強いられるのだ。
それは一言では難しいがコンピュータが計算するときに物凄く時間を費やして計算される点にある。
だから無闇に使うと技術計算等ではバカに出来ない処理時間を強いられるのだ。
しかし、そんな工夫が出来てもどうしても距離を計算しなければならない場面もある。
そんなときは仕方なく平方根を計算する、、、しかし、これでも分野によっては罵倒されるだろう。
そんなときは仕方なく平方根を計算する、、、しかし、これでも分野によっては罵倒されるだろう。
文献をあさると色んなテクニックがどっさりと出てくるのだが用途に合わせて選択する必要がある。
一概にどれが良いかは言いがたいのだが標準の平方根計算と同程度の精度の高速計算する方法にも色々とあるが適当に漁って試してみたのが次の結果だ。
一概にどれが良いかは言いがたいのだが標準の平方根計算と同程度の精度の高速計算する方法にも色々とあるが適当に漁って試してみたのが次の結果だ。
ちょっとした工夫でも、１．２倍も早い事がわかる。これだけでも膨大な計算をするとそのコストは計り知れない。しかし、面倒な事である。
ところがもともとはスーパーコンピュータではよく見られた手法だが近年のパソコンではSIMD(Single Instruction Multiple Data )というプロセッサが搭載されている。パソコンでは、インテルが開発したCPUのSIMD拡張命令セットであるSIMD 拡張命令 (SSE, Streaming SIMD Extensions)が使える。
なんか小難しいのだがきっとあなたのパソコンにもこんな物々しい機能が搭載されているのだ。
これを使うと
SSEの平方根計算 time 23592[msec]
でなんと標準のsqrtと比べて1.6倍も早い。
しかもかなりお手軽だ。こういうのは膨大なベクトル計算では威力を発揮する。
サンプルコード
float sqrt_sse( const float& a )
{
float ret;
_mm_store_ss( &ret, _mm_sqrt_ss( _mm_load_ss(&a) ) );
return ret;
}
