Chaos with Newton’s method

Question

The following is the program 3.2.6. from the book Computer Science An Interdisciplinary Approach by Sedgewick & Wayne:

// This data type is the basis for writing Java programs that manipulate complex numbers.    
public class Complex
{
    private final double re;
    private final double im;

    public Complex(double real, double imag)
    { re = real; im = imag; }
    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 String toString()
    {
        return re + " + " + im + "i";
    }
    public static void main(String[] args)
    {
        Complex z0 = new Complex(1.0, 1.0);
        Complex z = z0;
        z = z.times(z).plus(z0);
        z = z.times(z).plus(z0);
        System.out.println(z);
    }
}

I also added the following method to it:

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);
}

The following is the exercise 3.2.34. from the book Computer Science An Interdisciplinary Approach by Sedgewick & Wayne:

The polynomial f(z) = z^4 - 1 has four roots: at 1, -1, i, and -i. We can find the roots using Newton’s method in the complex plane: z_{k+1} = z_k - f(z_k) / f'(z_k). Here, f(z) = z^4 - 1 and f'(z) = 4z^3. The method converges to one of the four roots, depending on the starting point z_0. Write a program that takes a command-line argument n and creates an n-by-n picture. Color each pixel white, red, green, or blue according to which of the four roots the corresponding complex number converges (black if no convergence after 100 iterations).

Here is my program:

import java.awt.Color;

public class NewtonianChaos 
{
    private static Complex polynomial(Complex complexNumber)
    {
        Complex minusOne = new Complex(-1.0 ,0.0);
        return complexNumber.times(complexNumber).times(complexNumber).times(complexNumber).plus(minusOne);
    }
    private static Complex polynomialDerivative(Complex complexNumber)
    {
        Complex four = new Complex(4.0, 0.0);
        return complexNumber.times(complexNumber).times(complexNumber).times(four);
    }
    private static Complex applyNewtonMethod(Complex complexNumber, int iterations)
    {
        Complex minusOne = new Complex(-1.0 ,0.0);
        Complex complexRoot = complexNumber;
        for (int i = 0; i < iterations; i++)
        {
            complexRoot = complexRoot.plus((polynomial(complexRoot).divide(polynomialDerivative(complexRoot))).times(minusOne));
        }
        return complexRoot;
    }
    private static Color pickColor(Complex complexNumber)
    {
        if      (complexNumber.re() == 1.0  && complexNumber.im() == 0) return new Color(255, 0, 0);
        else if (complexNumber.re() == -1.0 && complexNumber.im() == 0) return new Color(0, 255, 0);
        else if (complexNumber.im() == 1.0  && complexNumber.re() == 0) return new Color(0, 0, 255);
        else if (complexNumber.im() == -1.0 && complexNumber.re() == 0) return new Color(255, 255, 255);
        else                                                            return new Color(0, 0, 0);
    }
    private static Picture paint(Picture picture, int iterations)
    {
        int width = picture.width();
        int height = picture.height();
        for (int j = 0; j < width; j++)
        {
            for (int i = 0; i < height; i++)
            {
                double realPart = 1.0 * j / width;
                double imaginaryPart = 1.0 * i / height;
                Complex complexNumber = new Complex(realPart, imaginaryPart);
                Complex complexRoot = applyNewtonMethod(complexNumber, iterations);
                Color color = pickColor(complexRoot);
                picture.set(j, i, color);
            }
        }
        return picture;
    }
    public static void main(String[] args)
    {
        int side = Integer.parseInt(args[0]);
        int iterations = Integer.parseInt(args[1]);
        Picture picture = new Picture(side, side);
        paint(picture, iterations);
        picture.show();
    }
}

Picture is a simple API written by the authors of the book. I checked my program and it works. Here is one instance of it:

Input: 7000 100

Output:

Is there any way that I can improve my program?

Thanks for your attention.

Answer 1

Formatting

Run your code through a style checker / formatter to make it more readable and follow a standardized code style. For example this one

