ruby - Ruby-非常に大きな整数の平方根は丸めの問題を引き起こします

Question

私はフィボナッチ問題を解決しようとしていますが、丸めの問題に遭遇しています。

i = 8670007398507948658051921その場合fib1 = 19386725908489880000000000.0。

私のコードは以下のとおりです-助けてくれてありがとう。

def is_fibonacci?(i)

  fib1 = Math.sqrt(5*(i**2)+4)
  fib2 = Math.sqrt(5*(i**2)-4)

  fib1 == fib1.round || fib2 == fib2.round ? true : false

end

Answer 1

sqrtはFloatを返し、その精度はここでは十分ではないため、このようなsqrtを実行してもそのような大きな値では機能しません。独自のsqrt関数を実装することをお勧めします。それを行う方法を提案するアルゴリズムはいくつかありますが、私は個人的に、関数の逆を計算するために二分探索を使用するのが最も簡単です。

def sqrt a
  begv = 1
  endv = a
  while endv > begv + 1
     mid = (endv + begv)/2
     if mid ** 2 <= a
        begv = mid
     else
        endv = mid
     end
  end
  return begv
end

あるいは、sqrtにBigDecimalを使用してみることもできます（単に累乗する0.5）が、二重計算を必要としないため、上記の方法の方が好きです。