DAVISM@kcgl1.eng.ohio-state.edu (Michael T. Davis) (11/23/89)
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 | ------------------------------------------------------------------------
pell@isy.liu.se (P{r Emanuelsson) (11/26/89)
Michael T. Davis: > 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... This is of course not mathematically correct, but it's a useful assumption. Especially if you take, say, every fifth point on the rectangle borders. Sure, the images will start to look a bit strange but it's useful if you want to have a quick peek at what things look like. But if you take *every* point on the border and the image is very complex (:-), as is often the case at higher magnifications, the standard Mandelbrot algorithm is actually faster. Region search is another method which can be quite fast. You label the areas with equal dwell and then fill in the right color in a raster-scan fashion. I might release some programs that implement this, but I don't have anything ready yet. Don't ask me: I will announce here. /Pell -- Dept. of Electrical Engineering pell@isy.liu.se University of Linkoping, Sweden ...!uunet!isy.liu.se!pell
dplatt@coherent.com (Dave Platt) (11/28/89)
In article <1989Nov25.174444.8953@isy.liu.se> pell@isy.liu.se (P{r Emanuelsson) writes: >This is of course not mathematically correct, but it's a useful assumption. >Especially if you take, say, every fifth point on the rectangle borders. >Sure, the images will start to look a bit strange but it's useful if you >want to have a quick peek at what things look like. It's true that the rectangle-approximation system is not mathematically justifiable. However, it actually works out in practice _extremely_ well... there are very few cases in which it miscolors an image, as long as it's implemented correctly. The implementation I use (Mariani/Silver) was described in the Amygdaya newsletter a couple of years ago. Briefly: pick a rectangular region which does not include the full M-set. Scan the border of this region, checking to see whether it's monochromatic. If so, color the entire region with this color and exit. Otherwise, divide the region in half along its longer axis, and run this algorithm recursively on each half. Stop recursing if the size of a rectangle drops below a chosen minimum (shorter side < 5 seems to work well) and color points in the rectangles by the usual point-at-a-time iteration. This algorithm may "miss" occasionally, if a tiny tendril of one color "sneaks through" the border of a rectangle which is otherwise monochromatic. In practice, this seems to be a very rare occurrance... I've calculated images using a normal raster-scan sweep and via the Mariani/Silver algorithm, and have been unable to see _any_ differences between the two. It's entirely possible that my eyes have missed a single-pixel difference here and there... but no gross differences have ever appeared in the tests I've run. At high magnifications, and at high dwell limits, the Mariani/Silver algorithm doesn't buy you much... the dwell bands are so close together, and so greatly convoluted, that there aren't many sizeable monochromatic areas to be found. In this situation, the Mariani/Silver algorithm's performance degenerates, and it becomes slightly slower than the raster-scan iteration (same number of calculations, with higher overhead). In practice, I've never seen Mariani/Silver run slower than raster-scan. -- Dave Platt VOICE: (415) 493-8805 UUCP: ...!{ames,apple,uunet}!coherent!dplatt DOMAIN: dplatt@coherent.com INTERNET: coherent!dplatt@ames.arpa, ...@uunet.uu.net USNAIL: Coherent Thought Inc. 3350 West Bayshore #205 Palo Alto CA 94303
rokicki@polya.Stanford.EDU (Tomas G. Rokicki) (11/28/89)
dplatt@coherent.com (Dave Platt) writes: > The implementation I use (Mariani/Silver) was described in the Amygdaya > newsletter a couple of years ago. Briefly: pick a rectangular region > which does not include the full M-set. Scan the border of this region, > checking to see whether it's monochromatic. If so, color the entire > region with this color and exit. Otherwise, divide the region in half > along its longer axis, and run this algorithm recursively on each half. > Stop recursing if the size of a rectangle drops below a chosen minimum > (shorter side < 5 seems to work well) and color points in the rectangles > by the usual point-at-a-time iteration. I've found a different algorithm to be faster, combining parts of the raster scan and parts of the rectanglularly-enclosed algorithms. You calculate the entire top and the entire bottom raster row of a region using the standard scan approach. Then, you search these rows for a region of a single color, where the color is the same in both rows. For each of these regions, you scan down to complete the rectangle---if you can (and you will, most of the time) then you fill the entire rectangle. Then, you recurse, filling in a row in the middle, and iterating as before. The reason this works is that most regions of the same color are approximately parallelograms: ---------------|---------------|------------------- one raster row /| | / / | | / / | | / / | | / / | |/ ---------------|---------------|------------------- another raster row The parallelogram is the `actual' same-color region. The rectangle is the same-color region you find because the top and bottom colors are the same. This helps maximize the size of the rectangles you find each time, and there is very, very little overhead . . . Of course, when you scan vertically trying to complete a rectangle, you save away the colors you calculate into an array so you don't have to recalculate them . . . I've always wanted to refine this into a `boundary seeking' algorithm (ie, trace out the actual parallelogram rather than using a bunch of progressively smaller rectangles) but haven't had the time or patience. -tom
jwz@teak.berkeley.edu (Jamie Zawinski) (11/28/89)
In case anyone is interested, I've got some Lisp code that computes the Mandelbrot set using what's been being called the Mariani/Silver algorithm (imagine my dismay at finding out that someone thought of it before me :-/). Most of the code is TI Explorer specific user-interface stuff, but it will probably run on a Symbolics without much tweaking. I think the actual bitmap-generation is portable Common Lisp. (On an Explorer II, this baby generates faster than anything I've seen on a Sun 3/60 or Amiga, even though everyone "knows" that C is faster than Lisp. So there!) Anonymous FTP from spice.cs.cmu.edu, in the directory /usr/jwz/public/, file mandelbrot.lisp. -- Jamie