How do i compute $f_n = 3f_{n-1} + 2\sqrt{2f_{n-1}^2 - 2}$ for $n$ around $10^{18}$? So I have the recurrence $$f_n = \begin{cases}
3f_{n-1} + 2\sqrt{2f_{n-1}^2 - 2}, &n > 1\\
3, &n = 1\\
\end{cases}$$
and I need to compute it in $O(\lg n)$, for $n$ as big as $10^{18}$.
I tried to reduce it to a closed form equation but I don't see how that could be achieved.
 A: This should help:
Let $x=f_{n+1}$, $y=f_n$ and $z=f_{n-1}$, then we have after squareing $$x^2-6xy+y^2=-8$$ and $$y^2-6yz+z^2 =-8$$
If we substract these two we get $$(x-z)(x-6y+z)=0$$
Since clearly these sequance is increasing, we can't have $x=z$, so $$x =6y-z$$ or $$f_{n+1}=6f_n-f_{n-1}$$
A: For an integer $n\geq 1$, let $a_n$ and $b_n$ be integers such that $(3+2\sqrt{2})^n=a_n+b_n\sqrt{2}$.  Prove by induction that $f_n=a_n$ for every $n=1,2,3,\ldots$.  This shows that
$$f_n=\frac{(3+2\sqrt{2})^n+(3-2\sqrt{2})^n}{2}=\left\lceil\frac{(3+2\sqrt{2})^n}{2}\right\rceil$$
for all integers $n\geq 1$.  Taking $n$-th powers can be computed with time complexity $\mathcal{O}\big(\log_2(n)\big)$.
A: In the programming contest this is apparently taken from, you may want to use (long long) integer arithmetic only to compute $f_n$. This will come in handy:
Suppose we know $f_{n+1}=af_n+bf_{n-1}$ for all $n$. 
Then 
$$ \begin{pmatrix}f_{n+1}\\f_n\end{pmatrix}=\begin{pmatrix}a&b\\1&0\end{pmatrix}\begin{pmatrix}f_{n}\\f_{n-1}\end{pmatrix}$$
and consequently by induction 
$$ \begin{pmatrix}f_{n+1}\\f_n\end{pmatrix}=\begin{pmatrix}a&b\\1&0\end{pmatrix}^n\begin{pmatrix}f_{1}\\f_{0}\end{pmatrix}.$$
Then recall that computing $n$th powers can be done in $O(\log n)$ by square-and-multiply.
Also, if you know that $f_n$ fits into your favourite integer type on a two's complement machine, you need not worry about any overflows in the computations above.
