タグ別アーカイブ: algorithm

平方根の逆数を高速に求める

float InvSqrtLinear(float x, int magic){
   float xhalf = 0.5f*x;
   int i = *(int*)&x; // get bits for floating value
   i = magic - (i>>1); // gives initial guess y0
   x = *(float*)&i; // convert bits back to float
   return x;
}

平方根の逆数の近似値を高速に求めるアルゴリズム。ゲームのQuake3で有名になった方法らしいです。詳しくはOrigine of Quakes3′s Fast InvSqrt()に解説があるのでそちらを参照してください。

簡単に説明すると、ニュートン・ラプソン法による平方根の逆数の計算を、最初の1回だけ行って近似値を求めるという方法で、それほど精度を必要としないなら高速な計算が行えます。

これをFlashでも使えないかと思って調べてみると、mtascやhaxeの作者nicolas自身がこの記事に解説を書いてくれていました。
FlashのAS3ではByteArrayのwriteFloat()、readInt()を使ってInt型とNumber型を変換する処理を行いますが、これらのメソッドの実行速度が遅く、普通に計算するより遅くなってしまうようです。

高速にアクセスできるhaxeのVirtual Memory APIで実装すると以下のようになります。

[hx]
public function prepare() {
var b = new flash.utils.ByteArray();
b.length = 1024;
flash.Memory.select(b);
}

public function invSqrt( x : Float ) : Float {
var half = 0.5 * x;
flash.Memory.setFloat(0,x);
var i = flash.Memory.getI32(0);
i = 0x5f3759df – (i>>1);
flash.Memory.setI32(0,i);
x = flash.Memory.getFloat(0);
x = x * (1.5 – half*x*x);
return x;
}
[/hx]

この方法だと、約700%程高速に実行できるようです。グレート!
haxe3DphysaXeもこのメソッドを採用しているようです。

参考サイト