How to find if a number is a Fibonacci
A positive integer ω
is a Fibonacci number:
If and only if
5 * ω^2 + 4
OR5 * ω^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
Written by Amr Tamimi
Related protips
3 Responses
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
·
Have a fresh tip? Share with Coderwall community!
Post
Post a tip
Best
#Ruby
Authors
Sponsored by #native_company# — Learn More
#native_title#
#native_desc#