平方根を任意精度でもとめる

Project EulerのProblem 80は、小数点以下100桁分の正確な平方根が必要になる。平方根を求める方法はたくさんあるが、有名なのは高校で学んだような気もする「ニュートン法」だとか「開平法」とかだろうか。 でもこれは筆算だとサクサクできるにもかかわらず、コンピュータ上で実行するのはやたらめんどくさい。参考：Wikipedia

めんどくさい問題は後回しにしていたのだけど、すごいPDFを見てしまった。なんと2ステップで任意の精度で平方根が求められるアルゴリズムだ。驚くほど簡潔で、感動的なほどエレガントだと思う。

def sqrt(n)
  a, b = 5 * n, 5
  1000.times do
    if a >= b
      a = a - b
      b += 10
    else
      a = "#{a}00".to_i               # 二つのゼロをaの後に付加する
      b = "#{b}".insert(-2, '0').to_i # ゼロを下一桁の直前に挿入する
    end
  end
  b
end

sqrt(2) #=> 1414213562373095048801688724209698078...

PDFによると日本で考え出されたアルゴリズムだそうだけど、私は知らなかった。もっと勉強しなきゃいけないね。したくはないけどね。