How to check if a given number is Fibonacci number? | GeeksforGeeks

How to check if a given number is Fibonacci number? | GeeksforGeeks
Given a number ‘n’, how to check if n is a Fibonacci number.
A simple way is to generate Fibonacci numbers until the generated number is greater than or equal to ‘n’. Following is an interesting property about Fibonacci numbers that can also be used to check if a given number is Fibonacci or not.
A number is Fibonacci if and only if one or both of (5*n² + 4) or (5*n² – 4) is a perfect square (Source: Wiki).

bool isPerfectSquare(int x)

{

    int s = sqrt(x);

    return (s*s == x);

}

// Returns true if n is a Fibinacci Number, else false

bool isFibonacci(int n)

{

    // n is Fibinacci if one of 5*n*n + 4 or 5*n*n - 4 or both

    // is a perferct square

    return isPerfectSquare(5*n*n + 4) ||

           isPerfectSquare(5*n*n - 4);

}

Why This Rule Works
http://calculus-geometry.hubpages.com/hub/How-to-Tell-if-a-Number-is-a-Fibonacci-Number
To see why the rule "5F² ± 4 = square" is enough to determine if a number is Fibonacci, we have to prove (1) that all Fibonacci numbers satisfy this relation, and (2) that only Fibonacci numbers do.

If F = F(2k) is an even-indexed Fibonacci number, i.e., part of the subsequence 0, 1, 3, 8, 21, 55, 144,..., then F satisfies the "+" relation:

5*F^2 + 4 = a square number

and if F = F(2k-1) is an odd-indexed Fibonacci number, i.e., part of the subsequence 1, 2, 5, 13, 34, 89, 233,..., then F satisfies the "-" relation:

5*F^2 - 4 = a square number

http://www.quora.com/What-is-the-most-efficient-algorithm-to-check-if-a-number-is-a-Fibonacci-Number
http://comproguide.blogspot.com/2014/10/how-to-check-if-given-number-is.html

def isFibonacci(num):


    if num < 2:


        return True


    else:


        first = 0


        second = 1


        while (first + second) <= num:


            third = first + second


            first = second


            second = third


        if third == num:


            return True


        else:


            return False

Read full article from How to check if a given number is Fibonacci number? | GeeksforGeeks