https://codebeautify.org/javaviewer

Don't repeat yourself 1

Complex minusOne = new Complex(-1.0 ,0.0);

You are defining this in more than one place. This should be a final member at the beginning of your class.

Don't repeat yourself 2

return new Color(255, 0, 0);

Instead of creating a new color over and over, which might consume a lot of memory and cpu, the colors should also be defined as constants in the beginning of the class, and named accordingly, for example RED is a good name. It is quite possible that the color library/tools you use already has such ready-to-use predefined colors, if that's the case then use those.

Naming / Clarity

polynomial

Why is the function named polynomial that returns c^4 - 1 ? Polynomial could mean any polynomial, so you should rather give the function a more specific name, or make a more general polynomial function that takes in some parameters and creates a polynomial accordingly.

(Within the context of your assignment, this is not very important though, since it won't be mistaken).

Code structure

private static Color pickColor(Complex complexNumber)
    {
        if      (complexNumber.re() == 1.0  && complexNumber.im() == 0) return new Color(255, 0, 0);
        else if (complexNumber.re() == -1.0 && complexNumber.im() == 0) return new Color(0, 255, 0);
        else if (complexNumber.im() == 1.0  && complexNumber.re() == 0) return new Color(0, 0, 255);
        else if (complexNumber.im() == -1.0 && complexNumber.re() == 0) return new Color(255, 255, 255);
        else                                                            return new Color(0, 0, 0);
    }

This is not a nice piece of code. In addition to using color constants as mentioned above, it would be natural to have an equals method for your Complex class. Add one if there isn't one already.

Then you can use that to compare like so:

if complexnumber.equals(Complex(1.0, 0.0)) return RED;
if complexnumber.equals(Complex(-1.0, 0.0)) return GREEN;

and so on.

The Complex(1.0, 0.0) should also be constants by the way, since we are re-using them a lot. So create some constants like final Complex ONE = new Complex(1.0, 0.0) and use that in the equals comparison.

Since you're returning in each if, you also don't need the else, just remove them.

Answer 2

I have some suggestions for your code.

As @user985366 also stated in his/her answer, the biggest issue in your code, in my opinion, is the code duplication.

For the colors, the java.awt.Color class offer lots of base color already computed and exposed as constants; you can see the in the documentation / class.

NewtonianChaos#pickColor method

You can extract some of the methods call into variables, since they are uses in most of the checks.

Before

if      (complexNumber.re() == 1.0  && complexNumber.im() == 0) return new Color(255, 0, 0);
else if (complexNumber.re() == -1.0 && complexNumber.im() == 0) return new Color(0, 255, 0);
else if (complexNumber.im() == 1.0  && complexNumber.re() == 0) return new Color(0, 0, 255);
else if (complexNumber.im() == -1.0 && complexNumber.re() == 0) return new Color(255, 255, 255);
else                                                            return new Color(0, 0, 0);

After

double re = complexNumber.re();
double im = complexNumber.im();

if (re == 1.0 && im == 0) return Color.RED;
else if (re == -1.0 && im == 0) return Color.GREEN;
else if (im == 1.0 && re == 0) return Color.BLUE;
else if (im == -1.0 && re == 0) return Color.WHITE;
else return Color.BLACK;

This will make the function look cleaner and make the code easier to read.

Complex#divide method

Again, you can extract into variables.

Before

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);

After

double v = b.re * b.re + b.im * b.im;
double real = (re * b.re + im * b.im) / v;
double imag = (im * b.re - re * b.im) / v;
return new Complex(real, imag);

Also, in this method, you should check if the value is != 0, when dividing, just to be sure.

double v = b.re * b.re + b.im * b.im;

if(v == 0d) {
    //[...] return a value or throw an 
}

double real = (re * b.re + im * b.im) / v;
double imag = (im * b.re - re * b.im) / v;
return new Complex(real, imag);

Answer 3

I hope you don't mind that I mostly copy&pasted my last answer to one of your questions, but basically, the points are mostly still the same.

Whitespace

