ARMの平方根(2)

ふと思った。

s = (x / s + s) >> 1;

この部分、除算を使っているんだけれども、ARMの命令には除算命令がない。
どうやって計算してるんだろう？と思ってアセンブラを吐き出してみると……。

BL       __rt_udiv

除算演算ライブラリを使ってるよ(ノ∀｀)ｱﾁｬｰ
こりゃ考えるまでもなく遅いな……。

昨日のURLに、

#define iter1(N) \
    try = root + (1 << (N)); \
    if (n >= try << (N))   \
    {   n -= try << (N);   \
        root |= 2 << (N); \
    }

uint32 sqrt (uint32 n)
{
    uint32 root = 0, try;
    iter1 (15);    iter1 (14);    iter1 (13);    iter1 (12);
    iter1 (11);    iter1 (10);    iter1 ( 9);    iter1 ( 8);
    iter1 ( 7);    iter1 ( 6);    iter1 ( 5);    iter1 ( 4);
    iter1 ( 3);    iter1 ( 2);    iter1 ( 1);    iter1 ( 0);
    return root >> 1;
}

ってのがあるんだけど、これなら1bitの収束が4クロックなので4*16=64クロックで、他の部分を入れて70〜80クロックぐらいと予想。
誤差の計算もしてみたけど、ニュートン法で５回計算したのと比較しても、ニュートン法の方が１だけ大きい場合が時々あったぐらいで、他は全て同じ。
これはかなり良さげ。

気が向いたら実機での速度を測ってみるかな(*´ω`)

追記：
BREW3.1のとある機種で、

uint32 s = 0;
uint32 t;
while( true ){
    sqrt( s );
    t = s;
    s += 1999;
    if( t > s ) break;
}

こんなプログラムを組むと、

ニュートン法  → 5290ms
bitごとに収束 → 880ms

になりました。
やっぱりARMは分岐に強いですね。

追記２：
ARMだから速いと思ったら、どうやら違うようです。
PC（Pen4 2.8GHz）で測定してみると、

ニュートン法  → 313ms
bitごとに収束 → 47ms

でした。
除算って結構大きい処理なのね（;´Д｀）