How to check if a given number is Fibonacci number?

Fibanacci numbers have one interesting property:

A number 'n' is a Fibanacci number if and only if (5*n*n + 4) or (5*n*n - 4) or both are perfect squares.

The below program will find whether input number is fibanacci number or not.

We have an alternate method also to find a number is fibanacci or not by generating fibanacci numbers until the value is equal to or greater than input number. But, this method is time consuming one. So, we are using fibanacci numbers property.

Code:

#include<stdio.h>

#include<math.h>

int isPerfectsquare(int input)

{

int result;

  result = sqrt(input);

if (result * result == input)

  return 1;

  else

     return 0;  

}

int isFibanacci(int input)

{

  int result;

 

 /* If return value of 

  sqrt(5*input*input + 4) or 

  sqrt(5*input*input - 4) is perfect sqaure then

  input number is fibanacci
  */

result = isPerfectsquare(5 * input * input + 4) || isPerfectsquare(5 * input * input - 4);

if (result)

   return 1;

  else

  return 0;
}

main()

{

   int input, result;

   printf("Enter a number to verify whether it belongs to fibanacci number set\n");

   scanf("%d", &input);

   

   result = isFibanacci(input);

   

   if (result)

      printf("Given number %d is fibanacci number\n", input);

  else

     printf("Given number %d is not fibanacci number\n", input);

}

Output:

Enter a number to verify whether it belongs to fibanacci number set

13

Given number 13 is fibanacci number

What is a fibanacci number ?
http://en.wikipedia.org/wiki/Fibonacci_number

How to recognize a fibanacci number
http://en.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers