Download an exciting AlmondBread technology demo for DOS that gives you a preview of what speed you can expect from the upcoming AlmondBread 0.3 which will include support for Windows95/NT. Here's the README.

AlmondBread is a program for the X Window System that generates images of the Mandelbrot set. Here are some of its features:

- Fast algorithms, among them an implementation of Simultaneous Orbit Iteration.
- Tcl/Tk user interface.
- Save/Load Fractint-compatible GIF files.
- Load Fractint-style colormap files (
`.MAP`

files). - Shared or own colormap using an allocation scheme similar to that of xv.
- Easy-to-use zoombox function.

News in version 0.22 include:

- Boundary Tracing.
- Improved Unroll Iteration Method.
- experimental Multithreading support (using POSIX 1003.1c threads).
- several bug fixes (e.g. 16bit Visuals work properly now).

AlmondBread is known to work on Linux using XFree86, Solaris, and IRIX. It requires X11 and the aforementioned Tcl/Tk (at least version 7.4/4.0), plus the jstools-package by Jay Sekora.

View a screenshot of AlmondBread in
action, then download AlmondBread
(400k gzipped tar-file from Berlin, Germany).
Outside of Europe, you
might want to use the Canadian
mirror instead.

By popular demand, it is also available as a zip file.

The remainder of this page is an adapted version of the AlmondBread help file.

The Mandelbrot set - or M - was discovered in 1980 by mathematician Benoit B. Mandelbrot. It is considered to be the most complex object mathematics has ever seen [1].

In [2] M is defined as follows: "The Mandelbrot set is the set of all complex numbers c such that iterating z->z²+c does not go to infinity (starting with z=0)".

It can be shown that the sequence diverges if the magnitude of z exceeds 2.

- z := 0, n := 0.
- z := z² + c.
- n := n + 1.
- If |z|<2 and n<N go to 2.

N is the maximum number of iterations you allow (smaller values mean faster execution, larger ones better accuracy). If the iteration loop terminates because n>=N, there is a good chance c lies in M, so you can color p accordingly. If, however, |z|>=2 then p lies outside of M and you can color p according to the number of iterations when z "bailed out", i.e. according to n.

`scan.c`

that comes with AlmondBread.
The idea is the following: For each i consecutive pixels, compute only one. If its color matches that of the previous computed pixel, assume all i are of same color and go on. If not, go back one pixel at a time until it matches the "saved" color (plotting each of those different colored pixels along the way, of course). Now, plot the whole line of unique color defined by the first point of "saved" color and the last.

Obviously, this is very fast for images containing
large areas of a single color, but may err in images with fine
filaments extending through areas of few colors. Thus, it follows the
same policy as Fractint's solid-guessing logic. Its complexity is
O(c·n²), with 1/i<=c<=1. For further details, check out
`interleave.c`

.

It makes use of the Mandelbrot set's connectedness property, which has as a consequence that there cannot be a region of one color inside a rectangle of another color, i.e. once you find that the sides of a rectangular region are of a single color, it is safe to assume the whole rectangle to be of said color (with some margin of error, of course, since strictly speaking one pixel defines a region, not just one point). The procedure used to generate the image is this:

- Compute the border of the region, keeping track of the number of colors used.
- If only one color was used, assume the whole region to be of that color and "blit" it in.
- If more than one color was used, subdivide the image into 2 smaller ones and calculate them recursively (stopping at a certain minimum side length, beyond which use scanning to finish up the image).

There are some details I think are worth elaborating on. First,
AlmondBread's algorithm subdivides at least once to avoid "blitting"
in the initial image. Secondly, it skips computing those edges of the
image that were already done in the previous stage (which is either 3
or all 4 using the "DIN" approach). Thirdly, AlmondBread uses the
"DIN" approach to subdividing the image (I call it that because of the
way paper sizes in the DIN system are related, e.g. DIN A5 is half the
size of DIN A4), which is also known as hv-splitting. This means
simply that subdividing in horizontal or
vertical direction is done in alternating fashion, which has proven to
be very efficient over other methods like 4-way splitting. The
complexity of the Tesseral algorithm is in O(n·log(n)). The code can
be found in `tesseral.c`

.

We scan the whole screen pixel by pixel, keeping an offscreen map of iteration values for each pixel (initially set to all -1s to signal "not done"). If we hit a pixel not done, we start tracing its border going right and keeping the "wall" to our left until we get back to the starting point. For each pixel, the next pixel visited will be computed thus:

