The Newton Rapshon method is used in mathematics to find approximations to the roots of an equation. f(x) we approximate a such that f(a)=0 and a is called the root of the equation. Newton's method can be applied on any equation but it is generally used on equations for which the calculation of the root is otherwise difficult.
Let me present an illustration of the beauty of Newton's method to show how fast it converges to the root. We make a guess about the root of f(x). Let the guess be a0. Then we pass a0 iteratively into the following function:
after few iterations we get a very close approximation of the exact root. For a demonstration, let the function be: f(x) = x2-10. Now we know that the square root of 10 is 3.16228 but let's see how good the Newton's method approximates it.
Let's see what we have
f(x) = x2 - 10
f'(x) = 2x
and let out initial guess a0 be 3
a1 = 3 - (32-10)/(2*3) = 3.16666…
a2 = 3.166665 - (3.1666652-10)/(2*3.166665) = 3.162281
which is a root of the equation and we found it in just two iterations. Newton's method depends on how good your initial approximation was and converges very fast to the actual root. If however you start with a bad approximation, more interesting things will happen which are the base of this beautiful fractal.
Similarly, the Newton's method can be applied to complex equations. The basic algorithm of this method is:
- Loop through each pixel of the image.
- For each pixel, scale the (x,y) in range [-2.5,2.5] and make a complex number scaled_x + (scaled_y)i which corresponds to a0.
- Pass this a0 iteratively to the Newton's function and loop until the root is found or a set number of MAXIMUM_ITERATIONS are reached.
- After this there are many ways to color it like by the number of iterations taken or by the nearest root or using both of these.
Let's start by the simplest of them.
Number of Iterations -> Hue Mapping
In this method we map the number of iterations to a hue from [0˚,360˚] or [0,1] keeping the saturation and brightness constant and color the pixel accordingly. Here's is the code for making the fractal for z5-1. The code can be easily tweaked to make fractals of any degree of type zn-1.
Note: The classes used in the code can be found on GitHub
import fractals.math.ComplexNumber;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.File;
import java.io.InputStreamReader;
import javax.imageio.ImageIO;
import java.awt.Color;
import java.awt.image.BufferedImage;
import fractals.util.MiscUtils;
import static java.lang.System.out;
// The fractal package can be found here https://github.com/abdulfatir/fractal-library
public class NRHueMapping {
private static final String USAGE = "java NRHueMapping WIDTH HEIGHT";
private static final int MAX_ITERATIONS = 32;
private static final double EPSILON = 0.000001;
static void printUsage() {
System.out.println(USAGE);
}
static boolean isRoot(ComplexNumber z) {
z = ComplexNumber.pow(z,5);
z.subtract(new ComplexNumber(1,0));
return Math.abs(z.mod()) < EPSILON;
}
public static void main(String args[])throws IOException {
double WIDTH = 0;
double HEIGHT = 0;
try {
WIDTH = Double.parseDouble(args[0]);
HEIGHT = Double.parseDouble(args[1]);
} catch(NumberFormatException nfe) {
printUsage();
System.exit(1);
}
catch(ArrayIndexOutOfBoundsException aiob) {
printUsage();
System.exit(1);
}
float hue = 0f;
float saturation = 1f;
float brightness = 0.95f;
BufferedImage fractal = new BufferedImage((int)WIDTH, (int)HEIGHT,BufferedImage.TYPE_3BYTE_BGR);
out.println("[*] Rendering ...");
long start_time_stamp = System.currentTimeMillis();
for(int X=0; X<WIDTH; X++) {
for(int Y=0; Y<HEIGHT; Y++) {
// Scaling to [-2.5,2.5]
ComplexNumber a = new ComplexNumber((X-WIDTH/2)/(WIDTH/5), (Y-HEIGHT/2)/(HEIGHT/5));
int iteration = 0;
for(; iteration<MAX_ITERATIONS; iteration++) {
// Calculating f(x)
ComplexNumber f = ComplexNumber.pow(a,5);
f.subtract(new ComplexNumber(1,0));
// Calculating f'(x)
ComplexNumber df = ComplexNumber.pow(a,4);
df.multiply(new ComplexNumber(5,0));
// a-f(a)/f'(a)
a.subtract(ComplexNumber.divide(f,df));
if(isRoot(a))
break;
}
// Mapping no. of iterations to hue
hue = (float)iteration/MAX_ITERATIONS;
fractal.setRGB(X,Y, Color.getHSBColor(hue, saturation, brightness).getRGB());
}
}
ImageIO.write(fractal ,"PNG", new File("huemappedNR.png"));
long time_taken = System.currentTimeMillis() - start_time_stamp;
out.println("Render Time: " + MiscUtils.formatTime((int)time_taken));
}
}Two examples of fractals drawn using the above code are:
Number of Iterations -> Grayscale Mapping
In this method we map the number of iterations to shades of gray.
Here's is the code for making the fractal for z3-1. The code can be easily tweaked to make fractals of any degree of type zn-1.
import fractals.math.ComplexNumber;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.File;
import java.io.InputStreamReader;
import javax.imageio.ImageIO;
import java.awt.Color;
import java.awt.image.BufferedImage;
import fractals.util.MiscUtils;
import static java.lang.System.out;
// The fractal package can be found here https://github.com/abdulfatir/fractal-library
public class NRGrayMapping {
private static final String USAGE = "Usage:\tjava NRGrayMapping WIDTH HEIGHT";
private static final int MAX_ITERATIONS = 32;
private static final double EPSILON = 0.000001;
static void printUsage() {
System.out.println(USAGE);
}
static boolean isRoot(ComplexNumber z) {
z = ComplexNumber.pow(z,3);
z.subtract(new ComplexNumber(1,0));
return Math.abs(z.mod()) < EPSILON;
}
public static void main(String args[])throws IOException {
double WIDTH = 0;
double HEIGHT = 0;
try {
WIDTH = Double.parseDouble(args[0]);
HEIGHT = Double.parseDouble(args[1]);
} catch(NumberFormatException nfe) {
printUsage();
System.exit(1);
}
catch(ArrayIndexOutOfBoundsException aiob) {
printUsage();
System.exit(1);
}
BufferedImage fractal = new BufferedImage((int)WIDTH, (int)HEIGHT,BufferedImage.TYPE_3BYTE_BGR);
out.println("[*] Rendering ...");
long start_time_stamp = System.currentTimeMillis();
for(int X=0; X<WIDTH; X++) {
for(int Y=0; Y<HEIGHT; Y++) {
// Scaling to [-2.5,2.5]
ComplexNumber a = new ComplexNumber((X-WIDTH/2)/(WIDTH/5), (Y-HEIGHT/2)/(HEIGHT/5));
int iteration = 0;
for(; iteration<MAX_ITERATIONS; iteration++) {
// Calculating f(x)
ComplexNumber f = ComplexNumber.pow(a,3);
f.subtract(new ComplexNumber(1,0));
// Calculating f'(x)
ComplexNumber df = ComplexNumber.pow(a,2);
df.multiply(new ComplexNumber(3,0));
// a-f(a)/f'(a)
a.subtract(ComplexNumber.divide(f,df));
if(isRoot(a))
break;
}
int shade = (int)(((float)iteration/MAX_ITERATIONS)*255);
fractal.setRGB(X,Y, new Color(shade, shade, shade).getRGB());
}
}
ImageIO.write(fractal ,"PNG", new File("graymappedNR.png"));
long time_taken = System.currentTimeMillis() - start_time_stamp;
out.println("Render Time: " + MiscUtils.formatTime((int)time_taken));
}
}
Number of Iterations -> Custom Palette Mapping
In this method we map the number of iterations to a custom color palette.
Here's is the code for making the fractal for z5-1. The code can be easily tweaked to make fractals of any degree of type zn-1.
import fractals.math.ComplexNumber;
import fractals.graphics.Palette;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.File;
import java.io.InputStreamReader;
import javax.imageio.ImageIO;
import java.awt.Color;
import java.awt.image.BufferedImage;
import fractals.util.MiscUtils;
import static java.lang.System.out;
// The fractal package can be found here https://github.com/abdulfatir/fractal-library
public class NRCustomMapping {
private static final String USAGE = "Usage:\tjava NRCustomMapping WIDTH HEIGHT";
private static final int MAX_ITERATIONS = 32;
private static final double EPSILON = 0.000001;
static void printUsage() {
System.out.println(USAGE);
}
static boolean isRoot(ComplexNumber z) {
z = ComplexNumber.pow(z,5);
z.subtract(new ComplexNumber(1,0));
return Math.abs(z.mod()) < EPSILON;
}
public static void main(String args[])throws IOException {
double WIDTH = 0;
double HEIGHT = 0;
try {
WIDTH = Double.parseDouble(args[0]);
HEIGHT = Double.parseDouble(args[1]);
} catch(NumberFormatException nfe) {
printUsage();
System.exit(1);
}
catch(ArrayIndexOutOfBoundsException aiob) {
printUsage();
System.exit(1);
}
BufferedImage fractal = new BufferedImage((int)WIDTH, (int)HEIGHT,BufferedImage.TYPE_3BYTE_BGR);
int[] palette = Palette.toArray(512,
new Color(255,255,255),
new Color(0,0,138),
new Color(0,0,0),
new Color(172,88,6),
new Color(255,255,255),
new Color(255,255,255),
new Color(0,0,138),
new Color(0,0,154),
new Color(0,0,0));
out.println("[*] Rendering ...");
long start_time_stamp = System.currentTimeMillis();
for(int X=0; X<WIDTH; X++) {
for(int Y=0; Y<HEIGHT; Y++) {
// Scaling to [-2.5,2.5]
ComplexNumber a = new ComplexNumber((X-WIDTH/2)/(WIDTH/5), (Y-HEIGHT/2)/(HEIGHT/5));
int iteration = 0;
for(; iteration<MAX_ITERATIONS; iteration++) {
// Calculating f(x)
ComplexNumber f = ComplexNumber.pow(a,5);
f.subtract(new ComplexNumber(1,0));
// Calculating f'(x)
ComplexNumber df = ComplexNumber.pow(a,4);
df.multiply(new ComplexNumber(5,0));
// a-f(a)/f'(a)
a.subtract(ComplexNumber.divide(f,df));
if(isRoot(a))
break;
}
float factor = ((float)iteration)/MAX_ITERATIONS;
int index = (int)((palette.length-1)*factor);
fractal.setRGB(X,Y, palette[index]);
}
}
ImageIO.write(fractal ,"PNG", new File("custmappedNR.png"));
long time_taken = System.currentTimeMillis() - start_time_stamp;
out.println("Render Time: " + MiscUtils.formatTime((int)time_taken));
}
}
All of these fractals are beautiful but a visible flaw in all of them is that the color transition is not continuous. In the upcoming articles I'll describe the removal of color edges, coloring by root and many more cool things. Stay tuned.
If you learnt something from this article, please share it. Sharing is caring.