Orbit Detection

Robert P. Munafo, 2008 Mar 14.

Describes a set of closely-related techniques for detecting a limit cycle period in the iterates of a point, with the goal of speed-optimization by terminating the process of iteration before the dwell limit is reached.

Orbit-detection is one type of orbit-based optimization. See that heading for references to others; see also speed improvements.

It is relatively easy to detect the existance of orbits. Finding the actual period of the limit cycle is more difficult, because of roundoff and approximation errors. See period for algorithms that determine the period.

The following techniques for orbit detection are commonly used:

Floyd's algorithm, called the "RHOP algorithm" by the Scientific American article. Two values of Z are iterated. Both start out at the same value, and both use the same value of C, but one is iterated twice per loop while the other is iterated once.

let z_fast = c let z_slow = c while (still iterating) let z_fast = z_fast ^ 2 + c let z_fast = z_fast ^ 2 + c let iter_fast = iter_fast + 2 let z_slow = z_slow ^ 2 + c let iter_slow = iter_slow + 1 if (z_fast equals z_slow) then comment orbit has been detected let period = iter_fast - iter_slow end if end while

This method is guaranteed to eventually find an orbit if one exists, however the value of "period" that is found this way will usually be an integer multiple of the true orbit period.