From: Shin-ichiro HARA <sinara@...>
Date: 2008-03-27T17:13:44+09:00
Subject: [ruby-dev:34155] Re: rational.rb, complex.rb and mathn.rb

> 原です。

> 今回、mathn.rb で aRational**aRational が Rational で表現できるときは、
> Rational を返すように凝った作りになってるのに気付きました。いまさら。
> すばらしい。
> 
> ただ、石塚さんは素因数分解を使っているけど、もうちょっと速い方法がある
> かもしれませんね。1/2 乗だと、整数の高速に平方根を求める方法が、
> ruby/math のどこかで isqrt とかいう名前で提案されていたし、同様に整数の
> 1/n 乗もニュートン法を使って速く求めることができると思います。

みつけました。[ruby-math:00914] New methods of Integer から延々と続くス
レッドで議論されていました。かなり膨大な内容で、時間が無いとと読み返せ
ません。整数の k 乗根については、正木さんが、再帰による方法や Newton 法
による方法を書いています。再帰によるもの([ruby-math:00936] の irootB)を
ちょっと変えてここに書くと：

  def iroot(k, n)
    return 0 if n <= 0
    r0 = 2 * iroot(k, n >> k)
    r1 = r0 + 1
    n < r1 ** k ? r0 : r1
  end

です。整数 n の k 乗根(のfloor)が求まります。Newton 法だともっと速いみ
たいだけど、難しすぎ。これを利用すれば、** のための Prime は mathn.rb
では不要になるのではないでしょうか。

Prime は Prime でとても面白いので、そういう数学的なものを集めた新たなラ
イブラリを起こしたらどうかな。