How do I determine if a number is part of the Fibonacci sequence?

Question

I have an assignment to write a method that determines whether or not a number is part of the Fibonacci sequence.

Going along with the formula:

a positive integer z is a Fibonacci number if and only if one of 5z^2 + 4 or 5z^2 − 4 is a perfect square

I defined the following method which works for small numbers and large Fibonacci numbers, however, for whatever reason, my assignment specs throw an error when processing a large non-Fibonacci number, specifically when running is_fibonacci?(927372692193078999171). Apparently the method returns true instead of false. Everything else seems to be correct, so I'm kind of pulling my hair out over why this wouldn't work. Any suggestions?

def is_fibonacci?(i)
  bigNumber1 = Math.sqrt((5*(i**2)+4))
  bigNumber2 = Math.sqrt((5*(i**2)-4))
  if bigNumber1 == bigNumber1.round || bigNumber2 == bigNumber2.round
    return true
  else 
    return false
  end
end

Answer 1

As noted elsewhere, the issue is with the precision of Floats. BigDecimal provides arbitrary-precision arithmetic:

require 'bigdecimal'

def is_fibonacci?(i)
  i = BigDecimal.new(i)
  bigNumber1 = (5*(i**2)+4).sqrt(0)
  bigNumber2 = (5*(i**2)-4).sqrt(0)
  return (bigNumber1 == bigNumber1.round || bigNumber2 == bigNumber2.round)
end

is_fibonacci? 927372692193078999171 # => false
is_fibonacci? 927372692193078999176 # => true

Answer 2

The problem is that Math.sqrt returns a floating-point value which is normally just an estimation of the real square root. For large numbers you just get something like 1234567600000.0 which will always be considered an integer by your code.

Implement your own arbitrary-precision, integer square-root function. A naive approach could be like this:

def is_fibonacci?(i)
  n1 = 5 * i**2 + 4
  n2 = n1 - 8
  is_square?(n1) or is_square?(n2)
end

# find floor(sqrt(i)) by nesting intervals
def sqrt(i)
  a, b = 0, i
  while a + 1 < b
    m = (a + b) / 2
    if m**2 > i
      b = m
    else
      a = m
    end
  end
  a
end

def is_square?(i)
  s = sqrt(i)
  s ** 2 == i
end