Best Mandelbrot Bailout Methods

[Timeroot]

The "classic" bailout method for the Mandelbrot set is |z|>4. But I've been trying to come up with other methods, which will hopefully give speedups. An example of a relatively simple one is Re(z)>2, or abs(Im(z))>1.1275707. Both of these can potentially give speed-ups, without clipping. And while the MSet may look ugly at a low zoom, these other tests all smooth out at high depths.

I'm trying to write a formula with many different bailout methods, that can possibly be checked or unchecked by the user - with any luck, this will increase speed.

These bailout formulas are based on "cutting off" different parts of the Antibuddhabrot fractal, so that only the illuminated parts remain. Here are some ones I've got so far:
|z|>4
abs(Imag(z))>1.1275707
Real(z)<-1.5&&abs(Imag(z))>0.270228
abs(Imag(z))>0.1&&Real(z)<-1.5 + 0.11*abs(Imag(z))
Most of these are "cutting" in straight lines. Note that you cannot just cut out areas outside the Mset; they need to be outside the Antibuddhabrot.

I'm hoping somebody can give more bailout formulas? I'm only looking for ones that are quick to calculate, and do not results in any clipping. Thanks to anyone who helps! 

[hobold]

Some of the simple bailouts, like Re(z)>2, can potentially make computation slower. Imagine an orbit that spends several extra iterations in the Re(z)<-2 half plane, even though it has already escaped.

I think it will be hard to beat the standard. The squares of x and y have to be computed as part of the iteration anyway, so they are available "for free" when checking for bailout.

Nonstandard exit criteria still have their place as artistic variations, or to emphasize more of the structure surrounding the Mandelbrot set.

[Timeroot]

I'm combining these various bailouts, though - if it bails out for any of these conditions, then it stops iterating. So I obviously don't use Re(z)>2, since this is included in |z|>4. But by combing, I can get faster things.

[hobold]

So you are looking for tight bounding volumes that contain the Mandelbrot Set, and compute faster than the usual bounding sphere. With "fast" meaning practical computation time on a real machine.

Hmm. The usual |z|^2 <= 4 needs just one add, one compare, and one conditional branch (assuming that the squares of real and imaginary part are already provided). On most current hardware, basic floating point arithmetic is executed with a throughput of one instruction per cycle, with short latencies on the order of 4 to 8 cycles.

There simply is not much computation time left that could be reduced further. Remember that the bailout test is done for every iteration, so the times for doing a few extra tests quickly adds up. Tighter bounds can at best reduce the computation time by a fixed number of iterations. But the closer you get to the Mandelbrot Set, the more iterations you need. So eventually, the increased computational cost per iteration will outweigh the constant per pixel gain.

[Timeroot]

Actually, I tried the methods I listed above on a very deep zoom of the Mandelbrot Set - Maginification: 1.85E33 - and it gave about an 8% time gain over the regular Mandelbrot. Of course, it was only one test, and I didn't compare with the built-in formula, but I think that if it's designed for efficiently it might work well. For example, just today I read in The Beauty of Fractals that the rule |z|>4 can be improved to |z|>cabs(#pixel)+2. This doesn't give much speed, but it's something. Another one is |z|>2+(cabs(#pixel)+|#pixel|)/3. I don't know why that works, but it does. And since the bailout value has to be computed only once each iteration, that's not an issue.

But I'm still convinced that these other bailouts based on straight lines can be useful. They're particularly good at sectioning off antennas, for instance. By cutting off the area around the main antenna, it does the same for all the others.

[lkmitch]

There's another bailout condition that may not save you much time, but it brings the iteration bands in closer to the set.  |z| > (1 + sqrt(1 + 4*cabs(#pixel))/2.  This gives |z| > 1 for #pixel = 0, which makes sense, and |z| > 2 for the tip of the spike at #pixel = -2.

[Timeroot]

Actually, lkmitch, that method doesn't help at all.... erm...

[hobold]

A magnification of 10^33 sounds like you were using arbitrary precision numbers, i.e. arithmetic implemented in software. In that case, arithmetic is a lot more costly, and my statements about how cheap |z| is are wrong.

But if you do care for very deep zooms, then I have another optimization for you. It is based on the fact that the Mandelbrot set is connected, and that all level sets are topologically equivalent to concentric circles. First compute the outermost frame of pixels, i.e. the top and bottom rows as well as the leftmost and rightmost columns. Find the minimum iteration count of that frame.

When computing the remaining pixels, you can do that minimum number of iterations blindly, as no point will escape earlier than the points on the border. The cheapest bailout check is no bailout check at all. :-)

This optimization is only an approximation, because the border is sampled only at the pixel centers. But in practice the probability of visible errors is vanishingly small.

[Timeroot]

Yeah, it was with arbitrary precision. I'm just wondering: how many operations does the actual squaring take, compared to the bailout? That is, if you're using standard precision. I'm sorry if I'm a bit a slow here, I'm just curious about these things.

[David Makin]

You could also use a method I was contemplating for IFS fractals, adapted to a standard Mandelbrot as follows:

