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.

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}$$
