How to make Mandelbrot faster?
I am currently drawing a set of Mandelbrot pixels by pixel using PhotoImage and tkinter. I use mostly the algorithm directly without any modification. Are there ways to speed up computations? Maybe quickly fill in large areas of color, or predict constants?
Part of the code:
ITERATIONS = 50
WIDTH, HEIGHT = 600, 600
CENTER = (-.5, 0)
DIAMETER = 2.5
def mandel(c):
z = 0
for i in range(ITERATIONS):
z = z**2 + c
if abs(z) > 2:
return i
return ITERATIONS
root = Tk()
canvas = Canvas(root, width=WIDTH,height=HEIGHT)
canvas.pack()
img = PhotoImage(width=WIDTH, height=HEIGHT)
canvas.create_image((WIDTH/2, HEIGHT/2), image=img, state="normal")
real = CENTER[0] - 0.5 * DIAMETER
imag = CENTER[1] - 0.5 * DIAMETER
def color(i):
colors = ("#0000AA", "#88DDFF", "#FF8800", "#000000")
if i == ITERATIONS:
return colors[-1]
else:
choice = (i//2) % len(colors)
return colors[choice]
for x in range(WIDTH):
for y in range(HEIGHT):
i = mandel(complex(real, imag))
img.put(color(i), (x, HEIGHT-y))
imag += DIAMETER / HEIGHT
imag = CENTER[1] - 0.5 * DIAMETER
real += DIAMETER / WIDTH
mainloop()
Setting one pixel at a time is probably the main source of slowdown. Instead of calling put for each pixel, the computer is a whole row of pixels or an entire matrix of pixels, and then called once at the end of the loop.
You can find an example here, among other places: https://web.archive.org/web/20170512214049/http://tkinter.unpythonic.net:80/wiki/PhotoImage#Fill_Many_Pixels_at_Once
Here is my code, it draws a 640x480 Mandelbrot in 8-9 seconds.
It performs up to 256 iterations per pixel, uses a list of color maps, "sets" only once on, PhotoImage
and does not rely on symetry, so it can display any zoomed area of the set.
It's a shame that Tkinter doesn't allow access to bitmap information PhotoImage
as a buffer and that a clunky string is required.
from tkinter import Tk, Canvas, PhotoImage,NW,mainloop
from time import clock
def mandel(kx,ky):
""" calculates the pixel color of the point of mandelbrot plane
passed in the arguments """
global clr
maxIt = 256
c = complex(kx, ky)
z = complex(0.0, 0.0)
for i in range(maxIt):
z = z * z + c
if abs(z) >= 2.0:
return (255-clr[i],0,0)
return(0,0,0)
def prepare_mdb(xa,xb,ya,yb):
""" pre-calculates coordinates of the mandelbrot plane required for each
pixel in the screen"""
global x,y,xm,ym
xm.clear
ym.clear
xm=[xa + (xb - xa) * kx /x for kx in range(x)]
ym=[ya + (yb - ya) * ky /y for ky in range(y)]
x=640
y=480
#corners of the mandelbrot plan to display
xa = -2.0; xb = 1.0
ya = -1.5; yb = 1.5
#precalculated color table
clr=[ int(255*((i/255)**12)) for i in range(255,-1,-1)]
xm=[]
ym=[]
prepare_mdb(xa,xb,ya,yb)
#Tk
window = Tk()
canvas = Canvas(window, width = x, height = y, bg = "#000000")
t1=clock()
img = PhotoImage(width = x, height = y)
canvas.create_image((0, 0), image = img, state = "normal", anchor = NW)
pixels=" ".join(("{"+" ".join(('#%02x%02x%02x' % mandel(i,j) for i in xm))+"}" for j in ym))
img.put(pixels)
canvas.pack()
print(clock()-t1)
mainloop()
Pure python is not that fast for numeric code. The easiest way to speed things up is to use PyPy. If that's not fast enough, highlight your algorithms with numpy. If that's not fast enough yet, use Cython or rewrite it in C.
For a slight increase in speed (but not enough to compensate for the difference between the compiled language and the interpreted one), you can pre-compute some of the values.
Right now, you are evaluating DIAMETER / HEIGHT
once per inner loop and CENTER[1] - 0.5 * DIAMETER
, and also DIAMETER / WIDTH
once per outer loop. Do this beforehand.
len(colors)
also will not change and can be replaced with a constant. In fact, I would probably write this function as
def color(i):
if i == ITERATIONS:
return "#000000"
else:
return ("#0000AA", "#88DDFF", "#FF8800", "#000000")[(i//2) % 4]
# are you sure you don't want ("#0000AA", "#88DDFF", "#FF8800")[(i//2) % 3] ?
Also, it x**2
is slower than that x*x
(since the operator x**y
does not work for the trivial case y==2
), so you can speed up this calculation a little.
Most of the time is spent in the inner loop in mandel (). z*z
instead z**2
had little effect. There's not much to speed up there that I see. Removing constants from other loops is ineffective, although I prefer to do it. Choosing Iterations to ITERATIONS//2 % len(colors) == len(colors)-1
, as in 46 //2 % 4 == 3
, allows you to simplify your code. Using symmetry around the x-axis cuts the time in half. Running imag at 0 eliminates the rounding error of 300 subtractions from +/- DIAMETER / 2 and results in a clean centerline in the image.
from tkinter import *
ITERATIONS = 46
WIDTH, HEIGHT = 601, 601 # odd for centering and exploiting symmetry
DIAMETER = 2.5
start = (-.5 - DIAMETER / 2, 0) # Start y on centerline
d_over_h = DIAMETER / HEIGHT
d_over_w = DIAMETER / WIDTH
def mandel(c):
z = 0
for i in range(ITERATIONS):
z = z*z + c
if abs(z) > 2:
return i
return ITERATIONS
root = Tk()
canvas = Canvas(root, width=WIDTH,height=HEIGHT)
canvas.pack()
img = PhotoImage(width=WIDTH, height=HEIGHT)
canvas.create_image(((WIDTH+1)//2, (HEIGHT+1)//2), image=img, state="normal")
real, imag = start
colors = ("#0000AA", "#88DDFF", "#FF8800", "#000000")
ncolors = len(colors)
yrange = range(HEIGHT//2, -1, -1) # up from centerline
ymax = HEIGHT - 1
for x in range(WIDTH):
for y in yrange:
i = mandel(complex(real, imag))
color = colors[i//2 % ncolors]
img.put(color, (x, y))
img.put(color, (x, ymax - y))
imag += d_over_h
imag = start[1]
real += d_over_w
mainloop()