periodicity-checking.md

Periodicity checking

"Periodicity checking" is a performance optimisation technique used in fractal image generation. This technique 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:

$$z = (0,0) c = (0,0) f(z) = z² + c f(0) = 0 f(1) = 0 f(2) = 0 f(3) = 0 f(4) = 0 f(5) = 0 f(6) = 0 ...$$

Obviously the series does not tend to infinite.

Point (0,i) also belongs to the set:

$$z = (0,0) c = (0,i) f(z) = z² + c f(0) = 0 + 1i f(1) = -1 + 1i f(2) = 0 - 1i f(3) = -1 + 1i f(4) = 0 - 1i f(5) = -1 + 1i ...$$

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:

$$z = (0,0) c = (-1,0) f(z) = z² + c f(0) = 0 f(1) = 2i f(2) = -4 + 2i f(3) = 12 - 14i f(4) = -52 - 334i f(5) = BIG (meaning far from the origin) f(6) = BIGGER ...$$

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" technique 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 or this one 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.

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.

In 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 checking 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 it's not possible 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:

Acknowledgements

Two articles where specially useful for us to understand periods in Mandelbrot Set. In fact, we would say this article explanation is very similar to the one by Robert L. Devaney, simply adding more graphs.

• Julien Clinton Sprott
• Robert L. Devaney

Links

Period checking explanations:

1. Basic explanation
2. Mandelbrot Set Chaos
3. What is the period of the "primary bulbs"
4. Periods of the Bulbs
5. Iterations

Cycle detection:

1. Wikipedia article about cycle detection and different algorithms implementation
2. Blog post explaining Brent's Cycle Detection Algorithm by David Aramant
3. Wikipedia explanation for Brent's algorithm supposedly used by Gnofract 4D
4. Explanation about the orbit detection technique
5. Short explanation about the periodicity checking technique
6. How Fractint software implemented it
7. Orbit detection

Sample implementations:

1. C implementation using Gnofract 4d
2. Another C implementation with arbitrary precision
3. Java implementation

Orbit visualization:

1. Draw orbit with lines between point in the series

Math:

1. Periodic points of complex quadratic mappings
2. How to find periodic points for given period
3. Paper: The size of Mandelbrot bulbs

Wiki/Books:

1. WikiBook about fractals

Images:

1. Mandelbrot Set with periodicities coloured

Software using perdiodicity checking:

1. Gnofract 4D