Test if a number is fibonacci

c++ algorithm math testing fibonacci
VaioIsBorn picture VaioIsBorn · Mar 12, 2010 · Viewed 45.1k times · Source

I know how to make the list of the Fibonacci numbers, but i don't know how can i test if a given number belongs to the fibonacci list - one way that comes in mind is generate the list of fib. numbers up to that number and see if it belongs to the array, but there's got to be another, simpler and faster method.

Any ideas ?

Answer

Il-Bhima picture Il-Bhima · Mar 12, 2010

A very nice test is that N is a Fibonacci number if and only if 5 N^2 + 4 or 5N^2 – 4 is a square number. For ideas on how to efficiently test that a number is square refer to the SO discussion.

Hope this helps

Related questions

Fast ceiling of an integer division in C / C++

Given integer values x and y, C and C++ both return as the quotient q = x/y the floor of the floating point equivalent. I'm interested in a method of returning the ceiling instead. For example, ceil(10/5)=2 and ceil(11/5)=3. The …

Read More
Creating all possible k combinations of n items in C++

There are n people numbered from 1 to n. I have to write a code which produces and print all different combinations of k people from these n. Please explain the algorithm used for that.

Read More
Finding square root without using sqrt function?

I was finding out the algorithm for finding out the square root without using sqrt function and then tried to put into programming. I end up with this working code in C++ #include <iostream> using namespace std; double …

Read More