Lab 03: Visualizing the Mandelbrot Set
using vector operations to perform Mandelbrot calculations quickly
DUE: Friday, March 24, Monday, March 27, 11:59 pm
Background
The Mandelbrot set
The Mandelbrot set is among the most widely depicted mathematical objects. In order to define the Mandelbrot set (and understand how to draw it), we need to start with the complex numbers and the complex plane.
Complex numbers
Complex numbers are numbers of the form \(a + b i\) where \(a\) and \(b\) are real numbers, and \(i\) is the imaginary number satisfying \(i^2 = 1\). Complex numbers can be added and multiplied:
 \[(a + b i) + (c + d i) = (a + c) + (b + d)i\]
 \[(a + b i) (c + d i) = (a c  b d) + (a d + b c) i\]
Further, complex numbers have a modulus defined by
 \[ a + b i  = \sqrt{a^2 + b^2}\]
The complex plane consists of the set of all complex numbers represented as points in a plane: each \(a + b i\) corresponds to the point \((a, b)\) in the plane.
Mandelbrot definition
Given a complex number \(c = a + b i\), consider the sequence of complex numbers \(z_1, z_2, \ldots\) defined by the following recursive formula:
 \[z_1 = c\]
 for \(n > 1\), \(z_n = z_{n1}^2 + c\).
For each starting point \(c\), one of two things can happen:
 the sequence \(z_1, z_2, \ldots\) remains bounded—i.e., there is a positive (real) number \(M\) such that \(\mid z_n \mid \leq M\)
 the sequence \(z_1, z_2, \ldots\) is unbounded—\(\mid z_1 \mid , \mid z_2 \mid , \ldots\) grows without bound.
The Mandelbrot set is defined to be the set of complex numbers \(c\) for which the sequence \(z_1, z_2, \ldots\) remains bounded. For example, \(c = 1\) is not in the Mandelbrot set because its corresponding sequence is \(1, 2, 5, 26, \ldots\) which grows without bound. On the other hand, \(c = 1\) is in the Mandelbrot set because its corresponding sequence is \(1, 0, 1, 0, \ldots\) which remains bounded.
Computing the Mandelbrot set
In general, it might be difficult to determine if a given sequence \(z_1, z_2,\ldots\) remains bounded analytically. To visualize the Mandelbrot set it is enough to determine if the sequence is bounded empirically. Specifically, we can choose two parameters: a modulus bound \(M\) and an iteration bound \(N\). We then proceed as follows. Starting from a complex number \(c\), compute \(z_1, z_2, \ldots\) as required. For each \(z_n\), compute \(\mid z_n\mid\) and do the following:
 if \(\mid z_n\mid \geq M\), stop and report that \(c\) is not in the Mandelbrot set,
 if \(n = N\), stop and report that \(c\) is in the Mandelbrot set
 otherwise, continue.
Following this procedure, we can obtain this following image of the Mandelbrot set.
The image above depicts the region of the complex plane with real part (\(x\)coordinates) between \(2\) and \(1\), and imaginary part (\(y\)coordinates) between \(1.5\) and \(1.5\). The image is 1024 by 1024 pixels, where each pixel represents an point in the complex plane. Each pixel is colored black if it is (empirically) in the Mandelbrot set, and white otherwise. For points \(c\) not in the Mandelbrot set (i.e., for which case 1 above occurs), the first iteration \(n\) at which \(\mid z_n \mid \geq M\) is called the escape time. In order to generate a color image such as the image below, the color is determined by the escape time.
Specifically, the color of a point \(c\) is determined by a color map applied to the escape time for the point. In the image above, brighter colors indicate shorter escape times. You can read about different methods for coloring the Mandelbrot set at the following link:
Vector Operations in Java
For given parameters \(M\) and \(N\) as above, determining the escape time of a single complex value \(c\) is straightforward. Thus, images as above can be computed by simply iterating over all pixels sequentially and computing the escape time of the point corresponding to each pixel. For the \(1024 \times 1024\) pixel images above, this requires about a million individual escape time computation, and each escape time requires up to \(N\) iterations to compute. The calculations for coloring different pixels, however, and independent of one another. Thus we may be able to employ parallelism to compute escape times faster. In this lab, we will explore how vector operations can speed up escape time calculations by performing arithmetic operations for multiple points in parallel.
Vector operations are single instruction, multiple data (SIMD) operations. This means that they perform the same elementary operation on multiple primitive values in parallel. In newer versions of Java (16+), SIMD instructions are supported via the Vector
package. The Vector
package provides support for SIMD operations on primitive datatypes. Here are links to the relevant documentation:
Program description
For your assignment, you will write a program that uses vector operations to compute escape times for Mandelbrot set operations. To get started, download the following archive:
The program includes four files, Mandelbrot.java
, MandelbrotTester.java
, MandelbrotViewer.java
, and runtest.sh
.

Mandelbrot.java
defines a class that stores parameters to describe a region in the complex plane, as well as methods for computing escape times for points in that region. It defines a baseline method,escapeTimesBaseline
as well as a(in incomplete)escapeTimesOptimized
method. Your task is to complete theescapeTimesOptimized
method. 
MandelbrotTester.java
defines methods for testing yourescapeTimesOptimized
method. The methodcorrectnessTest
verifies that your optimized and the baseline implementation provide the same escape times, while two performance test methods compare the running times of baseline and optimized implementations. 
MandelbrotViewer.java
draws the Mandelbrot set in a specified region using the escape time calculations fromMandelbrot.java
. This file is not required for the assignment, but is included so that you view the output of your program and experiment with finding interesting regions of the Mandelbrot set. 
runtest.sh
is a shell script for running your program on the HPC cluster. Once your completed files are on the cluster, you can run the tests usingsbatch runtest.sh
. When the tests complete (typically in about five minutes), the program will write a filemandelbrotTest.txt
that includes the results of the test.
Your task is to complete the method escapeTimesOptimized
in Mandelbrot.java
. You should only complete this method. You should not modify any other methods in Mandelbrot.java
or anthing in MandelbrotTester.java
. Your implementation of escapeTimesOptimized
should be a singlethreaded method that employs Vector
operations to perform the escape time operations more quickly than the escapeTimesBaseline
method (provided in Mandelbrot.java
).
What to turn in
To complete the assignment, turn in only your completed Mandelbrot.java
file.
Grading
Your programs will be graded on a 10 point scale according to the following criteria:

Correctness (3 pts). Your program compiles and completes the task as specified in the program description above. The program passes the correctness test in
MandelbrotTester.java
.  Style and Vectors (3 pt).
 Coding style: code is reasonably wellorganized and readable (to a human). Variables, methods, and classes have sensible, descriptive names. Code is wellcommented.
 The program correctly applies
Vector
operations in order to perform the operations inescapeTimesOptimized
. No multithreading or other performance enhancements should be used.
 Performance (4 pts).
 2 pts. The optimized method is faster than the baseline for at least 3 of the 5 performance tests.
 3 pts. Additionally, the optimized method is at least 2 times faster than baseline for one of the tests.
 4 pts. The optimized method is at least 3 times faster than the baseline for one of the tests.
Extensions
There are a lot of directions you can go with this assignment! Here are a few:
 Make a color map that makes things look much better than mine, and use it to make some nice images. (You can submit image files if you’d like.)
 Modify the
MandelbrotViewer
to do an infinite zoom into an interesting portion of Mandelbrot set. If you do this, have the program print the framerate to the console.  Draw other fractals! The Mandelbrot set is but one fractal in a large family of fractals produced using similar methods. For example, you could draw Newton fractals or other Julia sets.