Checking if a number is a Fibonacci or not?

Solution 1:

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.

Solution 2:

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$

Solution 3:

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 5n² ± 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 5n² + 4.

Solution 4:

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].

Let me know if I can help you anymore!

[1] http://www.tylerclark12.com/blog/wp-content/uploads/2010/10/Math_542_9-24.pdf

[2] Kelley, W. & Peterson, A. (2001). Difference Equations: An Introduction with Applications (2nd Ed.). San Diego, CA: Academic Press.

Solution 5:

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.