3
\$\begingroup\$

The purpose of this project is to generate an interactive Mandelbrot set. The user can specify the degree of magnification from the command-line and click on the produced picture to magnify the picture at that point.

Here is a data-type implementation for Complex numbers:

public class Complex
{
    private final double re;
    private final double im;

    public Complex(double re, double im)
    { 
        this.re = re; 
        this.im = im; 
    }
    public double re() 
    { 
        return re; 
    }
    public double im()
    { 
        return im; 
    }
    public double abs()
    { 
        return Math.sqrt(re*re + im*im); 
    }
    public Complex plus(Complex b)
    {
        double real = re + b.re;
        double imag = im + b.im;
        return new Complex(real, imag);
    }
    public Complex times(Complex b)
    {
        double real = re*b.re - im*b.im;
        double imag = re*b.im + im*b.re;
        return new Complex(real, imag);
    }
    public Complex divide(Complex b)
    {
        double real = (re*b.re + im*b.im) / (b.re*b.re + b.im*b.im);
        double imag = (im*b.re - re*b.im) / (b.re*b.re + b.im*b.im);
        return new Complex(real, imag);
    }
    public boolean equals(Complex b)
    {
        if (re == b.re && im == b.im) return true;
        else                          return false;
    }
    public Complex conjugate() 
    {
        return new Complex(re, -1.0*im);
    }
    public String toString()
    {
        return re + " + " + im + "i";
    }
}

Here is my program:

import java.awt.Color;

public class InteractiveMandelbrot {
    private static int checkDegreeOfDivergence(Complex c) {
        Complex nextRecurrence = c;
        
        for (int i = 0; i < 255; i++) {
            if (nextRecurrence.abs() >= 2) return i;
            nextRecurrence = nextRecurrence.times(nextRecurrence).plus(c);
        }
        return 255;
    }
    private static Color[] createRandomColors() {
        Color[] colors = new Color[256];
        double r = Math.random();
        int red = 0, green = 0, blue = 0;
        
        for (int i = 0; i < 256; i++) {
            red = 13*(256-i) % 256;
            green = 7*(256-i) % 256;
            blue = 11*(256-i) % 256;
            colors[i] = new Color(red,green,blue);
        }
        return colors;
    }
    private static void drawMandelbrot(double x, double y, double zoom) {
        StdDraw.enableDoubleBuffering();
        
        Color[] colors = createRandomColors();
        
        int resolution = 1000;
        int low = -resolution / 2;
        int high = resolution / 2;
        double xLowScale = x + zoom*(1.0 * low / resolution);
        double xHighScale = x + zoom*(1.0 * high / resolution);
        double yLowScale = y + zoom*(1.0 * low / resolution);
        double yHighScale = y + zoom*(1.0 * high / resolution);
        StdDraw.setXscale(xLowScale, xHighScale);
        StdDraw.setYscale(yLowScale, yHighScale);

        for (int i = low; i < high; i++) {
            for (int j = low; j < high; j++) {
                double realPart = zoom*(1.0 * i / resolution) + x;
                double imaginaryPart = zoom*(1.0 * j / resolution) + y;
                Complex c = new Complex(realPart,imaginaryPart);
                int degreeOfDivergence = checkDegreeOfDivergence(c);
                Color color = colors[degreeOfDivergence];

                StdDraw.setPenColor(color);
                double radius = 1.0 / (resolution * 2 / zoom);
                StdDraw.filledSquare(realPart, imaginaryPart, radius);
            }
        }
        StdDraw.show();
    }
    public static void main(String[] args) {
        double x = Double.parseDouble(args[0]);
        double y = Double.parseDouble(args[1]);
        int magnifier = Integer.parseInt(args[2]);
        double zoom = 1;

        drawMandelbrot(x, y, zoom);

        while (true) {
            if (StdDraw.isMousePressed()) {
                x = StdDraw.mouseX();
                y = StdDraw.mouseY();
                zoom = zoom/magnifier;

                drawMandelbrot(x, y, zoom);
            }
        }
    }
}

StdDraw is a simple API written by the authors of the book Computer Science An Interdisciplinary Approach. I checked my program and it works. Here is one instance of it.

Input: 0.5 0.5 10

Output (actually a succession of outputs):

enter image description here

enter image description here

enter image description here

enter image description here

I used paint to show where I clicked.

From my own previous posts, I already know how to improve Complex. In this post, I am solely interested in the improvement of InteractiveMandelbrot. Is there any way that I can improve my program?

Thanks for your attention.

\$\endgroup\$
3
\$\begingroup\$

Performance: the Complex class

You've mentioned that you already know how to improve it, but the single biggest performance improvement to this program is removing the Complex class. Perhaps it's sad to say goodbye to that class, but run some performance tests and decide.

On my PC, at the point/zoom 0.5, 0.5, 10, the original code runs in 100 - 110 ms per frame. Excluding drawing time, I removed that and just save the colors to an array. Excluding the first run, which is slower as is usual with Java.

If I write the complex arithmetic inline, without fundamentally changing it, like this:

private static int checkDegreeOfDivergence(double r, double i) {
    double a = r, b = i;
    
    for (int j = 0; j < 255; j++) {
        if (Math.sqrt(a * a + b * b) >= 2) return j;
        
        double nextA = a * a - b * b + r;
        double nextB = a * b + b * a + i;
        a = nextA;
        b = nextB;
    }
    return 255;
}

Now it runs in 30 - 40ms per frame. Around 3 times as fast, just by simple refactoring.

The logic can be slightly optimized, but the improvement from this is much less significant.

private static int checkDegreeOfDivergence(double r, double i) {
    double a = r, b = i;
    
    for (int j = 0; j < 255; j++) {
        if ((a * a + b * b) >= 4) return j;
        
        double nextA = a * a - b * b + r;
        double nextB = a * b * 2 + i;
        a = nextA;
        b = nextB;
    }
    return 255;
}
\$\endgroup\$
1
  • \$\begingroup\$ Just wow! It's a great perspective. Thank you very much. \$\endgroup\$ – Khashayar Baghizadeh Oct 3 '20 at 22:05
3
\$\begingroup\$

Comment 1

You are not using the r variable in createRandomColors , so there is nothing random in it.

Comment 2

if (nextRecurrence.abs() >= 2) return i;

You should use brackets after if, don't try to be smart by writing one-liners like this. It will bite you one day when you misread it or edit it without noticing.

Comment 3

for (int i = low; i < high; i++) {
    for (int j = low; j < high; j++) {
        double realPart = zoom*(1.0 * i / resolution)

The calculation zoom * 1.0 / resolution is calculated 3 times in this double for loop, that's for every pixel on screen I think. It might be worth optimizing your calculations by taking out this factor and calculating it just once.

Since it doesn't depend on i or j, you could take this calculation out of the loop entirely and so you would calculate it once per screen instead of 3*millions times.

Likewise, the realPart does not depend on j, so calculate it outside of the j loop to save yourself 999/1000 (approximately) calculations for realPart.

double realPart = zoom*(1.0 * i / resolution) + x;

\$\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.