Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!quanta.eng.ohio-state.edu!kcgl1.eng.ohio-state.edu!DAVISM
From: DAVISM@kcgl1.eng.ohio-state.edu (Michael T. Davis)
Newsgroups: comp.graphics
Subject: Excluding Mandelbrot set -- Summary
Message-ID: <3586@quanta.eng.ohio-state.edu>
Date: 22 Nov 89 18:17:09 GMT
References: <3544@quanta.eng.ohio-state.edu>
Sender: news@quanta.eng.ohio-state.edu
Organization: Ohio State University
Lines: 105


In article <3544@quanta.eng.ohio-state.edu>, I wrote:

#
#	I have written a program based primarily on the fractal generating
#program from Douglas A. Young's X WINDOW SYSTEMS AND APPLICATIONS WITH XT.
#This thing is unbearably slow, and our system programmer suggested figuring
#out some way to determine if a given point is within the Mandelbrot set or
#not, before actually running through some number of iterations.  I don't need
#to know the distance from the origin, only whether or not the point is within
#the Mandelbrot set or not.  The algorithm should amount to no more than a
#simple check, something like the following:
#
#	if (InMandelbrot(point(x,y)))
#	    /*ignore*/
#	else
#	    /*calculate distance*/
#
#The basic idea is to avoid running through the "maximum" number of iterations
#for each point in the Mandelbrot set.  Is this possible, or alternately, is
#there a more acceptable algorithm in terms of speed?
#

	All the replies I received pointed out that by the very nature of the
Mandelbrot set, you have to go through all the iterations, as that is how the
set is defined.  This much I suspected.  Luckily, almost all the messages I
received mentioned ways of speeding up the calculations.

	celit!billd@celerity.fps.com provided several ways of optimizing the
code:

>	Given: the original function of cr+ci
>
>		zr = 0.0;
>		zi = 0.0;
>		for ( i = 0; i < MAX && sqrt(zr*zr+zi*zi) < 2.0; i++ ){
>			zt = zr * zr - zi * zi + cr;
>			zi = 2.0 * zr * zi + ci;
>			zr = zt;
>		}
>		return i;
>
>	You can do better with:
>
>		zr = cr;
>		zi = ci;
>		for ( i = 1; i < MAX && zr*zr+zi*zi < 4.0; i++ ){
>			zt = zr * zr - zi * zi + cr;
>			zi = 2.0 * zr * zi + ci;
>			zr = zt;
>		}
>		return i;
>
>	Using the distance squared less than four is just as valid as distance
>	less than two.  Losing a transendental operation is always a big win.
>	Cutting out the first iteration which is redundant may save a small
>	amount of time.
>
>	With some optimizers (at least Sun's with SunOS 3.4) you can do better
>	with:
>
>		zr = cr;
>		zi = ci;
>		two = 2.0;
>		four = 4.0;
>		for ( i = 1; i < MAX && zr*zr+zi*zi < four; i++ ){
>			zt = (zr * zr - zi * zi) + cr;
>			zi *= two * zr;
>			zi += ci;
>			zr = zt;
>		}
>		return i;
>

	Many replies included variations of the following theme from Dave
Platt (dplatt@coherent.com), who wrote a program called MandelZot for the Mac
(available via ftp at SUMEX-AIM.Stanford.Edu):

>There are a couple of algorithms that people have developed to speed things
>up.  These algorithms work by entirely avoiding the iteration on many points.
>One algorithm is the Mariani/Silver "Eat my dust!" divide-and-conquer
>algorithm... it assumes that if all of the points lying on the border of a
>rectangle have the same dwell (the same number of iterations prior to
>divergence), then all points in the interior of the rectangle can be marked as
>having the same dwell...

	Several others -- Everett Lipman (lipm@tank.uchicago.edu) and Todd S.
Lehman (toddl%garfield.cs.wisc.edu@cs.wisc.edu) -- mentioned the book THE
SCIENCE OF FRACTAL IMAGES by Peitgen and Richter (Springer Verlag publishers),
in which many algorithms are mentioned for speeding up the computation.

	Thanks also go to Mark (edsr!jupiter!cheeks@uunet.uu.net), Tony Foiani
(afoiani@NMSU.Edu), Doug Young (dmy@solbourne.com -- no relation to the author
of the aforementioned book) and anyone else who I might have missed.

							Mike

    ________________________________________________________________________
   |   InterNet> davism@{kcgl1.eng|rcgl1.eng|osu-20.ircc}.ohio-state.edu    |
   |                                  -or-                                  |
   |                       davis-m@eng.ohio-state.edu                       |
   |                         CompuServe> 73667,541                          |
   |************************************************************************|
   |                      These thoughts, they be mine                      |
    ------------------------------------------------------------------------