~/blog on main cat making-the-mandelbrot.md

I have something of a strange relationship with the Mandelbrot set. When I was first learning Python, I used my rudimentary understanding of complex numbers and some simple image manipulation library to generate a picture of the set. It wasn’t a particularly good, or even all that interesting, bit of code, but what it did represent to me was something of a benchmark. To me, a program to generate an image of the Mandelbrot set is something of a “Hello, World”, and a way of seeing how my approach to programming changes with time and as my skills evolve.

I’ve recently been learning the Rust programming language, and I’ve found it to be both a very fun language to write and a way to explore some ideas in functional programming. I started my journey with Rust by reading “The Rust Programming Language”, a tome of Rust known to Rust programmers simply as “The Book”, and creating some programs here and there, none of which were really any good. At some point, I decided to take a crack at making a picture of the Mandelbrot set, and I wound up falling into a relatively shallow, but quite interesting, rabbit hole of functional programming.

Before I talk about that though, exactly what is the Mandelbrot set? The answer to that turns out to be deceptively simple. Let us consider the function fc(z)=z2+cf_c(z)=z^2+c. The Mandelbrot set is simply the set M\mathcal{M} of cCc\in\mathbb{C} for which fc(z)f_c(z) does not diverge when iterated from z=0z=0. Great, and a monad is a monoid on the category of endofunctors. To be a bit more descriptive, let’s consider a single complex number cc. We can then iteratively apply fcf_c to 00, and we obtain a seqence of complex numbers fc(0),fc(fc(0)),fc(fc(fc(0))),f_c(0), f_c(f_c(0)), f_c(f_c(f_c(0))), \cdots. If, as we apply fcf_c an infinite number of times, the value stays bounded below some finite value, cc is in the Mandelbrot set. Now, the astute reader may notice a very significant issue here: how do we know that a given value will certainly blow up to infinity? We could apply fcf_c to 00 a huge number of times and obtain a very large number, but how do we know that that large number doesn’t still stay bounded under some finite number? This seems like a very significant problem, but fortunately fcf_c has a very nice property that saves us. We can demonstrate that if the absolute value of zz, z=zzˉ\|z\|=\sqrt{z\bar{z}} is greater than 22, it will certainly go on to grow without bound under repeated application of fcf_c. This means that if we apply fcf_c to 00 some large number of times, and the absolute value of the output is less than 22, we guess that cc is probably in the Mandelbrot set, with this confidence approching 100% as we increase the number of applications of fcf_c.

With the mathematical formalism out of the way, let’s take a look at how you might create a function to determine whether or not some complex number cc is in the Mandelbrot set. The easiest way to do this, and the way I intuitively implemented, was an imperative approach, which looked something like

fn in_mandelbrot(c: Complex<f64>, max_iter: usize) -> bool {
    let mut z = Complex::new(0.0, 0.0);
    for _ in 0..max_iter {
        if z.norm() > 2 {
	    return false;
	} else {
	    z = z.powu(2) + c;
	}
    }
    true
}

This may not be completely clear to you if you’re not a Rust programmer, but the gist of it is pretty simple. First, start with z=0z=0, then loop some set number of times, every time checking if zz is greater than 22, and returning false if it is. If it isn’t, we apply fcf_c once, then loop. If we get to the end of the loop without returning false, it must be that we didn’t cross the threshold, so we return true.

Now, to be completely clear, this works. This is good, semantic, clean code, and this is pretty well the way that everyone who writes this sort of thing checks if a number is in the Mandelbrot set. That being said, something about this always irked me. The issue that I had with this imperative approach was that I felt like the Mandelbrot set had this sort of elegant recursive series at its heart that was lost when translating it into purely imperative code. This immediately made me think of iterators, a major feature in Rust and in functional programming in general. My immediate instinct was that I should be able to create some iterator that always returns fcf_c of its previous element. That would be an elegant solution that would respect the recursive, sequential nature of the definition of the set. The first thing to do was to define some struct that would act as my iterator, which would have to take some form like

struct MandelbrotIterator {
    z: Complex<f64>,
    c: Complex<f64>
}

This effectively encapsulated what I needed for this iterator: a way of keeping track of the current value of zz while computing the subsequent one, and the value cc that we need to define fcf_c. It was then easy to quickly implement a method to create a new instance of this struct which could be used to compute whether or not a point was in the Mandelbrot set, which looked like

impl MandelbrotIterator {
    fn new(c: Complex<f64>) -> Self {
        MandelbrotIterator {
	    z: Complex::new(0.0, 0.0),
	    c
	}
    }
}

With this simple definition out of the way, all I had to do was implement Rust’s Iterator trait, and I’d have a full-fledged, honest-to-goodness Mandelbrot set iterator on my hands. This was similarly not too difficult, and was a simple matter of

impl Iterator for MandelbrotIterator {
    type Item = Complex<f64>;

    fn next(&mut self) -> Option<Complex<f64>> {
    	let item = self.z;
	self.z = self.z.powu(2) + self.c;
	Some(item)
    }
}

This gives our function for determining whether or not is in the Mandelbrot set a new, and I think much more mathematically elegant, form:

fn in_mandelbrot(c: Complex<f64>, max_iter: usize) -> bool {
    !MandelbrotIterator::new(c)
        .take(max_iter)
	.any(|z| z.norm() > 2.0)
}

I personally think that this is a very clean, elegant expression of the idea behind the Mandelbrot set in programmatic form: given this specific sequence defined by cc, look at some number of the elements of the sequence, depending on how precise you want to be, and if any of those elements have a magnitude greater than 22, cc is not in the Mandelbrot set.

While it’s not strictly relevant to the ideas at play here, it turns out that this idea of an iterator whose elements are computed based on their preceding element is so common that there is a provision for it in the standard library, which you can read up about here.

Now, my goal in writing this certainly isn’t to suggest that this is how people should be writing these sorts of things, or that functional programming is the One True Way™, but rather to encourage people to look for opportunities for elegance in the code they write. Not only is it rewarding and fun, but you just might wind up learning something new!

Thanks for reading my little spiel about math and programming! If you’re interested in the code that I discussed here, you can find the whole Mandelbrot-generating CLI that I wound up writing in this GitHub repo. If you’d like to see a video that I made using the images produced by the CLI, check out this YouTube video. Finally, if you’d like to see an unreasonably large picture of the Mandelbrot set (65536 x 65536 pixels) generated with the CLI, check it out here (warning: may crash web browsers).