# external angle

All rays landing at the same periodic point have the same period: the common period of the rays is a (possibly proper) multiple of the period of their landing point; therefore one distinguishes: the ray period from the orbit period.

# The doubling map

How to find the period of angle under doubling map
* visual
* numerical
** read period from denominator of decimal fraction ( reduced rational fraction m/n )
** find period/preperiod in the binary expansion ( binary sequence)
*** string matching algorithms, for instance, naive or brute-force search, Knuth-Morris-Pratt algorithm
*** discrete Fourier transform
** read it from the itinerary of angle under doubling map
Period of binary expansion of reduced rational fraction m/n is equal to the multiplicative order of 2 modulo n:
$Period_{2}(m/n)={ord}_{n}(2)$
* orbit of angle 5/31 under doubling map

## Haskell version

Haskell version
Conversion from an integer type (Int or Integer) to anything else is done by "fromIntegral". The target type is inferred automatically

# Complex quadratic map

* island
* distortion of the island
* centers of componenets
* math.stackexchange question: function-to-calculate-the-period-of-a-mandelbrot-set-point

## What c parameters are hard cases when computing period ?

* boundary and near boundary points ( parabolic, Siegel, Cremer)
* "for example, c=1/4−10^{−10} takes over 800000 iterations to reach a fixed point in double precision floating point, but 20 iterations of Newton's method suffice to reach a fixed point. The two fixed points are slightly different, but both are fixed (each to themselves) in double precision." - Claude Heiland-Allen
* " You may need very small epsilon and very large n, otherwise for example c=−3/4+10{−10} will probably give an incorrect period of 2 instead of the correct period of 1, which error will compound to an incorrect interior distance estimate (for example distance 3.8e-8 with your method (epsilon 1e-12, n 79,573,343) instead of 2e-10 with my method). " Claude Heiland-Allen
* "one can iterate a "whole lot" of times, then see if the last iteration equals any of the previous iterations. However, such methods are never foolproof. Typically, they fail when used on points that are comparatively close to the boundary of their mu-atom. In such cases the algorithm will usually "find" an integer multiple of the actual period. This happens because as you get close to a child mu-atom, the points approaching the limit cycle converge in a spiral or pinheel-like manner. For example, imagine the period is actually 5, and our point is close to a child mu-atom with period 35. If you look at each 5th iterate, you'll typically find a pattern that spirals in on a limit point, taking 7 steps to go each time around the spiral. Because of the spiral pattern, the 7th step (35th iteration) is a lot closer than the 1st step (5th iteration), and simple period-finding algorithms will catch the closer one." Robert Munafo From the Mandelbrot Set Glossary and Encyclopedia
Solution:
* do not use naive method for computing period by iteration
* use Robert P. Munafo's Jordan curve method

## checking the period using position of parameter = periodicity checking

* https://www.shadertoy.com/view/4sdXWX
* Period_detection on the parameter plane

### Jordan curve method

* Period from the Mandelbrot Set Glossary and Encyclopedia, by Robert Munafo, (c) 1987-2017.
* periodicity_scan using the box period Jordan curve method by Claude Heiland-Allen
C code from mandelbrot-numerics library by Claude Heiland-Allen

## Finding period of the orbit

* critical orbit with 3-period cycle
* periodic components of M set
* Drawing Julia set and critical orbit. Computing period
* Computing period for drawing Mandelbrot set
Methods :
* direct period detection from iterations
* the spider algorithm
* "methods based on interval arithmetic when implemented properly are capable of finding all period-n cycles for considerable large n." (ZBIGNIEW GALIAS )
* Floyd's cycle-finding algorithm
Finding period is used to :
* draw components of Mandelbrot set
* Interior DEM/M

### Period of critical orbit

Finding period of critical orbit using forward iteration of critical point :

#### c

* code by Claude
Comparison of 2 functions for finding a period :
Non-linear scale shows bigger periods ( along real slice of Mandelbrot set ) :

#### c#

User:Simpsons_contributor: periodicity_checking

# References

* ↑ H. Bruin and D. Schleicher, Symbolic dynamics of quadratic polynomials, Institut Mittag-Leffler, The Royal Swedish Academy of Sciences, 7.
* ↑ math stackexchange question: period-of-a-finite-binary-sequence
* ↑ lavaurs' algorithm in Haskell with SVG output by Claude Heiland-Allen
* ↑ Rigorous Investigations Of Periodic Orbits In An Electronic Circuit By Means Of Interval Methods by Zbigniew Galias
* ↑ Mandelbrot set drawing by Milan

# See also

* Cycle detection at wikipedia
* Period at wikibooks
* Periodic point at wikibooks
* Finding period of angle under doubling map
* periodic points in wikipedia
* Period_detection