Check whether a number is Fibonacci number or not?
Sunday, May 25, 2014
(This was a Blog Entry Published in the Year 2014 in "Analysis leads to Paralysis")
I just happen to see in a site that, there is a generator to find whether some number is a Fibonacci number or not. Here is a C/C++ program which computes it
//////////////////////////////
// IsFib.cpp
//
// A Naive C/C++ Program to check whether
// a number is Fibonacci number
//
// If 5*n*n + 4 or 5*n*n-4 is a perfect
// square, it is a Fib #
//
// g++ -o temp.exe ISFib.cpp
//
#include <stdio.h>
#include <math.h>
///////////////////////////////
//
// Checks whether a number is a Perfect
// Square
//
bool PERFECT_SQUARE( int x)
{
int _n = (int) sqrt(x);
return (_n*_n == x);
}
////////////////////////
//
// Check If , 5*n*n + 4 or 5*n*n - 4
// is a perferct square
//
bool IsFib( int n ) {
int c = 5*n*n;
return PERFECT_SQUARE( c + 4 ) ||
PERFECT_SQUARE( c - 4 );
}
/////////////////////////////
//
// Entrypoint
//
int main( int argc, char **argv )
{
for( int j=0; j<200; ++j )
{
if ( IsFib(j) ) {
printf("%d is a Fib #\n",j);
}
}
}
The console output is given below
D:\PRASEED_PERSONAL\cpp>g++ -o temp.exe IsFib.cpp
D:\PRASEED_PERSONAL\cpp>temp
0 is a Fib #
1 is a Fib #
2 is a Fib #
3 is a Fib #
5 is a Fib #
8 is a Fib #
13 is a Fib #
21 is a Fib #
34 is a Fib #
55 is a Fib #
89 is a Fib #
144 is a Fib #
D:\PRASEED_PERSONAL\cpp>