How to Check a Number is Fibonacci

If you have to check that given number is fibonacci number or not. You can check this by generating all fibonacci numbers until you get larger than given number But this take very much computation.

You should use the following method.........

The given number is n
compute two numbers from n like this
a=(5*(n*n)+4)
b=(5*(n*n)-4)

If atleast one of them(a and b) is Perfect Square then the given number n must be Fibonacci Number.

Here a source code in Python.

def isPSqr(x):
    s=int(x**.5)
    return (s*s == x)
#print isPSqr(25)

def isFibo(n):
    return isPSqr(5*(n*n)+4) or isPSqr(5*(n*n)-4)
t=input()
while t:
    n=input()
    if isFibo(n):
        print 'isFibo'
    else:
        print 'isNotFibo'

    t-=1