- check pixel to left (looking in the current direction, i.e. if the current direction is right, the pixel to the left is the one above it). If it's part of the wall (i.e. offscreen or a different color than the one we're tracking), go to 2. If it's not, it is the next pixel.
- do same for pixel straight ahead. Go there if it's not part of the wall.
- ditto for pixel to the right. If this pixel is also part of the wall, go back one pixel.

When we're back at the starting point we trace the boundary once more. Now, whenever we move up, we plot pixels to the right of the current one until we hit the wall.

This method was inspired by a post on sci.fractals by Maarten Egmond (cp@stack.urc.tue.nl).

The complexity of the
Boundary Tracing algorithm is in O(n^{2}). The code can be
found in
`boundary.c`

.

As you may recall from section The Mandelbrot Set, calculating M involves an iterative process, which means on successive iterations one point is mapped onto another one. Now, if we look at not only one point but a whole set of points, say a rectangle, these points get mapped onto a different set of points in the complex plane. If this (iterated) set of points is still a rectangle, we can make the reasonable assumption that in order to obtain the iterated value for a point inside the original rectangle all we have to do is a linear interpolation, i.e. determine where the point in the original rectangle would be in the new, iterated rectangle if we had merely "resized" it and moved it to the new location (which in effect is what we have done by iterating). To put it in other words, if point x is in the middle of the rectangle before iterating it will be in the middle of the iterated rectangle also.

The problem is that for a given rectangle the iterated point set is very rarely a perfect rectangle. The approach used by AlmondBread involves a polynomial interpolation of 2nd degree (using Newton interpolation). For every rectangle we have 9 key points plus four test points. All points are iterated and the test points are interpolated. If the ratio of iterated to interpolated test points is greater than an allowed margin, we subdivide, proceeding in a fashion similar to the Tesseral algorithm (using a 4-way split, though). Otherwise, we do the iterating and interpolating over until we have to split or maxiter is reached, in which case we simply fill the rectangle and exit. This may sound trivial at first, but the whole interpolating stuff can get pretty confusing after a while, particularly when you have to interpolate certain points and don't know which key points to use (just take a look at the subdividing part in the code), but this is mainly due to my quick'n'dirty implementation tactics.

SOI does a very good job on images that have a high number of average iterations, typically very deep zooms that take a long time using other algorithms such as Interleave. The following image is a very deep zoom that took over 2 hours using Fractint under DOS on a 486DX-33. It took about 4 minutes using AlmondBread under Linux on the same machine.

Load the image into Fractint and check out yourself how long this image takes to calculate (Download the Parameter file if you just want to calculate the image).

SOI does not do as good a job on
low-magnification images, because unlike Interleave, for example, SOI
has a large organizational overhead. There are a few tricks, however,
which can make SOI as fast or even faster on low-magnificaction
images. The main problem with low-magnification images is that the
number of simultaneous iterations is very small and you have to
subdivide after very few iterations. Therefore, AlmondBread has a
`minprogress` variable, which controls the minimum number of
iterations
required to allow subdividing. If this number is not
reached, Interleave scanning is employed.

A word of warning is necessary at this
point. The SOI in AlmondBread is far from perfect. With certain images
you may notice severe distortions caused by a failure of the tolerance
code. You can then lower the value of the variable
`tolerance` (possibly
from 0.1 to 0.05). Of course, this is not acceptable, but up till now,
I have not found a fool-proof way of detecting distortion (I would
greatly appreciate any input you might have on this or any other
aspect of SOI. Plus, let me know if you have implemented SOI or a
similar method yourself). The complexity of SOI cannot be easily
compared to previous methods, since it does not depend on the side
length of the image. The code for SOI can be found in `soi.c`

.

`conventional.h`

.
- Periodicity checking
- Recall that a
point is in M if during iteration its magnitude does not exceed
bailout. We know that this is the case for a certain point
z
_{0}:=c if we discover that z_{i+p}=z_{i}, i.e. the iteration has entered a cycle. This sounds easy enough, but implementing it proves rather cumbersome since we do not know in advance what p is and saving every z_{i}and testing it against all its predecessors would take too long. Therefore AlmondBread saves only every "maxiter/8"th z, exiting if |z-"saved z"|<pixelsize. This is nowhere near optimal, but suffices to catch a lot of "offenders". If you have a better method, please let me know. - Cardioid checking
- If you take a look a the Mandelbrot set, you will notice that most of it is made up of a number of discs that are attached to an object that looks like a sliced apple, which is called a cardioid (presumably because it looks a little like a heart, too). With a couple of operations we can check whether a given point lies inside one of those objects and exit if it does (at least for the main cardioid, and the 3 biggest discs attached to it). For example, if z=(r,i) satisfies (1/4)²<=(r+1)²+i², it lies inside the disc at (-1,0) with radius 1/4. Most of the cardioid checking code in AlmondBread was taken from a post by Todd S. Lehman (toddl@county.lmt.mn.org) on sci.fractals. Also, check out "The Beauty of Fractals" (p.56).

