sinclair@aero.ARPA (William S. Sinclair) (09/09/85)
I have been looking at the error propagation properties of the Mandelbrot formula,
e.g. z=z*z+c. The error grows without bound in a very small number of iterations. The implication on a finite precision machine is that for the exact same
number on two different machines, you are going to get different results.
In fact, on the SAME machine, using two different precisions, the results will
be different. I have verified this on the CDC Cyber 176.
The gist of this is: For points near the Mandelbrol set boundary, without an infinite
precision machine, you can't determine whether or not the point really does belong in the set.
Bill Sinclair 213/647-1753
P.S. I tried integer and fractional arithmetic, but in both cases,
the numbers grow without bound, and have to truncated at some point.sinclair@aero.ARPA (William S. Sinclair) (09/11/85)
Someone pointed out to me that the Mandelbrot set is well defined, although on
a finite-precision machine it might be impossible to do the iterative
process to establish that a number is IN the set. Of course, there are many examples
of numbers NOT in the set. Rational arithmetic isn't much help; the numbers in
the fractions get big in a BIG hurry. To see what I mean, take the complex
number (1/3,0.). How do you show that it is in the set?
On a more practical note, is there a way to standardize the iterative process
such that all machines give the same answer for a number which can be expressed
exactly on those machines, for example (1/4,1/4)?
Bill Sinclaircjh@petsd.UUCP (Chris Henrich) (09/17/85)
[] In article <418@aero.ARPA> sinclair@aero.UUCP (William S. Sinclair) writes: >I have been looking at the error propagation properties of the Mandelbrot >formula, e.g. z=z*z+c. The error grows without bound in a very small >number of iterations. The implication on a finite precision machine >is that for the exact same number on two different machines, you are >going to get different results. >... >For points near the Mandelbrot set boundary, >without an infinite precision machine, you can't determine whether or >not the point really does belong in the set. Does the difference affect the overall appearance of the Mandelbrot set? In other words, are the "scrollwork" effects so dramatically displayed in Dewdeney's article in _Scientific_American_ artifacts? By the way, I think that article was mistaken in stating that if the value of z ever got to where |z| > 2, it was sure to go to "infinity". It is fairly easy to show that if |z| > |c| + 1 then the sequence will go to infinity. Regards, Chris -- Full-Name: Christopher J. Henrich UUCP: ..!(cornell | ariel | ukc | houxz)!vax135!petsd!cjh US Mail: MS 313; Perkin-Elmer; 106 Apple St; Tinton Falls, NJ 07724 Phone: (201) 758-7288
putnam@steinmetz.UUCP (jefu) (09/19/85)
Some questions on the mandelbrot set -- but not necessarily having anything
to do with it being a fiction.
The Sci. Am. article mentioned that there is an 'amazing theorem' that the
Mandelbrot set is connected. I dont expect to be able to do this myself,
but was wondering if anyone would like to sketch out the basic ideas for
the proof.
Is the complement of the set connected (im pretty sure that the
answer to this one is yes, but again, wouldnt know how to prove it
without a (or many) hint)?
Is there some sort of minimal nice closed bounding curve for the set?
(nice meaning continuous and derivatives of all orders existing)
(minimal meaning minimum area in the curve, but not in the set) ?
Lacking the above, what would a minimum bounding convex polygon look like?
(That is, what are the extreme points)
What is the area of the set? (I would guess that it is measurable.)
Has anyone tried looking at the 3-d surface generated by iterating the
process until the |z| > m (m not necessarily 2) and drawing this?
--
O -- jefu
tell me all about -- UUCP: edison!steinmetz!putnam
Anna Livia! I want to hear all.... -- ARPA: putnam@kbsvax.decnet@GE-CRDcjh@petsd.UUCP (Chris Henrich) (09/20/85)
[] In article <273@steinmetz.UUCP> putnam@kbsvax.UUCP (jefu) writes: >Some questions on the mandelbrot set -- but not necessarily having >anything to do with it being a fiction. > >The Sci. Am. article mentioned that there is an 'amazing theorem' >that the Mandelbrot set is connected. I don't expect to be able to >do this myself, but was wondering if anyone would like to sketch out >the basic ideas for>the proof. I have seen discussions of the proof. Unfortunately the heavy work on this circle of problems is mostly published in French. And, needless to say, my references are not where my terminal is. A good starting point (with decent graphics) is an article in the _Mathematical_Intelligencer_ , sometime in 1984, on "Julia" sets. There is also a survey article in the _Bulletin_of_the_American_Mathematical_Society_, also early 1984, on iteration and Julia sets. Further references can be tracked down there. The connectedness theorem of Hubbard and Douady can be chased down through a survey paper by Douady, in French of course, in the French periodical _Asterisque_. (Exact citation is found in the _Math_Intelligencer_ article.) The proof is sketched in a note in _Comptes_Rendus_. The fact that it's in French is not the only barrier to understanding it. The math is *heavy.* The gist seems to be a frightfully ingenious construction of an analytic function which maps the disc onto the complement of the Mandelbrot set. This implies that the Mandelbrot set, and its complement, are both connected. > >Is the complement of the set connected (im pretty sure that the >answer to this one is yes, but again, wouldnt know how to prove it >without a (or many) hint)? > >Is there some sort of minimal nice closed bounding curve for the set? >(nice meaning continuous and derivatives of all orders existing) >(minimal meaning minimum area in the curve, but not in the set) ? Well, imagine you were packaging Mandelbrot sets for sale in the corner drugstore. You would probably enclose them in a piece of plastic, to be mounted on a colorfully printed cardboard backing. Now, that plastic can be "shrink-wrapped" to fit the Mandelbrot set. The more you shrink the wrapper to fit the Mandelbrot set, the less air is left in your package, but the more irregular and wrinkly is the packaging. How far you go is up to you. > Regards, Chris -- Full-Name: Christopher J. Henrich UUCP: ..!(cornell | ariel | ukc | houxz)!vax135!petsd!cjh US Mail: MS 313; Perkin-Elmer; 106 Apple St; Tinton Falls, NJ 07724 Phone: (201) 758-7288
jbuck@epicen.UUCP (Joe Buck) (09/25/85)
> From: cjh@petsd.UUCP (Chris Henrich) > Date: 17 Sep 85 14:26:31 GMT > > By the way, I think that article was mistaken in stating > that if the value of z ever got to where |z| > 2, it was sure > to go to "infinity". It is fairly easy to show that if > |z| > |c| + 1 > then the sequence will go to infinity. I don't understand why you think discovering a different bound invalidates the one given in Scientific American. To show the result given there, first prove that the set is bounded by the circle |c| = 2. To show this, study the sequence z'=z*z+c for |c|>2; it grows without bound since |c^2|=|c|^2 is at least 4 and c*2+c must have a strictly larger magnitude than c. The slowest growth is when c is real and negative; in fact, it's not hard to show that all real, negative c's in [-2,0] are in the set. It's only slightly trickier to see that no point on the positive real axis is in the set (each term is at least c^2 greater in magnitude than the previous term, so the sequence goes to infinity). Next, assuming that |c|<2, it's straightforward to see that once |z|>2, the sequence grows without bound. -- Joe Buck | Entropic Processing, Inc. UUCP: {ucbvax,ihnp4}!dual!epicen!jbuck | 10011 N. Foothill Blvd. ARPA: dual!epicen!jbuck@BERKELEY.ARPA | Cupertino, CA 95014
sinclair@aero.ARPA (William S. Sinclair) (09/28/85)
Dear Joe;
I'm the one that started this Mandelbrot discussion. The reason I wondered
about the reality of it is for certain numbers near the boundary, it is
near impossible on a finite machine to carry thru the iterations without
the error propagation overwhelming the result. Of course, there are isolated
cases where you can prove a number is within the set, and it is easy to
show that certain numbers are outside the set if the number of iterations is
small enough. The really tough ones are those that require more than 20 or so
iterations, becuase by then the error has complely swamped the result.
I did work out a way where you can generate a large number of numbers in the
set when given just a few--but that doesn't help establish whether a number
picked at random is in or out of the set. The way it works is: Suppose a number
c1 is in the set. Then the number c2=c1**2+c1 is also in the set, and likewise
the 2 roots of this equation:
c3**2+c3=c1
are also in the set. The same inference can be made for numbers NOT in the set.
This gives you a way, by induction, to get a very large number of numbers either
in or out of the set, by starting from one or two numbers. Play with this, see if
you agree. This is interesting, but doesn't help with the pixel map a whole
lot.
Bill Sinclair
P.S. To get a good idea, take a complex number like (-1/4,1/4) and do the
iterations using *exact* arithmetic. You'll see how quickly you need to
start rounding off the operations.tet@uvaee.UUCP (Thomas E. Tkacik) (10/02/85)
>I'm the one that started this Mandelbrot discussion. The reason I wondered >about the reality of it is for certain numbers near the boundary, it is >near impossible on a finite machine to carry thru the iterations without >the error propagation overwhelming the result. Of course, there are isolated >cases where you can prove a number is within the set, and it is easy to >show that certain numbers are outside the set if the number of iterations is >small enough. The really tough ones are those that require more than 20 or so >iterations, becuase by then the error has complely swamped the result. > I have written a program to generate Mandelbrot's set, and have used it magnify some areas by a linear factor of about 100,000. The results have been spectacular. It has been obvious by just looking at the resulting pictures that roundoff errors have not completely swamped the results. To be sure, there are probably a few mistaken points in the pictures, but nothing extreme. To generate these pictures, I had to increase the iterations in some of the more extreme cases to 2048. I did expect lots of roundoff errors, so I used double precision (on a VAX that's 64 bits). > >I did work out a way where you can generate a large number of numbers in the >set when given just a few--but that doesn't help establish whether a number >picked at random is in or out of the set. The way it works is: Suppose a number >c1 is in the set. Then the number c2=c1**2+c1 is also in the set, and likewise > According to what you said above, this should also only work for the first 20 or so iterations before roundoff errors swamp the result. This would not generate many points, and would give points outside any region of intrest, so I think we are stuck doing this one pixel at a time. I agree that roundoff error will set a limit to what can be seen in the set, but I think that is a limit that has not yet been reached, (at least by me :-) .) Has anyone else generated pictures with very high magnifications, and/or many iterations. I would like to hear of your results. Tom Tkacik ...!decvax!mcnc!ncsu!uvacs!uvaee!tet
jr@bbncc5.UUCP (John Robinson) (10/07/85)
I am coming into this discussion late, so pardon me if this ground has been covered already. Naive analysis says that the roundoff error (assuming roundoff rather than truncation is used) is never more than .5 times the least significant bit's value. For truncation, the error is bounded by 1.0 times the least significant bit (worst case). The operation of multiplication results in errored bits only in positions at or below the least significant bit, and I think the magnitude is no greater. Addition, however, can cause addition of the error at the least significant bit. So now the error magnitude doubles (worst case) for each iteration. So n bits or precision can be used up by errors in 2n iterations worst case. This seems to say that a 64-bit mantissa is good for 128 iterations. The real trouble, I think, comes in at the completion test. It is a comparison with a constant of infinite precision. Any error anywhere can cause the wrong answer. So I guess the algorithm should keep track of its worst-case error estimate and, for points where the end test is within the error, mark the point as uncertain. This would probably make for far uglier pictures - everything would be colored uncertain for most zooms. But you still might get nice fringes from "uncertain after 1 iteration", "uncertain after 2", etc. I think there is probably a way to make the zoomed-in pictures less sensitive to roundoff problems than a naive approach. Suppose (without loss of generality) that the lower left corner point can be expressed with the smallest number of bits of precision in the picture. Then every other point can be found by computing the difference at each iteration from the corner point. The differences will be near 0, at least at first, thus their error terms should grow more slowly than if they had been represented in absolute coordinates from the start. I don't know if this increases the useful iteration count by more than a few, however. (color me lazy). This technique could also be applied recursively as you zoom in. Remember the sequence for each point (ugh! a lot of memory!). When zooming in, just copy the sequences for the points still in the picture in the new magniification. Use the difference technique from the old points to fill in the new points. Finally, this is how the entire picture should be generated. First use points (+- 2n, +- 2n). Then (+- n, +- n). And so on, filling in intermediate points up to the magnification of the initial picture. At first, color squares of 2n with the first answers. Then subdivide them as the answers come in. Could be fun in real time until it slows down for the last few exponents. Here at BBN, we have started generating Mandelbrot pictures using our (ARPA's, really) Butterfly multiprocessor (128 M68000's). Dewdney's Mandelbrot algorithm is ideal for parallelizing, of course. It generates a 400x400 picture in something like 10 seconds. Copying it over an Ethernet to a Lisp Machine for display, unfortunately, takes minutes. I don't know the details of this, but I expect it can be made zippier. I will look into what has been done more, in case anyone's interested (I am at least). /jr
allan@alice.UucP (Allan Wilks) (10/09/85)
> ... to show that all real, negative c's in [-2,0] are in the set. It's only > slightly trickier to see that no point on the positive real axis is in > the set (each term is at least c^2 greater in magnitude than the previous > term, so the sequence goes to infinity). The Mandelbrot set intersects the real axis in [-2,0.25]. 0 is always attracted to a fixed point for c in [-0.75,0.25].