Calculating the period of a mandelbrot bulb

[aluminumstudios]

Hello everyone,

I've been playing with my own C++ program to draw mandelbrots lately and I've been becoming more and more interested in the math and other technical aspects.

I would like to be able to calculate the period of a bulb if I know any point inside the bulb.

At first I thought this would be easy.  I take a point C and iterate it (Z=Z^2+C) and the number of iterations between Z having the same value twice would be the period.

I tried this and my software only registered a few points as having a period.  I did some more reading and saw that period detection is hard when using floating point (my C++ program uses long doubles) because if inherent inaccuracy in floating point numbers (I guess rounding error making the results ever so slightly different as calculations continue?)

So, my question is, is there a way to detect the period of the bulb given a point C from somewhere inside that bulb in a floating point implementation (even if it is slow)? 

My level is advanced novice, so please don't assume that I have a math degree or am an professional software developer if you give an explanation 

Thanks in advance!

[cKleinhuis]

this comes down to periodicity checking, when a point is reached that has exactly been reached
before, the iteration loop wont diverge. it does not matter if it is a 3rd or 4th deegree period - although it is interesting.

my most liked example for a period is the period at the fixed point (0.0,0.0) which has the simple 1 period,
in the other centers of minibrots, you find, even longer periods, did you know that plotting those orbits produce buddha brots?
 

[aluminumstudios]

I know that plotting the orbits produces Buddhabrots.  Here is a post I made the other day http://www.fractalforums.com/images-showcase-(rate-my-fractal)/relatively-new-to-here-my-buddhabrot/   (please note that my web host is pretty flakey, if the image doesn't appear in the thread at that link, please hit "refresh" and it should.)

I'm afraid I still need to know however, how to detect the period when using floating point math because when Z comes back around to what it was before, I might be a tiny amount off due to floating point rounding error.  Because of this a simple comparison doesn't work well to detect a period.  Is there a good trick to overcome this (other than changing to fixed point math?)

I don't want to detect that there is a period, but WHAT the period is.  That information is relevant to what I want to do.

[Timeroot]

Actually, it isn't that the period fails because of floating point error. What's actually happening is that it's approaching a period. But yes, small errors would have an effect if that wasn't the case. The thing is, you only hear about point that go directly into a period, such as (0,0) or (-1,0). But in reality, almost all points, such as (-0.9,0), only approach a period. (-0.9,0) eventually becomes period 2, but only after infinite time. Probably the best way is to set a small "radius", where if the point get's within that value, it's accepted as periodic. Such as, "If abs(z-oldz)<0.05 Then IsPeriodic()". Another option is seeing if it comes close repeatedly, with the same time interval each time, getting closer each time. If that is true, it is almost certainly periodic. This is obviously much harder to program, though! Good luck! 

[aluminumstudios]

Thanks for the reply.

Hmm, so it only approaches a period, it doesn't necessarily have an exact period itself ... at least no in the first few hundred or thousand iterations.

I wonder if there is a way to scan for periodic attractor?(I'm still learning the jargon) points within the portion of the plan that I am examining ...

[hobold]

I think there is no known algorithm that can give guarantees for the detected periodicity. But I think it should be possible to find approximations that turn out to work in practice. I am thinking of something with a tunable "accuracy" parameter, and with some adaptivity with respect to maximum iterations. Maybe along these lines:

1. iterate a few times as usual.

2. if the point didn't bail out, check if a distance estimate can safely determine this to be an outside point. if so, you are done (with respect to periodicity checking)

3. for all points in the orbit, compute the (square of the) distance to the final orbit position.

4. if the nearest orbit point is within "accuracy" of the final position, then use that nearest point to determine periodicity. otherwise, do another chunk of iterations (to allow the orbit to converge further) and goto step 2.

This algorithm is probably not ideal, but might be enough to start some experiments.

[lkmitch]

I think the basic ideas for periodicity checking with floats are to:  1) iterate "several" times before checking, to allow the orbit to settle into a pattern, and 2) check that the difference between subsequent iterates and your reference iterate is less than some small positive value (i.e., don't check for exact equality).

Part of the fun of the Mandelbrot set is that there are different types of orbits and some that seem headed in one direction can wind up going off in another, so periodicity checking is not an exact science.  Also, the closer the c value is to the boundary of its component (or further from its center), the harder it is to check.  The "center" point (e.g., 0+0i or -1+0i) has an orbit that goes exactly through 0+0i; boundary points will have larger "smallest" points.