[ruby-list:1335] Re: Rational and Complex

原です。

ひとつ言い忘れました。

> ところがあります。つまり整数 d の整数の平方根 r を求める Newton 近似
> の式は、[] をガウス記号( = Floor) として、
> 
> N(x) = [(x+[d/x])/2]

ここで、収束、振動にかかわらず、

    N(x) <= N(N(x))  ならば  N(x) == r

が証明できるので、これを収束の判定条件にできます。だから、

def isqrt(d)
  x = d
  loop do
    a = (x + d/x)/2
    return x if a >= x
    x = a
  end
end

で整数の平方根は求めることができるわけです。ここでは初期値を
d にしてますが。初期値を求めるのに float の sqrt を使ったら早
くなるかな？
---===-=-=-=-=-=-=-=-=======--=-=-=-==-=-===-=-=-=-=-=-=--=-==-=--
                            Shin-ichro Hara(Nagaoka Univ.of Tech.)