Last Updated: February 25, 2016
·
2.265K
· amrnt

How to find if a number is a Fibonacci

A positive integer ω is a Fibonacci number:

If and only if 5 * ω^2 + 4 OR 5 * ω^2 - 4 is a perfect square.

First lets write a method to test if a positive number is perfect square or not (note that there're many implementations of this method):

def is_perfect_square? pos_number
  Math.sqrt(pos_number).to_i == Math.sqrt(pos_number)
end

And here's the method of testing whether the number is a Fibonacci or not:

def is_feb? n
  is_perfect_square?(5 * n**2 + 4) ||
    is_perfect_square?(5 * n**2 - 4)
end

3 Responses
Add your response

Doesn't work with large numbers. Try n = 1000000000000001.

over 1 year ago ·

It works just fine! I guess, it allocates more memory because you are testing this against a big number.

See here: http://runnable.com/VCMQuH90pXNSaq8u/fibonacci-big-number-for-ruby

over 1 year ago ·

1000000000000001 is not a fibonacci number... are you suggesting your code doesn't return true for it?

over 1 year ago ·