There should be a blank line between two method definitions.

Also, some blank lines inside of the methods would give the code room to breathe, and allow you to visually separate individual "steps" from each other, for example in your main method:

int side = Integer.parseInt(args[0]);
int iterations = Integer.parseInt(args[1]);
Picture picture = new Picture(side, side);

paint(picture, iterations);
picture.show();

Formatting

The Java community has a fairly standard formatting style. In the early years of Java, Sun used to publish a standardized coding style. They stopped at some point, because they felt that it wasn't the job of the language creator to tell people how to write their code, but most of the community still sticks to those rules.

Another popular style guide is the Google Java Style Guide, which builds on Sun's, but deviates in a couple of places, e.g. Sun's style guide specified an indentation of 4 columns to be achieved either with spaces or tabs, Google specifies 2 spaces.

Most of these style guides would suggest to leave whitespace between method definitions. Also, almost all Java style guides use some form of Egyptian Braces where the opening brace is on the same line as the declaration or keyword that starts the compound statement.

Seeing something like

private static Complex polynomial(Complex complexNumber)
{
    Complex minusOne = new Complex(-1.0 ,0.0);
    return complexNumber.times(complexNumber).times(complexNumber).times(complexNumber).plus(minusOne);
}

will look weird to a Java programmer. They would expect to see either

private static Complex polynomial(Complex complexNumber) {
    Complex minusOne = new Complex(-1.0 ,0.0);
    return complexNumber.times(complexNumber).times(complexNumber).times(complexNumber).plus(minusOne);
}

or

private static Complex polynomial(Complex complexNumber) {
  Complex minusOne = new Complex(-1.0 ,0.0);
  return complexNumber.times(complexNumber).times(complexNumber).times(complexNumber).plus(minusOne);
}

And something like this:

public Complex(double real, double imag)
{ re = real; im = imag; }
public double re() 
{ return re; }
public double im()
{ return im; }
public double abs()
{ return Math.sqrt(re*re + im*im); }

is completely non-standard and non-idiomatic. It doesn't even match with the rest of your code. It should at least look like this to be consistent with the rest of your code:

public Complex(double real, double imag)
{
    re = real;
    im = imag;
}

public double re() 
{
    return re;
}

public double im()
{
    return im;
}

public double abs()
{
    return Math.sqrt(re*re + im*im);
}

but most Java style guides would prefer this:

public Complex(double real, double imag) {
    re = real;
    im = imag;
}

public double re() {
    return re;
}

public double im() {
    return im;
}

public double abs() {
    return Math.sqrt(re*re + im*im);
}

Personally, I would also be fine with this:

public Complex(double real, double imag) {
    re = real;
    im = imag;
}

public double re() { return re; }

public double im() { return im; }

public double abs() { return Math.sqrt(re*re + im*im); }

And even this:

public Complex(double real, double imag) {
    re = real;
    im = imag;
}

public double re() { return re; }
public double im() { return im; }
public double abs() { return Math.sqrt(re*re + im*im); }

Personally, what I do is I set my editor to "auto-format while type", "auto-format on paste", and "auto-format on save", and then I can just turn off my brain and never need to think about formatting ever again.

Magic values

There are some magic values in your code, for example (255, 0, 0) or (255, 255, 255).

Variables allow you to give explanatory, intention-revealing names to your values.

final var red = new Color(255, 0, 0);

However, note that as mentioned in Doi9t's answer, there is no need to define those yourself, all of the colors you are using are already predefined in Java SE.

Type inference

I am a big fan of type inference, especially in cases where the type is obvious:

int side = Integer.parseInt(args[0]);

How often do I have to told that this is an integer? I get it!

var side = Integer.parseInt(args[0]);

Same here:

Picture picture = new Picture(side, side);

This almost sounds like someone stuttering. I don't need the picture variable to be explicitly annotated with the Picture type to understand that a variable called picture being initialized with a Picture is probably a picture:

var picture = new Picture(side, side);

final

