algorithmtestingmathfibonacci

Test if a number is a Fibonacci number

I know how to make the list of the Fibonacci numbers, but I don't know how can I test if a given number belongs to the fibonacci list - one way that comes in mind is generate the list of fib. numbers up to that number and see if it belongs to the array, but there's got to be another, simpler and faster method.

Any ideas?

Solution

  • A very nice test is that N is a Fibonacci number if and only if 5 N^2 + 4 or 5N^2 – 4 is a square number. For ideas on how to efficiently test that a number is square refer to the SO discussion.