原です。

>近岡です。

近岡さんもしつこいですね。:-)

>[ruby-math:00943]のプログラムisqrt_iniの
>  >     j = (bitlength - 1) >> 2
>
>  >     j = (bitlength + 1) >> 2
>でも、構わないんじゃないかと思うようになりました。

なるほど、一回に処理する桁を増やして再帰を浅くしようと言う魂胆
ですね。最後の軽い処理 1 回をたまに省く事ができるだけで、処理
速度は変わらないと思いますが、理論的には興味があります。


近岡さんの論法を [ruby-math:00948] の方法でチェックしてみ
ます。問題は:

  最初の条件 k**4 <= a を k**4 <= 4*a にゆるめられるか?

となります。k が大きいほど再帰が浅くて済むのですね。こちらの x 
が向こうの k*x にあたるので、ちょっと混乱しますが、

>  2**(2*n)≦2*x
>ならば、
>  y ≦ sqrt(a)+1
>が成り立つはず。

ここは向こうの言葉では「k**2 <= 2*x*k ならば N(x) - r <= 1」
に相当し、

> 2**(4*n-2)≦a
>でありさえすれば、
> ...
> 2**(2*n-1)≦s*2**n≦x
>が成り立ちます。

は「k**4/4 <= a ならば k*x/2 <= x*k」に相当します。そして、ど
ちらの主張も正しい事は直ぐ分かるので、、、いいみたいですね。


>もしかして、[ruby-math:00936]内のプログラム isqrtC の
>効率が悪かったのは、
>>     j = (bitlength + 1) >> 2
>の影響じゃなくて、
>>    x = ((self >> (j << 1)).isqrt_ini + 1) << j
>の+1の影響だったんでしょうか?

多分そうですね。


>===(オマケ)============
>
>Fixnum用のルーチンを別に用意する場合は関係ないことですが、

そろそろ、Fixnum も含めてまとめていただいて良いのではないで
しょうか。

さしあたって、bitlegth は [ruby-math:00927] を改良した

-----^ bitlength.c
#include <ruby.h>
#include <math.h>
#define BDIGITS(x) ((BDIGIT*)RBIGNUM(x)->digits)
#define BITSPERDIG (SIZEOF_BDIGITS*CHAR_BIT)

static VALUE
rb_fix_bitlength(x)
     VALUE x;
{
    int v = FIX2INT(x), i;
    if (v == 0) return INT2FIX(1);
    for (i = SIZEOF_INT * CHAR_BIT - 2; ((1 << i) & v) == 0; i--) ;
    return LONG2FIX(i + 1);
}

static VALUE
rb_big_bitlength(x)
     VALUE x;
{
    long len = RBIGNUM(x)->len, i;
    BDIGIT u = BDIGITS(x)[len - 1];
 
    if (u == 0) return INT2FIX(1);
    for (i = BITSPERDIG - 1; (((BDIGIT)1 << i) & u) == 0; i--) ;
    return LONG2FIX((len - 1) * BITSPERDIG + i + 1);
}

void
Init_bitlength(void)
{
    rb_define_method(rb_cFixnum,"bitlength",rb_fix_bitlength,0);
    rb_define_method(rb_cBignum,"bitlength",rb_big_bitlength,0);
}
-----$ bitlength.c

でいいでしょうか?自信ありません。

あと、やっぱり ilog2 の方が好きなんだよなあ。^^;