I am also a big fan of making everything that can be made final explicitly final. And even for things that can't be made final as written, I'd investigate whether it can be rewritten so it can be made final.

Note, by "everything" I mean primarily variables and fields. However, unless a class is explicitly designed to be extended, it should also be marked final. And of course, immutable classes need to be final anyway.

Naming

complexNumber is not a very intention-revealing name. I already know it is a complex number from its type, but what does it do? What is its meaning?

Also note that Java SE does contain a couple of numeric classes such as BigInteger and BigDecimal, and they use the terms add and multiply instead of plus and times, so it would probably be a good idea to follow them.

polynomial was already mentioned in another answer.

Code Duplication

There are two identical definitions of minusOne. Also, the number -1 is used a third time in the paint method, but in a hidden way.

You can pull these out into private static final fields in your class. But really, if you compare the Complex class to other numeric classes in the Java SE standard library, e.g. java.math.BigInteger or java.math.BigDecimal, or third-party classes from the larger Java community, e.g. Apache Commons Math's apache.commons.math4.fraction.Fraction and JScience's org.jscience.mathematics.number.Rational, and especially other complex number implementations such as apache.commons.math4.complex.Complex or org.jscience.mathematics.number.Complex, you will see that they expose important and often needed numbers as static fields on the class itself.

Correctness

Your Complex class is missing an implementation of equals. As a result, it inherits the default implementation of equals which checks for reference equality, which means that e.g. the following will be false:

var two     = new Complex(2d, 0d);
var alsoTwo = new Complex(2d, 0d);

System.out.println(two.equals(alsoTwo));
System.out.println(two.equals(Complex.ONE.add(Complex.ONE)));

You should pretty much always override equals (and hashCode), at least in all your data classes and model classes. For Complex, it should be something like this:

@Override
public boolean equals(final Object other) {
    if (other == null) {
        return false;
    }

    if (this == other) {
        return true;
    }

    if (other instanceof Complex) {
        var otherComplex = (Complex) other;
        return re() == otherComplex.re() && im() == otherComplex.im();
    }

    return false;
}

Clarity

In the pickColor method, you sometimes use the order re first, im second, and sometimes the other way around. That is very confusing. At first glance, it looks like the first and third condition and the second and fourth condition are identical.

You should not switch the order in the middle of the method, and at least be consistent within the method but even better in the entire code. Also, try to be consistent with established conventions, and typically, the real part always comes first.

However, once you implement a proper Complex.equals method, that problem will go away, because you can then simply compare complex numbers instead of having to pick them apart. And if you also implement the idea of giving them well-known names, the method will look like this:

if (complexNumber.equals(Complex.ONE)) {
    return Color.RED;
} else if (complexNumber.equals(Complex.MINUS_ONE)) {
    return Color.GREEN;
} else if (complexNumber.equals(Complex.I)) {
    return Color.BLUE;
} else if (complexNumber.equals(Complex.MINUS_I)) {
    return Color.WHITE;
} else {
    return Color.BLACK;
}

Records

Records are an experimental feature in Java 14. "Experimental" means that they can be removed at any time without warning, changed in a backwards-incompatible breaking manner without warning, and require specific command line flags to work. So, they should not be used in production.

However, they are extremely useful, and classes like your Complex class are exactly what they were made for. Changing your Complex class into a record reduces the code from this:

public final class Complex {
    public static Complex ZERO      = new Complex(0.0, 0.0);
    public static Complex ONE       = new Complex(1.0, 0.0);
    public static Complex MINUS_ONE = new Complex(-1.0, 0.0);
    public static Complex I         = new Complex(0.0, 1.0);
    public static Complex MINUS_I   = new Complex(0.0, -1.0);

    private final double re;
    private final double im;

    public Complex(final double re, final double im) {
        this.re = re;
        this.im = im;
    }

    public double getRe() { return re; }
    public double getIm() { return im; }

