Translating matrix fibonacci into c++ (how can we determine if a number is fibonacci?) Is it possible to determine if a number is a fibonacci number in less than N time (where N is the Nth fibonacci number) using the matrix method?  I'm trying to exclude external libraries like cmath or math.h which include square roots and powers for simpler operations.
If anyone has any ideas I'd greatly appreciate it.
Thanks.
 A: Since you're excluding "external libraries", I imagine you are considering only numbers in the range $0 \leq x < 2^{64}$. There are fewer than 100 Fibonacci numbers within that range; you could just store all of them in a look-up table.
A: Here's the algorithm I use; you can decide if it is suitable for your purpose.
First, if the number fits into a machine word, use a binary search to determine if it is a Fibonacci number.
Otherwise, reduce mod 17711. If the residue is not 0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 15127, 16724, 17334, 17567, 17656, 17690, 17703, 17708, 17710, the number is not a Fibonacci number. (This excludes 99.8% of 'random' numbers.)
If it passes that test, calculate $k=5n^2+4$. If $k$ is a square, or if $n>0$ and $k-8$ is a square, then the number is a Fibonacci number; otherwise not.
Of course implementing these will require a way to work with numbers larger than wordsize; I leave that to you.
A: Recall that the $k$'th Fibonacci number, $F_k$ is given by the formula
$$
F_k = \frac{1}{\sqrt{5}}\left( \left( \frac{\sqrt{5}+1}{2} \right)^k-\left( \frac{\sqrt{5}-1}{2} \right)^k\right)
$$
Since $(\sqrt{5}-1)/2<1$ it follows that $ F_k \approx \frac{1}{\sqrt{5}}\left( \frac{\sqrt{5}+1}{2} \right)^k$ (and the error is less than 1), taking the logarithm gives
$$
\log (\sqrt{5}F_k) \approx k \log((1+\sqrt{5})/2) 
$$
i.e. 
$$
k \approx \frac{\log(\sqrt{5}F_k)}{\log((1+\sqrt{5})/2)}
$$
Plug in the number you want to test if it is Fibonacci as $F_k$, then compute $k$, round up and finally compute what $F_k$ would be and check if that was the number you had.
This can verify whether the number is Fibonacci in $\mathcal{O}(\log(k))$ time or $\mathcal{O}(\log(\log(F_k)))$ if you'd like.
You can repeat all this using eigenvalues and diagonalisation using
$$F_k = \begin{pmatrix}0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^k\begin{pmatrix}1& 0 \end{pmatrix} $$
but it is essentially the same.
A: I assume you mean this:
$$\left ( \begin{array} \\ 1 & 1\\1 & 0 \\ \end{array} \right ) ^k = \left ( \begin{array} \\ F_{k+1} & F_k\\F_k & F_{k-1} \\ \end{array} \right )$$
Here is a fast algorithm for computing powers of that matrix.  I can't vouch for it because I have not used it, but it looks OK.
A: As long as you are using a reasonably realistic model of computation, even if you know $N$ it will take $O(N)$ time just to test whether your number is equal to $F_N$!  Think about how many digits it has.
