"Periodicity checking" is a performace optimisation techniche used in fractal image generation. This techniche is used to reduce the number of calculations needed to calculate a pixel in the image, therefore reducing the time to generate the full fractal image. For the classic way of generating a Mandelbrot Set image you need to calculate a series of values applying the Mandelbrot formula recursively.
The basic Mandelbrot Set formula is:
f(z) = z² + c
In order to generate a fractal image a complex point on the plane is assigned to a pixel in the image.
For a very basic color map (black color inside the fractal and white color outside) you need to find out if the complex number belongs to the Mandelbrot Set. A complex number belongs to the Mandelbrot Set when using that point as c variable in the basic formula and applying the formula recursively the series does not diverge.
If you color points inside with black you get something like:
We can calculate some points for that picture. For example, the complex number (0,0) belongs to the Set and this is the series:
Obviously the series does not tend to infinite.
Point (0,i) also belongs to the Set:
This series values are: i, -1, -i, -1, -i, -1, ...
This is the orbit for c = (0,i):
Orange is the real part and blue the imaginary part.
Point (0,2i) not belonging to the Set:
This is the orbit for c = (0,2i):
Orange is the real part and blue the imaginary part.
We always start with z = 0 and that's called the orbit of 0 under iteration of z² + c. Under iteration of f(z) = z² + c, either the orbit of 0 goes to infinity, or it does not. The Mandelbrot Set represents the Set of complex numbers whose fate for the orbit of 0 under iteration of f(z) = z² + c does not diverge, that's to say it does tend to infinite.
When the orbit does not go to infinity, it may behave in different ways. It may be fixed or cyclic or behave chaotically. This is the list of possible behaviors:
- Tends to a fixed point (inside)
- Chaotic behavior (inside)
- Chaotic behavior close to n-cycle (inside)
- Period n (inside)
- Go to infinite (outside)
"Periodicity Checking" tecniche consist on detecting the cycles when we are calculating the orbit for a point c, that way we can stop iterations, becuase we know that the series is not going to diverge.
In the plots below, we have displayed the iteration series for z² + c for the orbit of 0, with different orbits periods. You can see two different graph types: real and imaginary vales and orbit lines (lines beetween the points in the series).
Point (-0.495,0.396), tends to a fixed point (period 1):
https://mandelbrot-set-periods.online/api/orbits?zx=-0.495&zy=0.396
Point (-1.101,0.100), period 2:
https://mandelbrot-set-periods.online/api/orbits?zx=-1.101&zy=0.100
Point (-0.100,0.764), period 3:
https://mandelbrot-set-periods.online/api/orbits?zx=-0.100&zy=0.764
Point (0.286,0.538), period 4:
https://mandelbrot-set-periods.online/api/orbits?zx=0.286&zy=0.538
Point (-0.506,0.566), period 5:
https://mandelbrot-set-periods.online/api/orbits?zx=-0.506&zy=0.566
As you can see points inside the set have orbits which are trapped inside the limits of the Mandelbrot Set. You can use this site to see the orbits with lines:
http://www.stefanbion.de/fraktal-generator/mandeliteration.htm
Or this one:
https://mandelbrot-set-periods.online
which is a Mandelbrot Periods Explorer.
If you want to know the cycle length for the different bulbs (a bulb is a cardioid or circle section of the Mandelbrot Set), this is how it looks like:
There are different algorithms for cycle detection. One of them is the Brent's algorithm. You can find an implementation here: https://github.com/josecelano/c-mandelbrot-arbitrary-precision/blob/master/src/cycle-detection/brent.c
One of the properties of this cycles is the more you are closer to the fractal border the more iterations you need to became a stable cycle. You also need to increase the tolerance to detect cycles, that means cycles are not pure, the repeated values is not exactly the same.
If fact this application is not able to detect correctly all the periods. If you want to contribute there is an open issue:
There are some fixed and hardcoded values for minimum number of iterations before checkinng periodicity, the period tolerance and the maximum number of interations. Those values should be calculated dinamically depending on the area, zoom, or other parameters of the image you are rendering.
We have not found a formula for that. We think most of the formulas out there are not exact. And we think it's not posible to find a formula for that in order to draw a perfect Mandelbrot Set with colored periods. This is the best approximation we have been able to generate:
Two articles where spaceilly useful for us to understand periods in MandelbBrot Set. In fact, we would say this article explanation is very similar to the one by Robert L. Devaney, simply adding more graphs.
Period checking explanations:
- Basic explanation
- Mandelbrot Set Chaos
- What is the period of the "primary bulbs"
- Periods of the Bulbs
- Iterations
Cycle detection:
- Wikipedia article about cycle detection and different algorithms implementation
- Blog post explaining Brent's Cycle Detection Algorithm by David Aramant
- Wikipedia explanation for Brent's algorithm supposedly used by Gnofract 4D
- Explanation about the orbit detection technique
- Short explanation about the periodicity checking technique
- How Fractint software implemented it
- Orbit detection
Sample implementations:
- C implementation using Gnofract 4d
- Another C implementation with arbitrary precision
- Java implementation
Orbit visualization:
Math:
- Periodic points of complex quadratic mappings
- How to find periodic points for given period
- Paper: The size of Mandelbrot bulbs
Wiki/Books:
Images:
Software using perdiodicity checking: