You have builŠµ a Fibonacci (?) field $Q[x]/(x^2-x-1)$. Every element of this field can be written as binomial, so it has representation in 2x2 matrices:
$$
ax+b\qquad\Leftrightarrow\quad \begin{pmatrix}a+b & a\\ a & b\end{pmatrix} = aF+bI
$$
You can check that $F^2=\begin{pmatrix}1 & 1\\ 1 & 0\end{pmatrix}^2=F+I $
You $O(\log n)$ algorithm is a well known the Doubling Method, which is essentially fast multiplication algorithm for matrix $F$.
To generalize, you should just select right first element. So in ordinary fibonacci, you start with (1,0), which is $X_1=1x+0$, next element is $X_2=x X_1$, then $X_3=x^2 X_1$ and so on. If you want to start with (-1, 2), then $Y_1=-1x+2$, $Y_2=x Y_1$, $y_3=x^2 Y_1$ and so on. You can use the same algorithm of fast multiplication to find $Y_n$.
Edit. As an example, I want to show how to build a tribonacci field $Q[x]/(x^3-x^2-x-1)$.
If we have $y=\alpha x^2+\beta x+\gamma$, then $$xy = \alpha x^3+\beta x^2+\gamma x = (\beta+\alpha)x^2 + (\gamma+\alpha)x+\alpha$$
So element $x$ is equivalent to matrix:
$$
T = \begin{pmatrix}1 & 1& 1\\ 1 & 0&0\\0&1&0\end{pmatrix}.
$$
So our field can be represented with $Q[I, T]$
A proof of integrality can be based on elementary algebra and some fortunate observations. The Darij Grinberg comments reminded me of some of my work I did in 2013 and which I did
not follow up on adequately.
Factorization of the $\,a_n\,$ sequence suggests the Ansatz
$$ a_n = p_n p_{n+1} p_{n+2} p_{n+3} $$
where $\,p_n\,$ is some sequence yet to be determined.
The sequence $\,a_n\,$ is supposed to satisfy a recurrence. For example, we must have
$$ a_4a_0 = (a_1+a_2)(a_2+a_3). $$
Rewriting this equation in terms of $\,p\,$ and solving for
$\,p_7\,$ gives the rational solution
$$ p_7 = \frac{(p_1 + p_5)(p_2 +p_6) p_3 p_4}{p_0 p_1 p_6}. $$
Rewrite this as a polynomial equation to get
$$ p_6p_0p_7p_1 = (p_1 + p_5)p_3(p_2 + p_6)p_4. $$
Now suppose that $\,p_n\,$ satisfies the recurrence
$$ p_n = p_{n-3}\frac{p_{n-1} + p_{n-5}}{p_{n-6}}. $$
Check that this recurrence satisfies the polynomial
equation for $\,p_7.\,$
From the $\,p_n\,$ recurrences for $\,n=9\,$ and
$\,n=6\,$ we have
$$ p_9p_3 = (p_4 + p_8)p_6 \quad \text{ and }
\quad p_6p_0 = (p_1 + p_5)p_3. $$
Combine the two equations to simply get
$$ (p_0 + p_4 + p_8)p_6 = (p_1 + p_5 + p_9)p_3. $$
This implies that the number
$$ c := \frac{ p_0 + p_4 + p_8 }{p_3 p_4 p_5} =
\frac{ p_1 + p_5 + p_9 }{p_4 p_5 p_6}$$
is constant and thus, the sequence $\,p_n\,$ satisfies the
equation
$$ p_{n}+p_{n-4}+p_{n-8} = c\,p_{n-3}p_{n-4}p_{n-5}. $$
By the way, defining another constant
$$ s := \sqrt{(a_2+a_1)a_2a_0/(a_3a_1)} $$
implies the equation
$$ c = s\frac{(a_0+a_1+a_2)(a_1+a_2+a_3)}{a_0a_2(a_1+a_2)}, $$
or more symmetrically, this can be written as
$$ c = \frac{(a_0+a_1+a_2)(a_1+a_2+a_3)}
{\sqrt{a_0a_1a_2a_3(a_1+a_2)}}. $$
Given values of $\,p_0\,$ and $\,p_1\,$ then
$\,p_2 = s/p_0\,$ and $\,p_3 = a_0/(p_1s)\,$
while the two sequences are related by
$\,p_n = p_{n-4}a_{n-3}/a_{n-4}.\,$
If the sequence terms $\,p_0, p_1,\dots, p_7\,$ are integers
and the constant $\,c\,$ is an integer, then this implies that
$\,p_n\,$ is an integer sequence, and also $\,a_n\,$ using the
Ansatz. In our case, $\,c=6\,$ and the sequence $\,p_n\,$
begins $\,1,1,1,1,1,1,2,3,4,10,33,140,\dots.\,$
This sequence was known to me in 2013 but I
do not think I connected it to A248049 at that time.
A simpler example of a sequence similar to $\,p\,$
is OEIS A064098 with
$$ a_na_{n-3} = a_{n-1}^2 + a_{n-2}^2 $$
and now with a constant
$$ c := \frac{a_n^2+a_{n+1}^2+a_{n+2}^2}
{a_na_{n+1}a_{n+2}} $$
such that the sequence $\,a_n\,$ also satisfies
$$ a_n + a_{n-3} = c\,a_{n-1}a_{n-2}. $$
Best Answer
You are iterating the function $f(x) = x + \sin(x)$. This is a nondecreasing function because $f'(x) = 1 + \cos(x) \ge 0$, and it has fixed points at multiples of $\pi$. If $x_0 < x_1 = f(x_1)$, we will have $x_i < x_{i+1}$ for all $i$. Since it is bounded above (by the next fixed point), it has a limit, and that limit can only be a fixed point. Similarly, if $x_i > x_{i+1}$ the sequence decreases to a limit at a fixed point. The fixed points for which $f'(x) = 0$ (namely the odd multiples of $\pi$) are stable. For $x$ near $k \pi$ where $k$ is odd, the Taylor series says $$ f(x) \approx k \pi + \frac{(x - k \pi)^3}{6}$$ so the "error" in the next iteration is approximately $1/6$ the cube of the error in this iteration. That makes it converge very rapidly.