`optimized.h`

.
```
do
{
im=(im+im)*re+cim;
re=rq-iq+cre;
rq=re*re;
iq=im*im;
/* maybe some periodicity checking here */
} while (i++<=maxiter && rq+iq<bailout);
```

As you can see, this process involves 3 floating point multiplies. We
would be able to eliminate one of them if we didn't have to check for
bailout on each iteration. And that's exactly what we do: We unroll
the loop and check for the bound only every n-th time.
```
do
{
/* do this n times */
i1 = (im+im)*re+cim;
r1 = (re+im)*(re-im)+cre;
/* now check the bound once */
rq = rn*rn;
iq = in*in;
if(rq+iq>bailout) { /* determine correct iter and return */ }
i+=n;
} while (i<maxiter);
```

In addition to saving one multiplication (which in fact isn't such a big savings on modern processors such as the Pentium) the comparison and looping overhead can be avoided. This turns out to be an even greater advantage, especially for Intel processors where floating point comparisons are very costly.

There are a couple of problems, though. First of all, we are running the risk of doing too many iterations if we don't check the bound each time, but if maxiter is large compared to the number of unrolled iterations the time-savings outweigh the overhead.

Secondly, the magnitude of z can get very large after it surpasses bailout, generating a floating-point exception. Therefore, AlmondBread unrolls only to a depth of eight, which seems to be safe for IEEE 754 doubles.

Thirdly, it has to be determined when exactly the
bailout value was exceeded in order to color the corresponding pixel
correctly. Nick Haines (nickh@cmu.edu) suggested doing an "exponent
correction hack", which uses the exponent of the magnitude of
z to determine the correct iteration number. It is based on the
observation that after |z| surpasses
bailout, its exponent is doubled on each consecutive iteration. However,
this works only for
bailout values larger than 4.
The code is in
`unroll.h`

.

`pot:=maxcolor-slope*log(|z`

,
_{n}|)/2^{n}

where `maxcolor`

is the maximum value for `pot`

. The variable
`slope`

affects
the width of the color bands. z_{n} is the value of z
at the end of iteration, i.e. the value it holds when bailout is
reached, after n iterations. Values less than 1 are "truncated" to
1.

`angle:=(atan2(i,r)/(2*pi)+0.5)*arity`

.

This will yield a value in the range 0-`arity`

.
The `arity`

parameter determines how many
segments the circle of possible angle values is divided into, i.e. if
`arity`

is 2, p will be colored according to whether the
imaginary part
of z_{n} is positive or negative. Again, try [1] or [3] for an
in-depth
explanation. `arity`

256 and a nicely shaded colormap gives beautiful pictures.

- [1]
- Peitgen, H.-O., Saupe, D., et al.,
*The Science of Fractal Images*. Springer Verlag, Berlin, 1988. - [2]
- Taylor, Michael C., et al., The sci.fractals FAQ.
- [3]
- Peitgen, H.-O., Richter, P.H.,
*The Beauty of Fractals*. Springer Verlag, Berlin, 1986. - [4]
- Giffin, Noel, The Spanky Fractal Database.

- Mu-Ency - The Encyclopedia of the Mandelbrot Set by Robert Munafo.
- Although a little chaotic (but that's what fractals are about, right), this has some very good information on the Mandelbrot set and how to speed up its generation.
- Fractal Geometry of the Mandelbrot Set by Robert L. Devaney.
- This explains some of the properties of the Mandelbrot set in detail.

Michael R. Ganss (rms@cs.tu-berlin.de) Last modified: Thu Apr 18 15:01:44 MEST 2002

© 1997 Michael R. Ganss. All Rights Reserved.

URL: http://www.cs.tu-berlin.de/~rms/AlmondBread/

For custom software development check out my company O&O Services.

Für individuelle Softwareentwicklung schauen Sie sich bitte meine Firma O&O Services an.

Take a look at the Ganss family homepage.

Werfen Sie einen Blick auf die Homepage der Familie Ganß.