近岡です。

>正木です。
>
>[ruby-math:00942] で書いたことは帰納法をつかって意外と簡単に
>証明できました。したがって
>
>class Integer
>  def isqrt_ini
>    return 0 if self < 1
>    return 1 if self < 4
>    return 2 if self < 9
>    return 3 if self < 16
>    j = (bitlength - 1) >> 2
>    x = (self >> (j << 1)).isqrt_ini
>    ((x<<j) + (self>>j).div(x)) >> 1
>  end
>
>  def isqrt
>    raise "argument is negative" if self < 0
>    return 0 if self == 0
>    return 1 if self < 4
>
>    x = isqrt_ini
>    x -= 1 if x * x > self
>#   x -= 1 if x > div(x)
>    x
>  end
>end

素晴らしいアイデアですね。これだけ凝ったものになると、
将来、メンテナンスをする人は苦労しそう。

拙作の isqrtD は、対象の自然数が15ビットぐらいと小さいとき、
従来のものより遅いようです。

時間がなくチェックしていませんが、これも、
>    j = (bitlength - 1) >> 2
の影響で小さな自然数の場合には、
従来のものよりも遅くなっているのではないでしょうか。
Fixnum 用のルーチンを別に用意されたらいかがでしょう。

あと、5分でネットワークから抜けなければいけないので、
今日はこれで失礼します。
[ruby-math:00945] の証明は、今晩よまさせてさせていただきます。

0----+----1----+----2----+----3----+----4----+----5----+----6
近岡 宣吉  Chikaoka, Nobuyoshi
富山県立高岡西高等学校(数楽科)
 E-mail : chikaoka-nobuyoshi / tym.ed.jp