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()
source to share
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
source to share
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()
source to share
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.
source to share
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()
source to share