# Checking if a number is a Fibonacci or not?

The standard way (other than generating up to $N$) is to check if $(5N^2 + 4)$ or $(5N^2 - 4)$ is a perfect square. What is the mathematical logic behind this? Also, is there any other way for checking the same?

-
The Binet formula should prove to be useful. – J. M. Nov 12 '10 at 13:21
@J.M :I knew Binnet formula but it's not much good when you are trying to generate up-to $10^{12}$ or more, since it will loose precision due to floating point operation, there also is one algorithm of O(lg n) time which uses matrix exponentiation trick for computing fib(n), but I don't really want to generate and check. – Quixotic Nov 12 '10 at 13:27
@J.M:Or do you mean that I can reduce Binnet formula to something that can be used for checking ? – Quixotic Nov 12 '10 at 13:27
A related thread at stackoverflow: stackoverflow.com/questions/2432669/… – Martin Sleziak Sep 2 '11 at 10:41

Binet's formula tells you that $F_n$ is asymptotic to $\frac{1}{\sqrt{5}} \phi^n$, where $\phi = \frac{1 + \sqrt{5}}{2}$ is the golden ratio. So to check if a number $x$ is a Fibonacci number you should compute $n = \frac{\log (\sqrt{5} x)}{\log \phi}$. If this number is very close to an integer then $x$ should be very close to the Fibonacci number $F_{[n]}$ where $[n]$ denotes the closest integer to $n$. In fact I think $x$ is a Fibonacci number if and only if the error is less than about $\frac{\log \phi}{5x^2}$.

But if you don't trust that computation, you can compute $F_{[n]}$ in $O(\log n)$ time, for example by using binary exponentiation to compute powers of the matrix $\left[ \begin{array}{cc} 1 & 1 \\\ 1 & 0 \end{array} \right]$, and then you can check whether this number equals $x$.

Your first question can be answered using the theory of (generalized) Pell equations.

-
Well,I derivation you showed me using the Binnet's formula will be again much prone to loss of precision,so it is not a much of useful while I am writing in C-family of languages, so I guess the perfect square method is something I need to concentrate, since that will be more or less O(1) + complexity of the square root algorithm,but I don't really understand how are you deriving it from Pell equation ?! :( – Quixotic Nov 12 '10 at 13:53
@Debanjan: if you are working in finite precision you can still compute F_{[n]}. 5n^2 + 4 is a square if and only if the (generalized) Pell equation m^2 - 5n^2 = 4 has a solution, and similarly for 5n^2 - 4. The theory of Pell equations can be adapted to this case and will tell you that n has to be a Fibonacci number. – Qiaochu Yuan Nov 12 '10 at 14:33
@ Qiaochu Yuan: if you are working in finite precision you can still compute F_{[n]} Can you please explain how ? I am interpreting F_{[n]} as Fib(floor(n)) where Fib(n) computes n-th Fibonacci number and the working of floor is mentioned here : cplusplus.com/reference/clibrary/cmath/floor – Quixotic Nov 12 '10 at 15:09
Or we can use binary search and avoid floating point computations altogether. – Aryabhata Nov 12 '10 at 15:24
@Moron: I don't understand. Computing logarithms is really, really easy; you can get a good estimate just by using strlen(x) and then you've already narrowed down n to within maybe four integers. Doesn't your algorithm take something like O(log x log log x) time? Mine takes O(log log x). – Qiaochu Yuan Nov 12 '10 at 15:42

HINT $\rm\ n\:$ is a Fibonacci number iff the interval $\rm\ [\phi\ n - 1/n,\ \phi\ n + 1/n]\$ contains a positive integer (the next Fibonacci number for $\rm\ n > 1\:$). This follows from basic properties of continued fractions. For one proof see e.g. $\$ T. Komatsu: The interval associated with a fibonacci number. $\$ This is a reasonably efficient test since it requires only a few multiplications and additions. $\$ For example, $\rm\ 2 \to [2.7,\ 3.7],\ \ 3\to [4.5,\ 5.2],\ \ 5 \to [7.9,\ 8.3]\ \ldots$

-
what operation is $\rm\ [\phi\ n - 1/n,\ \phi\ n + 1/n]\$ ? – Quixotic Nov 12 '10 at 14:22
Is there a LaTeX rendering problem? – AD. Nov 12 '10 at 14:25
Doesn't that method require knowing $\phi$ to high accurary when $n$ is large? – lhf Nov 12 '10 at 14:57
@lhf: Of course, but it can be precomputed (and lazily extended if need be). – Bill Dubuque Nov 12 '10 at 15:02
@Bill, my knowledge of continued fractions is very limited, can you point to a reference, or give a proof, that describes this property? thanks. – rcollyer Mar 3 '11 at 12:40

As for ways to check is a number is a Fibonacci number, I'll speak to efficient testing since the other aspects seem covered. First, you should check if the residue mod some fixed number is possible for a Fibonacci number. Sloane's A189761 gives the sequence of 'good' moduli to use: for example, there are only 54 distinct residues mod 39088169 that contain Fibonacci numbers. A binary search on these lets you quickly remove 99.9998% of possible numbers. (Depending on how large you want to go, a smaller or larger number may be advisable.)

Of course for very small numbers you may choose to do a binary search directly before checking residues to the chosen modulus.

For numbers that pass the test, the 5n2 ± 4 test is best, and it's probably sensible to do this directly—the residue test above ensures that the number is not of a prohibited congruence class to your modulus. That is, compute the square root of the number and see if it is close to an integer. If so, square it and test if the result is the original number. The methods of Bernstein's paper "Detecting perfect powers in essentially linear time" (section 8) can be used here if desired.

Note that if n < 0 you need only test 5n2 + 4.

-

Using integers only, I would use Binary Search. Certainly you can compute $F_n$ only with integers, the simplest way is matrix exponentiation. Using Binary Search you can find numbers near'' your number $x$ and you will find either $x = F_n$ or $F_{n+1} > x > F_n$. I suppose this method is generic for anything monotone you can compute fast. To initiliaze the binary search, just keep doubling $F_{2n}$

EDIT: Binary search allows you to search for a number x in a sorted "array" F[] (in the programming sense). Use this method to search for your number. When you need F[n] just compute $F_n$. This will work because the sequence is strictly increasing except for the initial 1,1.

-

On another note, many people have mentioned the Binet formula. There is a nice way to see how this formula comes about. The Fibonacci sequence is a recurrence relation, so we can apply difference calculus to the sequence. In my advanced discrete mathematics course, we looked at the Fibonacci sequence, naturally. You can see the notes from the day we derived a formula for it[1]. It is on page 1 and page 2 of [1].

A good text book to take a look at with regards to this is [2].