(Note: The original version of the question generated 1 upvote. Adding various explanatory comments in 3 subsequent Edits, generated 2 downvotes, which leads me to think added in the overall confusion, so I am reverting this back to the original. Eric Towers covered the question with his answer sufficiently.)
How can I extract the period of an eventually periodic sequence $a_n$, other than manually examining the entire orbit and making comparisons?
If my function is $f(z)$, my starting point is $z_0$, denoting the iterates of $f$ as $f^{(n)}(z)$, $n\in \mathbb{N}$, the orbit will be: $\{z_0, f(z_0), f^{(2)}(z_0), \ldots,f^{(n)}(z_0),\ldots\}$, and the sequence is given by $a_n=f^{(n)}(z_0)$, with $a_0=z_0$, etc.
A necessary (but not sufficient – depends on precision $\epsilon$, etc) condition for an eventually $p$-periodic convengence is obviously $|a_{n+p}-a_n|\le \epsilon$, for given $\epsilon>0$, so if I check a (finite always) orbit backwards starting at the last point $a_N$ for matches, then if the condition is satisfied for $a_N$ and $a_{N-p}$, then that's close to the converging period being $p$.
This calculation obviously contributes at least $O(N)$ for each point on my graphics plane in the worst case and stalks badly the calculations for the overall convergence.
Is there a faster way to check a finite list of values of $a_n$ for (almost – eventual) periodicity, under the assumption that $a_n$ is eventually periodically convergent?
Best Answer
You describe a search for a cycle in iterated function values. This is called "cycle detection".
If exact computation is possible in reasonable time (for instance if this is a sequence of integers), Floyd's algorithm finds the period in time $O(\mu +\lambda)$, where $\mu$ is the index of the first element of the cycle and $\lambda$ is the period. It requires $O(1)$ storage (since it only ever stores two sequence values). Brent has a similar algorithm with the same asymptotics. There are several algorithms that trade increased space complexity for time complexity.
If exact computation is not possible, then you are looking at "approximate period detection" (example paper). There are various definitions of approximate period, for instance this, this, and this. Algorithms strongly depend on what sort of approximation you are willing to use. A method is to use the Fourier transform to estimate the period -- note that this makes no claim that the values of the sequence approximately repeat.
If you attempt to use an exact method for an inexact iterator or inexact sequence, then you should not expect the algorithm to ever find a period. See chaotic iterated maps, for instance the logistic map -- (imagine that your iterations should be right at the edge of a transition from periodic to chatoc behaviour. If you had infinite working precision, you could stay on the periodic side, but since you don't you should expect unpredictable transitions from periodic to chaotic behaviour and back.)