END OF AN ERA, FRACTALFORUMS.COM IS CONTINUED ON FRACTALFORUMS.ORG

Wikipedia.

Basically it works like this. You have some sequence defined by a recurrence, a function to get the next element from the previous. You also have a starting point. Brent's algorithm works like this: first you calculate the function to get element two and compare to the starting point. Then you save element two and calculate element three, compare it to two. If still no cycle, calculate element four and compare to two. Save element four now and for points five through eight compare to that. Then save eight.

That is, you maintain a saved point from earlier in the sequence, compare every new element to the saved point, and every time the orbit length reaches a power of two you update the saved point to the current one.

Cycles of any length can be detected and there's no need to perform extra tandem iterations or anything like that; just store and compare values. So the overhead is fairly low, about the same as checking for a known finite attractor (the difference from that is logarithmic in the number of iterations).

BTW, to quickly find out if an integer N is a power of two, you can test

((N - 1) & N) == 0

On most processors, the comparison to zero is optimized away completely, so this takes just two simple computational instructions and a branch.


(The above expression clears the rightmost 1 bit. The result is zero if and only if there was at most one 1 bit, i.e. for powers of two and N == 0.)

Great explanation of Brent's algorithm. I'm going to try that for sure. What I do is I save the whole sequence and periodically check for cycles. This is useful if you want to measure the length of the cycle and/or find the starting point of the cycle. The length of the cycle seems to correlate to the number of "spiral arms" in the galaxy-like shapes generated by the orbits. For example:

http://www.butterflyeffect.ca/Close/Pages/SpaceTimeFluctuations.html

The dynamic or orbit this web page has 5 spiral arms so the cycle count is five. This is really interesting because the cycle only happens because of the limited resolution of the floating point processor in the computer. If we had an infinite number of bits or digits of precision, then the cycle would never happen. NOTE: the cycle we are talking about here is different than the orbital periods within the primary bulbs of the M-Set. For instance, a period 3 orbit might have a cycle count of 10 or 100 depending on how close to the "event horizon" you are.

Hope this makes sense...

In what order do they appear?

So, it's visually a double spiral, but if you connect the points in order of their appearace, they actually are on a single spiral.

Apologies, I just realised that you probably meant proving that all the truly complex attractors (i.e. non-zero real and non-zero imaginary) are irrational ? Which I guess may be true though I'd be surprised if it was, my reasoning being that the attractors vary smoothly from one point to another (given infinitessimal steps) and I suspect most/all values within a given 2D range are covered hence the likelihood that some values are rational complex.

You need to ignore the actual value and consider the value that it's tending towards, I mean if you take the point (0.25,0) and you use infinite precision then your orbit value will never actually reach (0.5,0) even though that is the attractor.
Also apart from the "obvious" points such as (0,0) or (0.25,0) etc. then you'll (probably) never be able to find a rational one by experimentation, you'll only find them analytically because experimentally the number of irrational attractive values is orders of infinity more than the number of rationals.