DAVISM@kcgl1.eng.ohio-state.edu (Michael T. Davis) (11/17/89)
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?
Much obliged,
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 |
------------------------------------------------------------------------cj@hpsad.HP.COM (Chris Johnson) (11/22/89)
> 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? > > Much obliged, > Mike Unfortunately, the definition of the mandelbrot set is: 2 Z = Z + C where Z & C are complex, and successive iterations with Z starting at (0 + 0i), Z does not ever atain a magnitude greater that 2. This implies that one must, necessarily, go through some number of iterations to determine whether or not the magnitude of Z is going to "blow up" or stabilize. Actually, I'm not sure about the limit of 2, maybe it's just whether or not it blows up. If anyone knows of any other way to do this, please send it in, also please feel free to correct me if I am wrong, I don't claim to be a mathmatician... -cj cj@hpsad.hp.com
prem@geomag.fsu.edu (Prem Subrahmanyam) (11/23/89)
In article <480003@hpsad.HP.COM> cj@hpsad.HP.COM (Chris Johnson) writes: >where Z & C are complex, and successive iterations with Z starting at >(0 + 0i), Z does not ever atain a magnitude greater that 2. This implies >that one must, necessarily, go through some number of iterations to determine >whether or not the magnitude of Z is going to "blow up" or stabilize. Actually, >I'm not sure about the limit of 2, maybe it's just whether or not it blows up. Actually, the true definition is that the number does not "blow up" to infinity. 2 is chosen, as there is a theorem that was developed that proves that if the magnitude of a number exceeds 2, then it will "blow up" to infinity very shortly afterwards, 2 is simply the smallest number at which it is certain that the magnitude will blow up. FYI, there is also a theorem that was developed that proves that the entire Mandelbrot Set is connected, i.e., that between small "pockets" of Mandelbrot numbers, there also exist tiny "filaments" of Mandelbrot numbers that connect them, so there is no isolated pocket of Mandelbrot numbers within the set. Some of the larger "filaments" are what create the lightning-like effects surrounding portions of the set. Oh, I forgot to mention, a Mandelbrot number is actually one that does not blow up to infinity after an infinite number of recursions. Of course, we'd be waiting around forever to find one Mandelbrot number. ---Prem Subrahmanyam (prem@geomag.gly.fsu.edu)
billd@fps.com (Bill Davids_on) (11/23/89)
In article <380@fsu.scri.fsu.edu> prem@geomag.UUCP (Prem Subrahmanyam) writes: > Actually, the true definition is that the number does not "blow up" to > infinity. 2 is chosen, as there is a theorem that was developed that proves > that if the magnitude of a number exceeds 2, then it will "blow up" to > infinity very shortly afterwards, 2 is simply the smallest number at which > it is certain that the magnitude will blow up. FYI, there is also a theorem > that was developed that proves that the entire Mandelbrot Set is connected, > i.e., that between small "pockets" of Mandelbrot numbers, there also exist > tiny "filaments" of Mandelbrot numbers that connect them, so there is no > isolated pocket of Mandelbrot numbers within the set. Some of the larger > "filaments" are what create the lightning-like effects surrounding portions > of the set. Gee, THEOREMS! I assume that means that there are proofs! If there are proofs then what is Krantz complaining about? If someone is going to the trouble to prove things then it's just as valid as any other mathematics (much of which is only of interest to mathematicians). > Oh, I forgot to mention, a Mandelbrot number is actually one that does not > blow up to infinity after an infinite number of recursions. Of course, we'd > be waiting around forever to find one Mandelbrot number. I seem to recall mention of a theorem that extrememely few numbers will "blow up" if they haven't already within 1000 iterations. By experiment, I've found most numbers that diverge, do so well before hitting 100. The gain in non-Mandelbrot points from 100 to 256 is fairly small. The gain from 256 to 1000 is even smaller. (often there is no difference depending on resolution and sample space). Does anyone have references for these theorems (including proofs)? English is prefered though I suppose I could dig out my old french book and wade through them in french if I had to. I'm tired of reading picture books on fractals. I'd like to know why 2 is magic. Why not 1.99? --Bill Davidson
md85-epi@nada.kth.se (Urban Koistinen) (11/23/89)
In article <4233@celit.fps.com> billd@fps.com (Bill Davids_on) writes: >I'd like to know why 2 is magic. Why not 1.99? Try c = -2 > >--Bill Davidson the initial value z(0) = 0 the recursion formula z(n+1) = z(n)*z(n) + c the distance from 0 of the next value |z(n+1)| >= |z(n)*z(n)| - |c| this you can use to prove that if |c|>2 then |z| grows without bond. Similarly you can prove that if |c|<=1/4 then c lies in the mandelbrot set. --Urban Koistinen
anton@sting.Berkeley.EDU (Jeff Anton) (11/24/89)
In one of the books about fractals there is a system of determining how far away a given point is from any point in the Mandelbrot set. From that you could write a program which could eliminate pixels from the set until it can eliminate no more leaveing pixels in the Mandelbrot set. In that book there are photos of graphics where these points outside of the Mandelbrot set were rendered as semi-sphears with a radius of the computed distaince to the set. Something like a sea of bubbles surrounding the familiar Mandelbrot shape. I think the system is not really better than traditional approach and is more complicated. Jeff Anton
pell@isy.liu.se (P{r Emanuelsson) (11/26/89)
Michael T. Davis: > 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? It is possible, but you have to do it while calculating the usual formula. Mandelbrot points "converges" by going into "loops" (or "cycles"). Thus, as soon as you detect a loop you can conclude that the point is in the set and move on. Unfortunately, it's not that simple to detect a loop. You have to store old iteration values and search for a match and undoubtedly this will take some time. I'm currently supervising a master's project and the students report that the gain was insignificant. Maybe this is because at larger magnifications there are usually not *that* many set-points in the region of interest but the extra calculation has to be performed for every point. There are, however, other faster algorithms, especially if you want to have a rough-n'-fast outline of what you're looking at. More about this later. /Pell -- Dept. of Electrical Engineering pell@isy.liu.se University of Linkoping, Sweden ...!uunet!isy.liu.se!pell
pell@isy.liu.se (P{r Emanuelsson) (11/26/89)
Jeff Anton: >In one of the books about fractals there is a system of determining >how far away a given point is from any point in the Mandelbrot set. >From that you could write a program which could eliminate pixels from the >set until it can eliminate no more leaveing pixels in the Mandelbrot set. >[...] >I think the system is not really better than traditional approach and >is more complicated. Perhaps not, but it's a different way! And it's fun to watch too! The main drawback as I see it is that the algorithm only generates B/W images. The main advantage is speed - especially when you are not interested about details in the current magnification, but want to move on to more interesting details. Now, suppose you choose to use the standard Mandelbrot algorithm, but to save time you only iterate every tenth point. Voila! The time drops to 1/100! But the resulting image will be of no use. Instead, use the disk algorithm mentioned above! As soon as you hit a point not in the set, the algorithm will recursively generate disks around the set. Not 1/100, but still a significant speedup. If you want full resolution the disk algorithm will be slower, though. I implemented this in February. You can get the program by anonymous FTP from isy.liu.se (130.236.1.3), file FastMtool.tar.Z. It's for SUN:s, but the algorithm is easy to rip out. I think the program FRACTINT for PC:s contains this algorithm too, but I haven't tried it. /Pell -- Dept. of Electrical Engineering pell@isy.liu.se University of Linkoping, Sweden ...!uunet!isy.liu.se!pell
peter@ficc.uu.net (Peter da Silva) (11/26/89)
One thing that can be done to speed up calculations of the mandelbrot set is to use memory. After you have determined that a point is in the set, you know that all the other points visited in determining that are in the set as well, so you can mark them black. Similarly, if you determine a point is not in the set you know that all the other points you visited are not in the set as well, so you can mark them white (or whatever colors you're using). This is a pretty safe optimisation. Also, if you are iterating over a point and you hit a point you've already calculated you can cut your calculations short there. But this optimisation may lead to problems from quantisation. -- `-_-' Peter da Silva <peter@ficc.uu.net> <peter@sugar.lonestar.org>. 'U` -------------- +1 713 274 5180. "The basic notion underlying USENET is the flame." -- Chuq Von Rospach, chuq@Apple.COM
cheeks@edsr.eds.com (Mark Costlow) (11/28/89)
In article <7106@ficc.uu.net>, peter@ficc.uu.net (Peter da Silva) writes: > One thing that can be done to speed up calculations of the mandelbrot set is > to use memory. After you have determined that a point is in the set, you know > that all the other points visited in determining that are in the set as well, > so you can mark them black. Similarly, if you determine a point is not in the > set you know that all the other points you visited are not in the set as well, > so you can mark them white (or whatever colors you're using). This is a pretty > safe optimisation. > Hmmm ... maybe I'm missing something here, but that doesn't seem to be a valid algorithm. Since the Mandelbrot algorithm is Z(n+1) = Z(n)^2 + C, then each iteration for a given C defines a "path" through the plane, stopping at several (possibly infinite) discrete points. But, isn't the path different for each different C? I mean, just because you saw point P when iterating with C1, doesn't mean that if you see point P when iterating on C2 that the C2 iteration will behave identically to the C1 iteration. Well, I didn't word that pretty well, but I think you can see what I mean. So, am I missing something? > `-_-' Peter da Silva <peter@ficc.uu.net> <peter@sugar.lonestar.org>. > 'U` -------------- +1 713 274 5180. > "The basic notion underlying USENET is the flame." > -- Chuq Von Rospach, chuq@Apple.COM Mark Costlow cheeks@edsr.eds.com
dplatt@coherent.com (Dave Platt) (11/28/89)
In article <4233@celit.fps.com> billd@fps.com (Bill Davids_on) writes: >I seem to recall mention of a theorem that extrememely few numbers >will "blow up" if they haven't already within 1000 iterations. >By experiment, I've found most numbers that diverge, do so well >before hitting 100. The gain in non-Mandelbrot points from 100 >to 256 is fairly small. The gain from 256 to 1000 is even smaller. >(often there is no difference depending on resolution and sample >space). Numerically, this is true... only an extremely thin "border" around M itself has dwells which lie above 256 (for example). If you're looking at a magnification-1 overview of M, there's not much sense in setting the dwell limit much above 256. However... things are very different if you're looking at high- magnification zooms. Many _very_ interesting and highly-detailed patterns can be found very close to M itself, at high magnifications (say, 10^12 or more). The points in these patterns tend to have very high dwell values... 2000 or more is not unusual, and I've seen some images that required a dwell limit of 32765 (which is as high as my program will go at the moment). Needless to say, these images take a _long_ time to resolve. I calculated an image a few months ago which required more than 36 hours on a dedicated Mac II, using a hand-coded 68881 instruction loop for the iterations. It was 1500 pixels wide by 1000 high, examined an area of M's border at a magnification of about 10^12, and had a dwell limit of 4095 or so (I think... it's been a while). I recently had a slide made from this data, and then had it printed on Cibachrome transparency material... fantastic pseudo-stained-glass imagery courtesy of a fractal formula! -- 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
dplatt@coherent.com (Dave Platt) (11/28/89)
In article <7106@ficc.uu.net> peter@ficc.uu.net (Peter da Silva) writes: >One thing that can be done to speed up calculations of the mandelbrot set is >to use memory. After you have determined that a point is in the set, you know >that all the other points visited in determining that are in the set as well, >so you can mark them black. Similarly, if you determine a point is not in the >set you know that all the other points you visited are not in the set as well, >so you can mark them white (or whatever colors you're using). This is a pretty >safe optimisation. > >Also, if you are iterating over a point and you hit a point you've already >calculated you can cut your calculations short there. But this optimisation >may lead to problems from quantisation. Urrgh. I tried this two years ago, believing (as you do) that it was valid. 'Taint.. it doesn't work at all well. Each point that you iterate has a unique track, which is controlled by the value of the original point. Take a point A0, and iterate it through points A1, A2, A3, ... and so forth. Note where it goes. Now... start with a point B0. Let's set B0 precisely equal to point A2, just for the sake of argument. Iterate B0, through points B1, B2, ... and so forth. Now... given that B0 = A2, will B1 = A3, and B2 = A4, and so forth. Nope... usually not. Why? Well, the iterations are being derived from _different_ formulae! For example: we know that A3 = A2^2 + A0, and B1 = B0^2 + B0. A2^2 = B0^2, so that part of the formula is fine... but A0 != B0, and so A3 != B1. The tracks diverge immediately. I've seen cases in which the tracks of points lying well outside of M actually pass through the body of M... and vice versa. The optimization you suggest would probably work well when iterating sets using the Julia formula... because the value added during each iteration doesn't depend on the value of the starting point. -- 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
dplatt@coherent.com (Dave Platt) (11/28/89)
In article <1989Nov25.173416.8870@isy.liu.se> pell@isy.liu.se (P{r Emanuelsson) writes: >Jeff Anton: >>In one of the books about fractals there is a system of determining >>how far away a given point is from any point in the Mandelbrot set. >>From that you could write a program which could eliminate pixels from the >>set until it can eliminate no more leaveing pixels in the Mandelbrot set. >>[...] >>I think the system is not really better than traditional approach and >>is more complicated. > >Perhaps not, but it's a different way! And it's fun to watch too! > >The main drawback as I see it is that the algorithm only generates B/W images. This isn't strictly true... although the algorithm is used only for B/W images in "The Science of Fractal Images". It's true that the disk-marking algorithm does not generate the nice, smooth dwell-bands that we're used to seeing with the standard raster-scan algorithm. The overlapping disks do look rather jarring if displayed in black&white, or with colors that contrast significantly. However, it's possible to extend the disk-marking algorithm a bit, and to generate some _very_ nice colored images from it. There are two aspects to this extension: [1] When iterating points, mark them in one of the following categories: - "In M". - "On the border". Not in M, but calculated distance to the nearest point in M is less than a suitable fraction of a pixel. I've found that border widths ranging from .3 to .001 pixels work well, depending on the complexity of the image. - "Dwell disk". Not in M, calculated distance > border limit. Mark all points in the disk with the dwell count for the point at the center. [Fisher simply marks them "not in M" and doesn't save the dwell count] [2] When displaying points, show points "in M" in black, points "on the border" in a contrasting bright color, and the points in the dwell-disks in a series of smoothly-shaded colors. The calculation process in step [1] takes no longer than the algorithm as described by Yuval Fisher... it simply uses a slightly more complex scheme for marking points in the dwell-disks. The display process in [2] is the critical one... you must choose colors for the dwell-disks that blend so smoothly that the borders between the disks aren't obvious to the eye. If done correctly, this process generates a very striking image... a lacy, highly-detailed tracery stands out against a smoothly-shifting background of colors. >The main advantage is speed - especially when you are not interested about >details in the current magnification, but want to move on to more interesting >details. The other advantage is that the border-of-M algorithm produces a very-high-detail image, which _really_ stands out against the background. I could probably mail out a small image calculated in this way... my program can write 24-bit RGB TIFF files. If there's somebody out there who'd be willing to accept such an image and then make it available for anonymous FTP, please drop me a line... our site isn't on the Internet, so I can't do this myself. If somebody else would be willing to convert it to GIF or a similar, popular format, please speak up! -- 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