Compressing Reality

# Mandelbrot Set Efficiency

The traditional algorithm for drawing the Mandelbrot set is to loop over all pixels in a grid and estimate whether each is in the Mandelbrot set by iterating with the famous formula $$z_{n+1} = z_n^2 + x + y \cdot i$$

However, the fact that the Mandelbrot set has a continuous boundary hints at a more efficient method. In particular, it seems like it should be possible to compute the Mandelbrot set using a "painting" method:

function is_in_mandelbrot(pixel) {
var real = 0;
var imaginary = 0;
for (var i = 0; i < 1000; ++i) {
new_real = real * real - imaginary * imaginary + pixel.x;
new_imaginary = 2 * real * imaginary + pixel.y;
real = new_real;
imaginary = new_imaginary;
if (real * real + imaginary * imaginary > 0) return false;
}
return true;
}

var pixels_enqued = Set()
var pixels_to_check = Queue();
not_mandelbrot_set = Set()
while (!pixels_to_check.is_empty()) {
pixel = pixels_to_check.pop();
if (!is_in_mandelbrot(pixel)) {
// not in mandelbrot set
if (pixels_enqued)
if ({"x": pixel.x+1, "y": pixel.y} in pixels_enqued) {
}
if ({"x": pixel.x-1, "y": pixel.y} in pixels_enqued) {
}
if ({"x": pixel.x, "y": pixel.y+1} in pixels_enqued) {
}
if ({"x": pixel.x, "y": pixel.y-1} in pixels_enqued) {
}
}
}

mandelbrot_set = Set();
for (pixel in grid) {
if (!not_mandelbrot_set.contains(pixel))
}