Sunday, 2 February 2014

Stopping at 4?

The Mandelbrot algorthm iterates z2+c many times and stops if either of the following two conditions are true:

  1. We've done lots of iterations and we can't keep going forever. We stop when we reach the maximum upper limit for iterations we've set outselves. 
  2. When the magnitude of the value popping out of the z2+c is greater than 4.
 The first conditions is understandable. What's the reason for the second?

Let's look at what the 4 means. The following diagram shows the regions marked out by this 4. The green circle contains all the points on the complex plane which have magnitude less than 4. Remember that magnitude is just the distance from the origin at (0+0i) to the point where the complex number is sat. The red area represents all the points with magnitude greater than 4.

We've also shown in grey a rough image of the Mandelbrot set. We've cheated and put it where we know others have calculated it to be. The usual box it sits inside has a bottom left at (-2.25-1.5i) and a top right of (0.75+1.5i).

We can see that the grey Mandelbrot set is entirely within the green zone. That means if the values popping out of the repeatedly iterative z2+c function ever stray outside the green zone we know they'll always diverge. Its just the same as if the starting point was outside the green zone - remember that the first value taken by z2+c is c itself, the point being tested.

So wht they value 4 and not 3 or 300? Well we need to balance two competing factors. One one hand we want to be really sure the points do diverge. If we wait until the values popping out of reach a distance of 300 we can be really sure they won't not diverge. But we don't want to waste time doing unnecessary calculations, and on slower computers this can really hurt how quickly we can draw the Mandelbrot set. It used to take hours back in the early 90s!

On the other hand if we choose to bail out when the magnitude is much smaller at 1.5 then, sure, we will have reduced unnecessary calculations but actually we can't be sure any value straying larger than magnitude 1.5 won't in fact ultimately not diverge. In fact we know that there are points outside the circle of radius 1.5 that are part of the Mandelbrot set.

So setting the threshold to 4 is a good balance between not doing too many unnecessary calculations and having high certainty about points which do ultimately diverge.