Render a low resolution image of the Set (say 256 by 192) as a bitwise (or bytewise) array of inside/outside flags at say 100 max iterations, then maybe expand the "inside" by a single pixel at the resolution of the array (just to be sure), finally when rendering the full-detail full-resolution version simply test the appropriate bit/byte in your array of flags for each new z - if bit/byte says outside then bailout.
Obviously this method is less cache-coherent but given the exponential increases in cache sizes over time I think it will become more optimum, if not already so - I admit I haven't tried it.

Edit: Of course I should add the caveat that this will only work provided either the Set is connected or your low resolution array of flags hasn't missed any dust-spots which should be OK if rendered using the escape-time method and the maximium iteration count used for the bitwise array is low enough

[Timeroot]

I don't think that would work (@David), because of course there are many points in the Mset whose orbits go out. Take the point (-2,0): it goes 0 > -2 > 2 > 2 > 2...... and 2 is of course outside the set. The orbits need to never exit the Antibuddhabrot, as I said before. And that takes a long time to calculate, which totally destroys the potential speed ups. It would work for IFS, and the Buddhabrot/Antibuddhabrot basically is an IFS... so yeah, it works there. It also works for Julia sets, since it really functions more like an object undergoing dynamics rather than a control map.

Fractals are hard. :-(

[hobold]

On the lowest level of the machine, there are two fundamental measurements of computing speed. One is throughput, which is a kind of parallel speed measure, and is given by the number of tasks completed per unit time (where task in this case would probably mean a single floating point operation). The other measure is latency, which is a sequential measure, and is given by the time it takes to fully process a single task from beginning to completion.

To illustrate the difference between these two measures, let me quote an old and bad joke (with apologies to the female readers): "One human female can give birth to a baby within a time span of nine months. How long does that take for three females?"

So in this case, latency is nine months. Throughput can be increased by parallelization, but latency cannot be lowered this way.


Okay, back to the topic of floating point arithmetic. Typical desktop machines that you can buy today, as well as most notebooks (with the exception of Atom netbooks), have very solid floating point hardware. They can execute an addition or multiplication with a throughput of one per clock cycle (so more than three billion of these operations for the fastest processors), and with a short latency of four to eight clock cycles. Latency limits the cases where a computation depends on the results of an immediately preceding computation. In such a case, the computer cannot execute the dependent instructions in subsequent clock cycles, but has to wait for the latency time to elapse.


In a typical Mandelbrot loop, the dependencies between the individual additions and subtractions are neither too strong nor too weak. Without special tuning, the machine usually achieves a throughput of less than one floating point operation per clock cycle, but considerably more than one instruction per latency time.

Only addition, subtraction, comparisons and multiplication get this kind of VIP treatment by the processor. Division and square root are roughly ten to twenty times slower in terms of throughput, not as much in terms of latency. Transcendentals and trigonometry are usually slower still.


So much for floating point arithmetic on the CPU. Things are complicated a bit by a special type of parallelism that modern CPUs employ: SIMD, i.e. "Single Instruction, Multiple Data". This is a limited support for vector arithmetic directly in hardware. But most of the time, unless you program specifically for it, the compiler will not be able to make use of these facilities, and so the above guesstimates for performance still apply.


With GPUs the situation is very different. Those use SIMD in much more extreme ways. That's why they have such a huge amount of raw power, but need special programming. And they can only put their brute force to good use when there are few data dependencies. That's because GPUs have an enormous throughput, but fairly long latencies as well. For purposes of rendering fractals, GPUs are not limited by latency. There are always more pixels/voxels/samples to be computed in parallel.


Now, arbitrary precision, on the other hand, is a whole 'nother can of worms. You lose at least a factor of ten by going from hardware to software floating point. And the relative costs of addition and multiplication keep shifting, depending on the precision in bits. Roughly, the cost of addition is proportional to the number of bits, but the cost of multiplication is proportional to the number of bits squared. Division and square root are more expensive still, and for trigonometry or transcendentals, all bets are off (depends very much on the specific algorithms used by the respective library of routines).

[David Makin]

I don't think that would work (@David), because of course there are many points in the Mset whose orbits go out. Take the point (-2,0): it goes 0 > -2 > 2 > 2 > 2...... and 2 is of course outside the set. The orbits need to never exit the Antibuddhabrot, as I said before. And that takes a long time to calculate, which totally destroys the potential speed ups. It would work for IFS, and the Buddhabrot/Antibuddhabrot basically is an IFS... so yeah, it works there. It also works for Julia sets, since it really functions more like an object undergoing dynamics rather than a control map.

Fractals are hard. :-(

Sorry - my bad - I forgot the difference between Mandys and Julias/escape-time IFS

[Timeroot]

Okay, (@hobold) I thiiink I get it. But I'm just writing for UF, and can't really interact with the CPU/GPU at a low level; I don't even know how UF compiles it (how do the conditionals work, for instance?), and I don't know how it interacts with arbitrary precision. All I really want is efficient bailout methods - I'm firmly convinced that if we get the right methods, it will GREATLY outweigh the few bit operations it will take to compare the two values. Could anyone perhaps provide a very high sample Antibuddhabrot? I'm working on one right now, but it's taking a long time, and I'm sure there's another one out there...

[johandebock]

Could anyone perhaps provide a very high sample Antibuddhabrot?

What do you mean?