C++ Programming -To check if a given number is Fibonacci number

Given a number ‘n’, how to check if n is a Fibonacci number. First few Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 141, ..

Examples :

Input : 8
Output : Yes

Input : 34
Output : Yes

Input : 41
Output : No

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*n2 + 4) or (5*n2 – 4) is a perfect square

[ad type=”banner”] [pastacode lang=”cpp” manual=”%2F%2F%20C%2B%2B%20program%20to%20check%20if%20x%20is%20a%20perfect%20square%0A%23include%20%3Ciostream%3E%0A%23include%20%3Cmath.h%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20A%20utility%20function%20that%20returns%20true%20if%20x%20is%20perfect%20square%0Abool%20isPerfectSquare(int%20x)%0A%7B%0A%20%20%20%20int%20s%20%3D%20sqrt(x)%3B%0A%20%20%20%20return%20(s*s%20%3D%3D%20x)%3B%0A%7D%0A%20%0A%2F%2F%20Returns%20true%20if%20n%20is%20a%20Fibinacci%20Number%2C%20else%20false%0Abool%20isFibonacci(int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20n%20is%20Fibinacci%20if%20one%20of%205*n*n%20%2B%204%20or%205*n*n%20-%204%20or%20both%0A%20%20%20%20%2F%2F%20is%20a%20perferct%20square%0A%20%20%20%20return%20isPerfectSquare(5*n*n%20%2B%204)%20%7C%7C%0A%20%20%20%20%20%20%20%20%20%20%20isPerfectSquare(5*n*n%20-%204)%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20for%20(int%20i%20%3D%201%3B%20i%20%3C%3D%2010%3B%20i%2B%2B)%0A%20%20%20%20%20isFibonacci(i)%3F%20cout%20%3C%3C%20i%20%3C%3C%20%22%20is%20a%20Fibonacci%20Number%20%5Cn%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20i%20%3C%3C%20%22%20is%20a%20not%20Fibonacci%20Number%20%5Cn%22%20%3B%0A%20%20return%200%3B%0A%7D” message=”C++ Program” highlight=”” provider=”manual”/]

Output:

1 is a Fibonacci Number
2 is a Fibonacci Number
3 is a Fibonacci Number
4 is a not Fibonacci Number
5 is a Fibonacci Number
6 is a not Fibonacci Number
7 is a not Fibonacci Number
8 is a Fibonacci Number
9 is a not Fibonacci Number
10 is a not Fibonacci Number