10
$\begingroup$

I'm writing JavaScript code to plot the Mandelbrot set on an HTML5 Canvas element. (That's probably not relevant to the answer to this question).

A core part of the problem is to write a simple function that returns true if a number is a member of the Mandelbrot set and false otherwise. Since JavaScript has no complex numbers in its built-in libraries, I simply represent a complex number as a two-element array with the first element being the real part and the second element being the imaginary part.

I know that if any iteration of the function z^2 + c returns a value with absolute value greater than two, then z is definitely not a member of the Mandelbrot set. If no iteration of z^2 + c returns a value greater than two, then z is a member of the Mandelbrot set, but it's impossible to iterate the function to infinity.

Therefore, I tried iterating the function 1000 times and assuming that if it takes more than 1000 iterations, the function doesn't diverge to infinity. This is a disaster. The plot produced contains many points that are definitely not in the Mandelbrot set by comparison to references on the internet.bad Mandelbrot plot

        function isInMandelbrot(z) {
            var i, a;
            a = z;
            for (i = 0; i < 1000; i++) {
                a = helper(a);                    
                if (a[0] > 2 || a[0] < -2 || a[1] > 2 || a[1] < -2)
                    return false;
            }
            return true;

            // Compute z^2 + c
            function helper(a) {
                var raisedToPower, sum;
                raisedToPower = square(a);
                sum = [raisedToPower[0] + z[0], raisedToPower[1] + z[1]];
                return sum;
            }
        }

        function square(z) {
            var rResult, iResult;
            rResult = z[0] * z[0] - z[1] * z[1];
            iResult = 2 * z[0] * z[1];
            return [rResult, iResult];
        }

Increasing the limit to 10,000 instead of 1000 produces almost exactly the same plot and takes lots longer. This makes me wonder if I could be running up against the precision limits of how JavaScript computes calculations. There's an explanation here: http://www.yuiblog.com/blog/2009/03/10/when-you-cant-count-on-your-numbers/

I think that in order to plot the Mandelbrot set, I need a better way of determining set membership. How might I do this?

The answer should not depend on what language the computation is done in unless floating-point precision is the issue.

Edit: I tried rendering the image at 16000*16000 and I noticed a fascinating result: The points outside the Mandelbrot set that are wrongly identified as points inside the Mandelbrot set... clump together into clumps shaped like the Mandelbrot set! You can't make this stuff up!

Edit again: Okay, I think I see what the problem is! I think that the darkened points are actually in the Mandelbrot set. I erroneously assumed that they were too far from the main "blob" to be part of the set, but after looking at some other plots, I think that there is a connection that is too small to render, as in this plot: http://en.wikipedia.org/wiki/File:Mandel_zoom_01_head_and_shoulder.jpg

$\endgroup$
5
  • $\begingroup$ Your absolute value code could be modified to $x^2+y^2\ge 8$ to achieve the same effect as the $x\gt 2$ etc. tests... $\endgroup$
    – abiessu
    Nov 9 '13 at 16:42
  • 1
    $\begingroup$ In general, I think there is no quick and easy way to determine when a point is in the Mandelbrot set or not, although it there are results which say things like the points inside the main cardioid shape (and the major "bulbs" round it) are all definitely inside, so you do not need to do any calculations in that region. Beyond that, I am pretty sure that your main problem is going to be with accumulating truncation errors. From past experience (mostly fairly old experience), programs to plot M do get pretty slow when the number of iterations increases - sorry. $\endgroup$
    – Old John
    Nov 9 '13 at 17:07
  • 1
    $\begingroup$ "This is a disaster. The plot produced contains many points that are definitely not in the Mandelbrot set by comparison to references on the internet." The plot looks pretty reasonable to me.... $\endgroup$
    – Sheldon L
    Nov 9 '13 at 20:55
  • $\begingroup$ Daniel wrote: "Edit again: Okay, I think I see what the problem is!" Hillarious! Mini-Mandelbrots strike again! Yes, the little block blocks that aren't visibly connected to the main Cardioid are in fact connected by filagrees, and they are little copies of the bigger main Mandelbrot. You are doing everything correctly. $\endgroup$
    – Sheldon L
    Nov 10 '13 at 1:37
  • $\begingroup$ I believe the Mandelbrot set is connected as a subset of $\mathbb{C}$ with the usual topology, but I am not sure that is going to help you much with a computer plot where you are restricted to individual pixels being marked as either "in" or "out". Some of the filaments doing the connecting are extremely thin! $\endgroup$
    – Old John
    Nov 16 '13 at 20:53
4
$\begingroup$

Your plot looks great. I don't know any better way than what you are doing. As you zoom in deeper, it takes more and more iterations to get a reasonable picture. To some extent, you can use fixed point instead of floating-define maxint as $4$ and do fixed point multiplies and bit shifts to rescale, then add. You can also do your compares to $2$ in each direction instead of squaring. If the value is greater than $2$ in magnitude, it will be greater than $2$ in one axis soon.

$\endgroup$
2
  • $\begingroup$ can you expand a little bit about how you're thinking of using bit-shifts? $\endgroup$ Nov 9 '13 at 23:43
  • $\begingroup$ Say you define $2^{30}$ as the coordinate $1.0$. Now you get $29$ bits of fraction in a $32$ bit word instead of only $23$ in a single float. Then to do the calculation you have $z$ in two ints. To do $z^2$ you multiply into 64 bit registers (which is fixed point), but if you multiplied $1.0 \cdot 1.0$ it would be represented as $2^{30} \cdot 2^{30}=2^{60}$ so you need to rescale by right shifting $30$ bits to get back to your representation. Then you can add $c$ and have your iteration done using only fixed point operations and more accuracy. $\endgroup$ Nov 10 '13 at 0:29
2
$\begingroup$

I think that in order to plot the Mandelbrot set, I need a better way of determining set membership. How might I do this ?

  1. You can use different version of algorithm. Now you use boolean version of escape time algorithm. If you change to integer or real version and use grey colour gradient then even with the same number of iterations, precision of numbers and zoom the filaments will be better visualised. enter image description here
  2. you can also use different algorithm like DEM/Menter image description here

If you change the algorithm, also change the bailout test.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.