How to make faster Mandelbrot set plot

Question

Ive written a function which uses turtle to draw a Mandelbrot set, however its very slow (~10's minutes) for any decent resolution, how could I make my code more efficient?

import math, turtle

screen = turtle.Screen()
screen.setup(width=1000, height=600 ,startx=0, starty=0)
screen.bgcolor('black')
screen.tracer(0)
pen = turtle.Turtle()
pen.penup()
pen.speed(10)
width = 800
height = 600
MAX_ITER=80

def draw_mandelbrot(c):
  z = 0
  n = 0
  while abs(z) <= 2 and n < MAX_ITER:
      z = z * z + c
      n += 1
  return n

def generate_mandelbrot_set(StartR, StartI, EndR, EndI):
  screen.setworldcoordinates(StartR, StartI, EndR, EndI)
  screen.bgcolor("black")
  for x in range(width):
      for y in range(height):
          c = complex(StartR + (x / width) * (EndR - StartR), StartI + (y / height) * (EndI - StartI))
          m = draw_mandelbrot(c)
          color = (255 - int(m * 255 / MAX_ITER)) / 255
          pen.goto(StartR + (x / width) * (EndR - StartR), StartI + (y / height) * (EndI - StartI))
          if y == 0:
            pen.pendown()
          elif y == height-1 :
            pen.penup()
          pen.color(color, color, color)
          pen.dot()

generate_mandelbrot_set(-2,-1,1,1)

screen.update()
screen.mainloop()

Im new to coding so any advice would be hugely appreciated!

Answer 1

I tried your code with a 80x60 resolution and I really liked the look of the little vertical lines and dots. Doing the Mandelbrot set in turtle graphics is impressive! You could speed it up by using screen.tracer(0, 0) and pen.speed('fastest') (which is faster than 10) for some minimal gains.

But at 800x600, the turtle is the wrong tool for the job: not only the artistic lines won't be visible, Python will spend a lot of time doing cute things like animating the turtle movements (which is only disabled at speed 11).

My suggestion would be to ditch the turtle and use a graphical interface with a canvas object, where you can place individual pixels. Python comes with Tkinter, a simple but efficient library that can do this.

Here's the exact same rendering logic, translated to Tkinter, finishing in under 7 seconds:

from tkinter import Tk, Canvas, PhotoImage, mainloop

WIDTH = 800
HEIGHT = 600
MAX_ITER = 80

def draw_mandelbrot(c):
    z = 0
    n = 0
    while abs(z) <= 2 and n < MAX_ITER:
        z = z * z + c
        n += 1
    return n

def generate_mandelbrot_set(StartR, StartI, EndR, EndI):
    img = PhotoImage(width=WIDTH, height=HEIGHT)
    for x in range(WIDTH):
        for y in range(HEIGHT):
            c = complex(
                StartR + (x / WIDTH) * (EndR - StartR),
                StartI + (y / HEIGHT) * (EndI - StartI),
            )
            m = draw_mandelbrot(c)
            color = 255 - int(m * 255 / MAX_ITER)
            color_str = "#{0:02x}{0:02x}{0:02x}".format(color)
            img.put(color_str, (x, y))
    return img

window = Tk()
canvas = Canvas(window, width=WIDTH, height=HEIGHT, bg="#000000")
canvas.pack()

img = generate_mandelbrot_set(-2, -1, 1, 1)

# Important: don't add the image to the canvas until it's fully generated.
# Otherwise each added pixel will cause the canvas to re-render.
canvas.create_image((WIDTH / 2, HEIGHT / 2), image=img, state="normal")

mainloop()

Answer 2

I've attempted to speed up your program by approaching the problem slightly more as vectors instead of pixels based on the comment by @Ouroborus (+1):

from turtle import Screen, Pen

MAX_ITER = 80
WIDTH, HEIGHT = 800, 600

def compute_mandelbrot(c):
    z = complex(0)
    n = 0

    while n < MAX_ITER and abs(z) <= 2.0:
        z = z * z + c
        n += 1

    return n

def generate_mandelbrot_set(StartR, StartI, EndR, EndI):
    screen.setworldcoordinates(StartR, StartI, EndR, EndI)

    pen = Pen(visible=False)
    pen.penup()
    pen.setheading(90)

    for x in range(WIDTH):
        real = StartR + (x / WIDTH) * (EndR - StartR)
        pen.goto(real, StartI)
        pen.pendown()

        for y in range(HEIGHT):
            c = complex(real, StartI + (y / HEIGHT) * (EndI - StartI))
            m = compute_mandelbrot(c)
            gray = 1 - m / MAX_ITER
            pen.color(gray, gray, gray)
            pen.forward((EndI - StartI) / HEIGHT)

        pen.penup()
        screen.update()

screen = Screen()
screen.setup(WIDTH, HEIGHT, startx=0, starty=0)
screen.bgcolor('black')
screen.tracer(0)

generate_mandelbrot_set(-2, -1, 1, 1)

screen.mainloop()

However, you'll notice that it introduces some line artifacts:

These are due to a bug in the turtle's line drawing logic discussed here:

Why is turtle lightening pixels?

How do I control turtle's self._newline()?

Answer 3

Like its animal namesake, turtle is very, very slow. It is only ever used as an educational tool, to let the learners see in real time how their algorithm translates to the turtle's movements. It is thus, unfortunately, pointless to try to speed up the code where a turtle poops out an image pixel by excruciating pixel. To get it up to speed (hehe), better tooling is required.

Jean-François Puget made an excellent comparison of various ways to generate the Mandelbrot set in Python. Among them, there is code for using GPU, code for using compiled Python... I chose to show you the numpy method, i.e. using the tools that most intermediate Python programmers might be familiar with, without going overboard. numpy is a library that does array calculations outside Python, and is thus able to do them very, very fast. Also, I switched the display library to pillow, a popular image processing library. Together, numpy and pillow let you do this quite fast.

As you said you were new to coding, a lot of this might be a bit advanced, but I wanted to show how actual production code might solve this issue, poossibly inspire you to see what is possible. Also, given that you are messing with Mandelbrot, I suspect you might have sufficient basis in mathematics to intuitively grasp the array operations numpy is providing here, even if you are just starting coding.

# pip install pillow numpy

from PIL import Image
import numpy as np

# Adapted from https://gist.github.com/jfpuget/60e07a82dece69b011bb

def mandelbrot(cmin, cmax, width, height, maxiter):
    """
    cmin: bottom left corner, as a complex number
    cmax: top right corner, as a complex number
    width: width of the resultant array
    height: height of the resultant array
    maxiter: maximum number of iterations
    """

    # make the real axis as an array of shape (width)
    real = np.linspace(cmin.real, cmax.real, width, dtype=np.float32)
    # make the imaginary axis as an array of shape (height)
    imag = np.linspace(cmin.imag, cmax.imag, height, dtype=np.float32) * 1j
    # combine them into a complex array of shape (width, height)
    c = real + imag[:, None]

    # make the output array of the same shape, fill it with int zeroes
    output = np.zeros(c.shape, dtype='uint16')
    # and a z array of the same shape, fill it with complex zeroes
    z = np.zeros(c.shape, np.complex64)
    # do the mandelbrotty thing:
    for i in range(maxiter):
        # make a bool array of the same shape showing where `z` is within range
        notdone = np.less(z.real * z.real + z.imag * z.imag, 4.0)
        # at the places where `notdone` is true,
        # update the current iteration number;
        # the places where `z` got out of range will be unaffected
        output[notdone] = i
        # update `z` in those same places
        z[notdone] = z[notdone] ** 2 + c[notdone]
    # make the center zero for nice contrast
    output[output == maxiter-1] = 0

    return output

cmin, cmax = -2-1j, 1+1j
width, height = 800, 600
maxiter = 80
# calculate the mandelbrot set
m = mandelbrot(cmin, cmax, width, height, maxiter)
# calculate the greyscale pixels
pixels = (m * 255 / maxiter).astype('uint8')
# make the greyscale image
img = Image.fromarray(pixels, 'L')
# and let us see it
img.show()

It takes my Macbook Pro 23ms to generate the mandelbrot array and then the image with the same parameters as yours.

Answer 4

Your code has two main problems: firstly, turtle isn't adapt for drawing fractals, because of how slow it draws. You should really use some other module like pygame. secondly, also python is slow calculating. I would suggest you use the module numba. Here is the documentation: https://numba.pydata.org/numba-doc/latest/index.html. You may need to split the main function in halfth and use one of them with numba for the calculation and the other one to display it.