Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.2 9/18/84; site bbncc5.UUCP Path: utzoo!linus!philabs!cmcl2!harvard!bbnccv!bbncc5!jr From: jr@bbncc5.UUCP (John Robinson) Newsgroups: net.math Subject: Re: Is the Mandelbrot set a fiction?? Message-ID: <585@bbncc5.UUCP> Date: Mon, 7-Oct-85 12:20:05 EDT Article-I.D.: bbncc5.585 Posted: Mon Oct 7 12:20:05 1985 Date-Received: Wed, 9-Oct-85 06:36:42 EDT References: <418@aero.ARPA> <646@petsd.UUCP> <221@epicen.UUCP> <480@aero.ARPA> Reply-To: jr@bbncc5.UUCP (John Robinson) Organization: Bolt Beranek and Newman, Cambridge, MA Lines: 58 Summary: maybe roundoff error is worse 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