    @Override
    public boolean equals(final Object other) {
        if (other == null) {
            return false;
        }

        if (this == other) {
            return true;
        }

        if (other instanceof Complex) {
            var otherComplex = (Complex) other;
            return getRe() == otherComplex.getRe() && getIm() == otherComplex.getIm();
        }

        return false;
    }

    public double abs() {
        return Math.sqrt(getRe() * getRe() + getIm() * getIm());
    }

    public Complex add(final Complex b) {
        final var real = getRe() + b.getRe();
        final var imag = getIm() + b.getIm();

        return new Complex(real, imag);
    }

    public Complex multiply(final Complex b) {
        final var real = getRe() * b.getRe() - getIm() * b.getIm();
        final var imag = getRe() * b.getIm() + getIm() * b.getRe();

        return new Complex(real, imag);
    }

    public Complex divide(final Complex b) {
        final var real = (getRe() * b.getRe() + getIm() * b.getIm()) / (b.getRe() * b.getRe() + b.getIm() * b.getIm());
        final var imag = (getIm() * b.getRe() - getRe() * b.getIm()) / (b.getRe() * b.getRe() + b.getIm() * b.getIm());

        return new Complex(real, imag);
    }

    public String toString() { return getRe() + " + " + getIm() + "i"; }

    public static void main(final String[] args) {
        final var z0 = new Complex(1.0, 1.0);
        var z = z0;

        z = z.multiply(z).add(z0);
        z = z.multiply(z).add(z0);

        System.out.println(z);
    }
}

to this:

public record Complex(final double re, final double im) {
    public static Complex ZERO      = new Complex(0.0, 0.0);
    public static Complex ONE       = new Complex(1.0, 0.0);
    public static Complex MINUS_ONE = new Complex(-1.0, 0.0);
    public static Complex I         = new Complex(0.0, 1.0);
    public static Complex MINUS_I   = new Complex(0.0, -1.0);

    public double abs() {
        return Math.sqrt(re * re + im * im);
    }

    public Complex add(final Complex b) {
        final var real = re + b.re;
        final var imag = im + b.im;

        return new Complex(real, imag);
    }

    public Complex multiply(final Complex b) {
        final var real = re * b.re - im * b.im;
        final var imag = re * b.im + im * b.re;

        return new Complex(real, imag);
    }

    public Complex divide(final Complex b) {
        final var real = (re * b.re + im * b.im) / (b.re * b.re + b.im * b.im);
        final var imag = (im * b.re - re * b.im) / (b.re * b.re + b.im * b.im);

        return new Complex(real, imag);
    }

    public String toString() { return re + " + " + im + "i"; }

    public static void main(final String[] args) {
        final var z0 = new Complex(1.0, 1.0);
        var z = z0;

        z = z.multiply(z).add(z0);
        z = z.multiply(z).add(z0);

        System.out.println(z);
    }
}

We get the fields, the constructor, as well as correct implementations of equals (I am not 100% convinced that my implementation is correct!) and hashCode for free. We also get a sensible implementation of toString, although we override it here to get the usual a + bi representation.

Single Responsibility Principle

Your NewtonianChaos class does two completely different things: it computes stuff and it draws stuff. One part is all about numbers. The other part is all about colors and coordinates.

Those are different responsibilities. They should be separated into different objects.

Likewise, your Complex class is a pure data class. Why does it have a main method? Because it does two things: it represents a complex number and it tests itself. Tests should go into … well … tests, not main methods.

Testability, Modularity, Overall Design

• All your methods are static, in other words, they aren't really methods at all, they are glorified procedures. There are no objects!
• Your NewtonianChaos class is intricately linked to the Picture class, there is no way to separate them, to use them independently, to test them independently.

It is hard to test code if I can't instantiate an object that I can test. It is hard to test code if I always need the entire thing and can't test pieces independently or swap out pieces for test versions.

At the moment, the only way to test your code, is to run the entire thing, take a screenshot and compare it with a pre-recorded one. This adds a huge amount of complexity to the tests, and is very slow. Ideally, you want to be able to run your tests every couple of seconds.

