原です。

In [ruby-math:00933] 

>正木です。

>Integer#isqrt ですが、Newton 法の初期値を更に Newton 法で求める次の
>方法が今まで考えた中では一番早いみたいです。

すんばらしい!!n が大きくなって初期値が甘くなるのを、再帰を使って
押さえ込んでいますね。しかもこの再帰の深さは log(log n) ぐらいなの
で、全く問題なしですね。

>n           Factorial[n].isqrt の計算時間 - Factorial[n] の計算時間
>5000            0.06 sec
>10000           0.45 sec
>20000           1.75 sec
>(i686, 1.6G)

単独ではわからないので(^^;、こちらでベンチマークを取ってみました。

                          user     system      total        real
isqrt(5000!)
masaki912             0.260000   0.000000   0.260000 (  0.257000)
hara926               0.111000   0.000000   0.111000 (  0.113000)
masaki933             0.040000   0.000000   0.040000 (  0.044000)

isqrt(10000!)
masaki912             1.892000   0.000000   1.892000 (  1.911000)
hara926               0.671000   0.000000   0.671000 (  0.680000)
masaki933             0.321000   0.000000   0.321000 (  0.319000)

isqrt(20000!)
masaki912             7.150000   0.000000   7.150000 (  7.184000)
hara926               2.504000   0.000000   2.504000 (  2.514000)
masaki933             1.161000   0.000000   1.161000 (  1.168000)


ここで masaki912 は [ruby-math:00912] の bitsize のみで初期値を
決める方法、hara926 は [ruby-math:00926] の開平法で初期値を決め
る方法、hara933 は今回 [ruby-math:00933] の方法です。


しかしいいアイデアですねえ。「正木法」と名付けます(私が^^)。