A Little Code

Periodicity Logic

The "Mandelbrot Lake" in the center of the M-set images is the traditional bane of plotting programs. It sucks up the most computer time because it always reaches the iteration limit -- and yet the most interesting areas are invariably right at the edge the lake. (See The Mandelbrot Set for a description of the iteration process.)

Thanks to Mark Peterson for pointing out (well, he more like beat us over the head until we paid attention) that the iteration values in the middle of Mandelbrot Lake tend to decay to periodic loops (i.e., Z(n+m) == Z(n), a fact that is pointed out on pages 58-61 of "The Beauty of Fractals"). An intelligent program (like the one he wrote) would check for this periodicity once in a while, recognize that iterations caught in a loop are going to max out, and bail out early.

For speed purposes, the current version of the program turns this checking algorithm on only if the last pixel generated was in the lake. (The checking itself takes a small amount of time, and the pixels on the very edge of the lake tend to decay to periodic loops very slowly, so this compromise turned out to be the fastest generic answer).

Try a full M-set plot with a 1000-iteration maximum with any other program, and then try it on this one for a pretty dramatic proof of the value of periodicity checking.

You can get a visual display of the periodicity effects if you press [O]rbits while plotting. This toggles display of the intermediate iterations during the generation process. It also gives you an idea of how much work your poor little PC is going through for you! If you use this toggle, it's best to disable solid-guessing first using [1] or [2] because in its second pass, solid-guessing bypasses many of the pixel calculations precisely where the orbits are most interesting.

Mark was also responsible for pointing out that 16-bit integer math was good enough for the first few levels of M/J images, where the round-off errors stay well within the area covered by a single pixel. Fractint now uses 16-bit math where applicable, which makes a big difference on non- 32-bit PCs.

Limitations of Integer Math (And How We Cope)

By default, Fractint uses 16-bit and/or 32-bit integer math to generate nearly all its fractal types. The advantage of integer math is speed: this is by far the fastest such plotter that we have ever seen on any PC. The disadvantage is an accuracy limit. Integer math represents numbers like 1.00 as 32-bit integers of the form [1.00 * (2^29)] (approximately a range of 500,000,000) for the Mandelbrot and Julia sets. Other integer fractal types use a bitshift of 24 rather than 29, so 1.0 is stored internally as [1.00 * (2^24)]. This yields accuracy of better than 8 significant digits, and works fine... until the initial values of the calculations on consecutive pixels differ only in the ninth decimal place.

At that point, if Fractint has a floating-point algorithm handy for that particular fractal type (and virtually all of the fractal types have one these days), it will silently switch over to the floating-point algorithm and keep right on going. Fair warning - if you don't have an FPU, the effect is that of a rocket sled hitting a wall of jello, and even if you do, the slowdown is noticeable.

If it has no floating-point algorithm, Fractint does the best it can: it switches to its minimal drawing mode, with adjacent pixels having initial values differing by 1 (really 0.000000002). Attempts to zoom further may result in moving the image around a bit, but won't actually zoom. If you are stuck with an integer algorithm, you can reach minimal mode with your fifth consecutive "maximum zoom", each of which covers about 0.25% of the previous screen. By then your full-screen image is an area less than 1/(10^13)th [~0.0000000000001] the area of the initial screen. (If your image is rotated or stretched very slightly, you can run into the wall of jello as early as the fourth consecutive maximum zoom. Rotating or stretching by larger amounts has less impact on how soon you run into it.)

Think of it this way: at minimal drawing mode, your VGA display would have to have a surface area of over one million square miles just to be able to display the entire M-set using the integer algorithms. Using the floating-point algorithms, your display would have to be big enough to fit the entire solar system out to the orbit of Saturn inside it. So there's a considerable saving on hardware, electricity and desk space involved here. Also, you don't have to take out asteroid insurance. 32 bit integers also limit the largest number which can be stored. This doesn't matter much since numbers outside the supported range (which is between -4 and +4) produce a boring single color. If you try to zoom-out to reduce the entire Mandelbrot set to a speck, or to squeeze it to a pancake, you'll find you can't do so in integer math mode.