a-berg/julia_set_kata

Julia sets in various languages (Rust, Haskell, Julia)

Julia Sets

This repository has code to compute Julia sets in various languages.

Computing Julia sets is an good coding kata for various reasons:

• The problem itself is easy to understand for anyone with high-school level math (complex numbers).
• It's purely a number crunching problem, so you'll learn to build that kind of code and make it run fast. This is important if you're interested in scientific computing, data science or machine learning.
• It lends itself to parallelization, which is an increasingly important feature for more and more programs and applications. Through this kata, one can learn both CPU and GPU acceleration libraries.
• From a software design POV, you can easily come up with certain features that, if you implemented your initial solution naively, will be challenging to add. Therefore you'll learn to refactor code and become better at designing numeric applications.
• As a bonus, the images generated make excellent wallpapers!!

The Kata

Part 1: Implement the escape time algorithm

Solve the problem of deciding if a point is part of a Julia set via the escape "time" algorithm:

Given a function of the form $f(z) + c$ (where $z$ and $c$ are complex numbers), you need to compute the sequence:

$$z_{k+1} = f(z_{k}) + c,$$

for a given $c$ and some initial complex number $z_0$.

The sequence should terminate if a maximum number of iterations (to be configured by the programmer, 100 is usually a good default) is reached, or if the modulus of $z$ is larger than some escape radius. For example, for the classic $f(z) = z^2$, the radius is 2: points whose modulus is greater than this radius always diverge (always are in the Julia set).

The implementation should return the "escape time", that is, the value of $k$. Points with infinite escape time (in practice, k == max_k) are part of the dual of the Julia set, the Fatou set (usually colored in black in most representations), whereas the rest are part of the Julia set.

Part 2: Compute a Julia set in a region, and create an image

After you got the initial algorithm, it's time to compute it for an array of complex numbers and plot the results in a beautiful PNG!

For starters, use a low resolution image of e.g. 640x480 pixels. The array of complex numbers should be centered around 0, and be a matrix in which the column index is linearly correlated with the real part, and the row index is linearly correlated with the complex part.

Part 3: Compute the associated Mandelbrot set

A nice extension to the above is to compute the Mandelbrot set. This set is defined as the sequence

$$z_{k+1} = f(z_{k}) + c,$$

where $z_0 = 0$ always, and you will study the escape time with respect of the constant $c$. The numbers of the complex plane that have an "infinite" escape time are part of the Mandelbrot set.

Mandelbrot, Fatou and Julia sets are all generated by the same $f$, so they are "siblings" in that sense.

Part 4: Implement the Distance Estimation Method algorithm

Instead of computing the escape time, there is a way to estimate the distance of any point to the Fatou set. This can lead to a much finer level of detail when generating the image.

This will require to compute the derivative of $f$ with respect to $z$ or $c$ (depending on which set you are computing: Julia or Mandelbrot respectively). You can either ask the user to provide the derivative function or use automatic differentiation libraries.

Extra 1: code parallelization (CPU)

Try to make your code as fast as possible using parallel capabilities of the language. For this part, limit yourself to CPU-only.

Extra 2: code parallelization (GPU)

Same as above, but use GPU libraries.

Extra 3: implement a zooming procedure

Given a zooming "speed" and a center point, make a program that will zoom for a while (or continuously). Output the video or render it in real-time.

Extra 4: anything goes!

Some ideas:

• make an interactive visualizator that let's you vary $c$ for Julia sets, rendering in real time
• same as above but letting you see the associated Julia set for a Mandelbrot point when the user hovers over a pixel
• use quaternions instead of complex numbers (this will render a 3D set)
• use arbitrary Clifford numbers (this may get hard to represent pretty quickly)

Languages used

Julia in itself is a perfect match for this problem (name jokes aside) since it advertises itself as a scientific computing, high performance language.

Rust I'm interested in because of its speed and modern features. It's a language that has been causing "some ruckus" in the FOSS community and I already use many tools written in it, so learning it could help me contribute back to these tools. Also, it has GPU and parallelism libraries like Julia. The code however is not as close to the math it is trying to solve as the other 2.

Haskell, well, I like Haskell. It's usually very elegant and forces helps you to think carefully about how you are going to break the problem into its fundamental parts, so for me it's the ideal prototyping language. Additionally, Haskell can compile to fast programs and its functional nature and ease of parallelization is well suited for this particular problem.

How to use this repo

I'm not going to implement a CLI for it (at least not in the short term). You can clone the repo and go into the src folder, then you can go into your language of choice folder (e.g. rust) and read its README.

The user is responsible for managing the needed runtimes: julia in the case of Julia (I recommend using juliaup, which coincidentally is written in Rust), rustc in the case of Rust and ghc and stack in the case of Haskell.

Other than that, just read the code and open issues if you feel something is not clear enough, you thought of some clever alternative to some of my implementations (discussions are very welcome!), or found a bug.