Back to Home

Creating Newton Fractals

Hello! I was recently given an exercise to generate newton fractals of simple polynomials of a degree less than or equal to ten and I was fascinated by the results. It's great how no more than a hundred lines of C code and an understanding of some simple mathematical concepts can result to such intricate visuals!

Description of the Exercise

A brief introduction to the Newton Raphson algorithm is required. I just gave a quick read to the Wikipedia article and practiced on paper, it's easy actually! Once you're done with that, you need to acquire a basic understanding of what complex numbers are, and how the operations of multiplication and division differed from what you were told in high-school. You could then abstract them into a set of C functions that act on a user-friendly complex number struct. In case you're a visual learner and are struggling to grasp the aforementioned terms, I'd recommend the following video:

3blue1brown visualization

And that's about all you'll need to know! You can visualize a range of complex numbers as a 2D plane where the real component stands on the x-axis and the imaginary part on the y-axis of your picture. All the magic boils down to the application of the Newton Raphson method to each individual pixel of that image (with each representing a complex number of the range), the colors of which will be assigned based on one of the distinct complex roots that the algorithm lead to! One could write a parser, evaluator and a generic derivative calculator so that the program accepts any function of choice, but you might as well keep it simple by just accepting polynomials of a limited degree like I did.

Once that's done too, what's left is a way to visualize the results! You could assign each solution a unique ASCII character and print out the results on your terminal, or create your own bitmap writer (you may want to check out Wikipedia's .bmp file format graph. Don't let it frighten you, it's not as difficult as it may seem like!) and save them up in a file. You can get more creative with this: Darken each pixel based on the number of iterations that it took to reach the solution and try to spot the roots of the polynomial (they should appear brighter).

You might notice that the program is disappointingly slow when processing relatively large ranges. Newton fractals are a perfect fit for the GPU! If you'd like to take this a step further, compute and visualize the results on a GLSL shader and render the texture using OpenGL. You could exploit the occasion to learn OpenCL too, which I'm definitely planning to attempt on the near future!