正木です。


In [ruby-math:00940]

|これはオリジナルの [ruby-math:00933] を少し変形していますよね。
|多分オリジナルのままの方がちょっと速いと思います。つまり、

オリジナルでは bignum が対象だったので必要なかったのですが、
Ruby script に書き直すときに
    return 2 if self < 9
    return 3 if self < 16
を書くのがいやで書き換えてしまいました。これがそんなに速度に
影響するとは思いませんでした。

|で、さらにたった今投げられた、近岡さんの [ruby-math:00939] を見たら
|
|    x = x << j
|    x = (x + self.div(x)) >> 1	
|
|は、
|
|    x = ((x << j) + (self >> j).div(x)) >> 1
|
|としてますね。ううむ、なるほど！気がつかなかった。こちらの方が割

これは速度の向上にかなり効きそうです。


|また、
|
|    x = ((x << j) + (self >> j).div(x)) >> 1
|
|という工夫も値が小さめになるので、isqrtC2 でさえちょっと不安です。

これは大丈夫だと思います。

調べてみると殆どの場合 isqrt2_ini の段階で正しい値が得られています。

Factorial[1000*n].isqrtC2 (n=10..20)

で実際に loop が回るのは n=12 のときだけ。

(2**(2**n-1)-1).isqrtC2 (n=1..19)

では n=5,6 のみ。


それにしてもアイデアを出しあうとどんどん早くなりますね。