けいじゅ@日本ラショナルソフトウェアです.

In [ruby-math :00632 ] the message: "[ruby-math:00632] Re: class Real
", on Oct/16 11:19(JST) 正木 功 writes:

>正木です。
>
>|[ruby-math:00577] Re: int / int -> ?
>|From: keiju / ishitsuka.com (石塚圭樹)
>|Integer.sqrtは高速に計算できそうですね. ビットシフトするだけだから.
>
>具体的な algorithm を教えて下さい。

たいへん申し訳ない. 私の超勘違いでした(__;;;;

>class Integer
>  def gcd(n)
>    return self if n==0
>    n=n.abs
>    n.gcd(self%n)
>  end
>end
>-----
>
>最後の gcd の変更で EulerConstant 60 桁の計算が 54sec から 27sec に
>劇的に早くなりました。Bignum に対しては単純な方法の方が早い場合が
>あるようです。
>調べてみると、従来の gcd の中で
>    n >>= 1 while n[0] == 0
>の所が意外に時間を食うようです。
>非常に極端な例をあげると
>(2**1000000+1).gcd 2**1000000
>は上の方法なら数十 ms で済むのに、従来の方法だと何時間もかかりそうです。

うーん. そうかぁ... ちゃんと考えないといけないですね...
__
..............................石塚 圭樹@日本ラショナルソフトウェア...
----------------------------------->> e-mail: keiju / rational.com <<---