Ruby - Sqrt on a very large Integer cause Rounding issues

Question

I'm trying to solve a Fibonacci problem and am stumbling into rounding issues.

If i = 8670007398507948658051921 then fib1 = 19386725908489880000000000.0.

My code is below - thanks for any help.

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

Doing sqrt like that will not work for such big values, because sqrt returns a Float and its precision will not suffice here. I would advice you to implement your own sqrt function. There are several algorithms out there suggesting how to do that, but I personally thing using a binary search for computing the reverse for a function is the easiest:

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

Alternatively you may try using BigDecimal for the sqrt(simply raise to power 0.5), but I like above method better as it does not involve any double calculations.