高速逆平方根のProcessingでの検証

はじめに

高速逆平方根のマジックナンバー(0x5f3759df)に関するアルゴリズムが気になったので、Processingで試したメモです。

（アルゴリズムの登場は1990年代後半で、SSEの登場が1999年。自分がGame Programing Gemsで近いものを見かけたのが、2001年ぐらい。2001年の当時は、まだ、この手の計算テクニックがやや、速かったと記憶しているが、SSEの環境で実行していたのか、はたまた、SSE最適化のコンパイルをしていたのか、覚えていないし、理解できていたのかも怪しい。）

環境

Processing 4
Apple M1 pro

コード

inv_sqrt.pde

void setup() {
  int msec = millis();
  for (float n=0; n<10000000; n++) {
    float r = Q_rsqrt(n)*n;
    //println(r);
  }
  println(millis()-msec);
  
  msec = millis();
  for (float n=0; n<10000000; n++) {
    float r = sqrt(n);
    //println(r);
  }  
  println(millis()-msec);
}

float Q_rsqrt(float n){
  int i = Float.floatToRawIntBits(n);
  float y = Float.intBitsToFloat(0x5f3759df - (i >> 1));
  return y * (1.5F - 0.5F * n * y * y);
}

結果

高速逆平方根が12msec
平方根が10msec
というわけで、processingでは遅くなりました。

メモ

下記サイトでも言及があるように「rsqrtss命令が最強」だとおもうので、この検証はあまり意味がない。javaのsqrt命令が内部でrsqrtss等を使っていることを願う。shaderを使ったりするなら、GPUで計算できるので、並列処理ならさらに速くできるはず。

参考サイト

Cのコードが掲載されています。

C言語ではポインタでfloatとlongの行き来をしているが、javaにはないので、
このサイトを参考にした。このサイトすごいな。

よくわかるアルゴリズムの解説