I just thought of a possible adjustment to my implementation of the algorithm for tracing external rays in the complement of the Mandelbrot set using Newton's method: instead of using the previous ray endpoint as initial guess for the next ray endpoint, extrapolate from three previous ray endpoints assuming the ray is approximately a geometric progression (aka logarithmic spiral):

guess r_{n+1} = r_n + \frac{ (r_n - r_{n-1})^2 }{ r_{n-1} - r_{n-2} }

Another alternative is to assume it's a straight line with length in geometric progression:

guess r_{n+1} = r_n + (r_n - r_{n-1}) \left| \frac{ r_n - r_{n-1} }{ r_{n-1} - r_{n-2} } \right|

Will have to do some benchmarking to see which is best in terms of speed; test cases should include both periodic (minibrot and bulb cusps / roots / bonds) and pre-periodic (Misiurewicz points aka spiral centers) rays. Tests should also check for correctness first.

The trouble with the current algorithm (using $guess r_{n+1} = r_n$) is that it needs many points in each dwell band (I typically use a "sharpness" of 4 to 8), maybe this modification could allow reducing that. Runtime is O(sharpness * depth^2) so this could be a nice speed boost.


It works well in some cases.

I found the nearest point algorithm (black line, previous implementation) is stable down to sharpness 2 in most cases (sharpness 1 fails immediately, unsurprisingly). This was a bit of a surprise, albeit a pleasant one.

The other pleasant surprise is that the new algorithm is ~2x faster for the same sharpness, presumably fewer iterations of Newton's method are needed to converge as the initial guess is better.

But they don't work for very low sharpness, and the linear approximation $r_{n+1} = r_n + (r_n - r_{n-1})$ fails often.

Caveat: I traced to dwell 1000 with low period rays, so the end result will be deep in a cusp: this is not a typical use case. Typical would be to trace to dwell 1000 with a period 500 ray, hopefully far enough for Newton's method to find the minibrot's nucleus.

· · Web · 1 · 0 · 0

sorry no image descriptions 

other cases did not do so well, the new algorithms failed for pre-periodic rays, and another periodic case had other problems

I wrote some code to test more typical use cases (generate random angle with period + preperiod ~= 500, trace ray to twice that depth) and the performance differences evaporated completely.

I calculated the mean and standard deviation of time(method M) / time(method 0) for sharpness from 2 to 8, partitioned into preperiodic rays and periodic rays:

method mean stddev
1 1.001 0.00801
2 1.002 0.0132
3 1.002 0.0128

method mean stddev
1 1.000 0.00461
2 1.002 0.01249
3 1.001 0.00618

OOPS the previous post had a typo in the code and was running (method 0, sharpness 8) always instead of comparing the different methods...

running the right implementations, the results are disappointing:

method 1 (linear extrapolation) takes ~68% of the time of method 0 (previous point), when it works, which is when sharpness is 7 or 8 (and presumably higher)

methods 2 and 3 (geometric extrapolation, restricted to a straight line for method 2, full curve for method 3) failed 100% of the time

68% speed boost of linear extrapolation vs nearest at sharpness 8 is not as good as 62% speed boost of sharpness 4 over sharpness 8 with nearest method for both.

Sign in to participate in the conversation

Welcome to post.lurk.org, an instance for discussions around cultural freedom, experimental, new media art, net and computational culture, and things like that.

<svg xmlns="http://www.w3.org/2000/svg" id="hometownlogo" x="0px" y="0px" viewBox="25 40 50 20" width="100%" height="100%"><g><path d="M55.9,53.9H35.3c-0.7,0-1.3,0.6-1.3,1.3s0.6,1.3,1.3,1.3h20.6c0.7,0,1.3-0.6,1.3-1.3S56.6,53.9,55.9,53.9z"/><path d="M55.9,58.2H35.3c-0.7,0-1.3,0.6-1.3,1.3s0.6,1.3,1.3,1.3h20.6c0.7,0,1.3-0.6,1.3-1.3S56.6,58.2,55.9,58.2z"/><path d="M55.9,62.6H35.3c-0.7,0-1.3,0.6-1.3,1.3s0.6,1.3,1.3,1.3h20.6c0.7,0,1.3-0.6,1.3-1.3S56.6,62.6,55.9,62.6z"/><path d="M64.8,53.9c-0.7,0-1.3,0.6-1.3,1.3v8.8c0,0.7,0.6,1.3,1.3,1.3s1.3-0.6,1.3-1.3v-8.8C66,54.4,65.4,53.9,64.8,53.9z"/><path d="M60.4,53.9c-0.7,0-1.3,0.6-1.3,1.3v8.8c0,0.7,0.6,1.3,1.3,1.3s1.3-0.6,1.3-1.3v-8.8C61.6,54.4,61.1,53.9,60.4,53.9z"/><path d="M63.7,48.3c1.3-0.7,2-2.5,2-5.6c0-3.6-0.9-7.8-3.3-7.8s-3.3,4.2-3.3,7.8c0,3.1,0.7,4.9,2,5.6v2.4c0,0.7,0.6,1.3,1.3,1.3 s1.3-0.6,1.3-1.3V48.3z M62.4,37.8c0.4,0.8,0.8,2.5,0.8,4.9c0,2.5-0.5,3.4-0.8,3.4s-0.8-0.9-0.8-3.4C61.7,40.3,62.1,38.6,62.4,37.8 z"/><path d="M57,42.7c0-0.1-0.1-0.1-0.1-0.2l-3.2-4.1c-0.2-0.3-0.6-0.5-1-0.5h-1.6v-1.9c0-0.7-0.6-1.3-1.3-1.3s-1.3,0.6-1.3,1.3V38 h-3.9h-1.1h-5.2c-0.4,0-0.7,0.2-1,0.5l-3.2,4.1c0,0.1-0.1,0.1-0.1,0.2c0,0-0.1,0.1-0.1,0.1C34,43,34,43.2,34,43.3v7.4 c0,0.7,0.6,1.3,1.3,1.3h5.2h7.4h8c0.7,0,1.3-0.6,1.3-1.3v-7.4c0-0.2,0-0.3-0.1-0.4C57,42.8,57,42.8,57,42.7z M41.7,49.5h-5.2v-4.9 h10.2v4.9H41.7z M48.5,42.1l-1.2-1.6h4.8l1.2,1.6H48.5z M44.1,40.5l1.2,1.6h-7.5l1.2-1.6H44.1z M49.2,44.6h5.5v4.9h-5.5V44.6z"/></g></svg>