2013年9月17日火曜日

整数で平方根を計算する

整数で平方根の近似値を出力する関数です

int sqr(int sq) {
int j, i;
for (j = 1, i = 0; sq >= j; sq -= j, j += 2, i++);
if (sq > (j / 2)) { i++; }
return(i);
}

実際の計算結果は
上の図のようにある程度正確になっています
およそ±0.5の範囲です
コード中のif分を外せば+0から-1の範囲になります

計算方法は
http://www.wizforest.com/gear/tiger/sqrt/
を参考にしました

実際は別の方法が良いようですが、とりあえずこのコードでも遅い以外のデメリットは特に無いです

で、実効速度の問題ですが
sqr(自作)及びsqrt(math.h)の実行速度を計測してみました
(図中ではpowと書かれていますがsqrtです)

sqrt関数の処理時間はほぼ一定ですが
sqr関数はforでデクリメントしているため、処理時間は一定の法則で伸びていきます

上記コード中のsq,j,iにregisterをつけるとかなり早くなり、30000を超えてもsqrt関数より早くなります


FPUが使えるシステムでは整数で計算するメリットは全くありませんが、FPUがなく、ソフトウェア的に計算しているCPUや そもそも浮動小数点演算ができない環境ではある程度使えると思います

例えば3軸加速度からその物体にかかっている加速度は
加速度=sqrt((x*x)+(y*y)+(z*z))
で求められるため、缶サットなどで瞬間的にどれくらいの加速度がかかっていたか等を計算することができます
(加速度は単純に x+y+z という計算はしてはいけません)

0 件のコメント:

コメントを投稿