And actually, that only applies to you! I cannot even do that, because I don't have the Picture class.

NewtonianChaos should be a true object, not a static class. In fact, as mentioned above, it should actually be two objects. It should have the dependency on Picture injected, not hard-coded. The Picture dependency should be abstracted behind an interface, so that, for testing purposes, I can replace the picture with a version that records the commands and compares them to a pre-recorded sequence instead of drawing on the screen.

import java.awt.Color;

public class NewtonianChaos {
    private static Complex polynomial(final Complex complexNumber) {
        return complexNumber.multiply(complexNumber).multiply(complexNumber).multiply(complexNumber)
                .add(Complex.MINUS_ONE);
    }

    private static Complex polynomialDerivative(final Complex complexNumber) {
        final var four = new Complex(4.0, 0.0);
        return complexNumber.multiply(complexNumber).multiply(complexNumber).multiply(four);
    }

    private static Complex applyNewtonMethod(final Complex complexNumber, final int iterations) {
        var complexRoot = complexNumber;

        for (var i = 0; i < iterations; i++) {
            final var newComplexRoot = complexRoot.add(
                    (polynomial(complexRoot).divide(polynomialDerivative(complexRoot))).multiply(Complex.MINUS_ONE));

            if (newComplexRoot == complexRoot) { break; }

            complexRoot = newComplexRoot;
        }

        return complexRoot;
    }

    private static Color pickColor(final Complex complexNumber) {
        if (complexNumber.equals(Complex.ONE)) {
            return Color.RED;
        } else if (complexNumber.equals(Complex.MINUS_ONE)) {
            return Color.GREEN;
        } else if (complexNumber.equals(Complex.I)) {
            return Color.BLUE;
        } else if (complexNumber.equals(Complex.MINUS_I)) {
            return Color.WHITE;
        } else {
            return Color.BLACK;
        }
    }

    private static Picture paint(final Picture picture, final int iterations) {
        final int width = picture.width();
        final int height = picture.height();

        for (int j = 0; j < width; j++) {
            final double realPart = 1.0 * j / width;

            for (int i = 0; i < height; i++) {
                final double imaginaryPart = 1.0 * i / height;

                final Complex complexNumber = new Complex(realPart, imaginaryPart);
                final Complex complexRoot = applyNewtonMethod(complexNumber, iterations);

                final Color color = pickColor(complexRoot);

                picture.set(j, i, color);
            }
        }

        return picture;
    }

    public static void main(final String[] args) {
        final int side = Integer.parseInt(args[0]);
        final int iterations = Integer.parseInt(args[1]);
        final Picture picture = new Picture(side, side);

        paint(picture, iterations);

        picture.show();
    }
}

public record Complex(final double re, final double im) {
    public static Complex ZERO = new Complex(0.0, 0.0);
    public static Complex ONE = new Complex(1.0, 0.0);
    public static Complex MINUS_ONE = new Complex(-1.0, 0.0);
    public static Complex I = new Complex(0.0, 1.0);
    public static Complex MINUS_I = new Complex(0.0, -1.0);

    public double abs() {
        return Math.sqrt(re * re + im * im);
    }

    public Complex add(final Complex b) {
        final var real = re + b.re;
        final var imag = im + b.im;

        return new Complex(real, imag);
    }

    public Complex multiply(final Complex b) {
        final var real = re * b.re - im * b.im;
        final var imag = re * b.im + im * b.re;

        return new Complex(real, imag);
    }

    public Complex divide(final Complex b) {
        final var v = b.re * b.re + b.im * b.im;
        final var real = (re * b.re + im * b.im) / v;
        final var imag = (im * b.re - re * b.im) / v;

        return new Complex(real, imag);
    }

    public String toString() {
        return re + " + " + im + "i";
    }

    public static void main(final String[] args) {
        final var z0 = new Complex(1.0, 1.0);
        var z = z0;

        z = z.multiply(z).add(z0);
        z = z.multiply(z).add(z0);

        System.out.println(z);
    }
}
```