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

-
What do you mean by "the matrix method"? And how, exactly, does <cmath> rate as an external library? If you have some esoteric requirements, it would be worth stating them explicitly. –  Hurkyl Feb 6 '13 at 2:19

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.

-

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.

-
Wow, pretty nifty. Do you have some pointers explaining the part about $k$ or $k-8$ being square. –  Peder Feb 6 '13 at 2:46
A number $n>0$ is a Fibonacci number if and only if one of $\sqrt{5n^2\pm4}$ is an integer. Everything else surrounding that is just an attempt to resolve the question more quickly. –  Charles Feb 6 '13 at 2:47
@Peder: One proof is to look at the number field $\mathbb{Q}(\sqrt{5})$ whose ring of integers is $\mathbb{Z}[\varphi]$. There is an identity $\varphi^n = F_{n-1} + F_n \varphi$, and $N(\varphi) = -1$: $\varphi$ is a fundamental unit. Given a value $b$, you can ask the question "Is there an $a$ such that $N(a + b \varphi) = \pm 1$?". This is a quadratic equation in $a$ whose discriminant is $5b^2 \pm 4$. Presumably (I haven't worked through the rest of the detail), the information above proves that, should an integer $a$ exist, that $a + b \varphi$ is a power of $\varphi$. –  Hurkyl Feb 13 '13 at 5:51

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.

-
...assuming that you have available sqrt(5) to the desired accuracy and can compute your logs to the necessary accuracy - both of which are trickier than you might think. This is $O(\log k)$ real operations, but computation on arbitrary reals is a rather dangerous thing to allow when trying to compute complexity, and it takes many more bit operations. –  Steven Stadnicki Feb 6 '13 at 2:09
Yes, agreed the computationally complexity is misleading, but it is clearly faster than trying computing $F_k$ until you become bigger than the number. In any case, even an approximate value of $\sqrt{5}$ will give you an approximate value for $k$. That greatly reduces the amount of computation you need to do to find the exact value of $k$. Even an approximate value of $\sqrt{5}$ will probably give you a value of $k$ that is exact up to rounding up to the nearest integer, unless your $k$ is ridiculously large. Try it for $n=500$ for example. –  Peder Feb 6 '13 at 2:16
Follow up. I found that $F_{500} = 1.39*10^{104}$ on Wolfram alpha, and $\hat{k}=\log(\sqrt{5}1.39*10^104)/\log((1+\sqrt{5})/2)=499.99$ and rounding up gives $k=500$! No need for a particularly accurate value of $F_{500}$ of $\sqrt{5}$ here. Of course to verify that the number was really Fibonacci, we need to plug back $k$ into the formula for $F_k$. This is where my $\mathcal{O}(\log(k))$ cost came from. –  Peder Feb 6 '13 at 2:24
I think the second term in your first equation should be $\left( \frac{1-\sqrt{5}}{2} \right)^k$. –  Tpofofn Feb 6 '13 at 3:26

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.

-

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.

-