luams-3.c

luams version 3 is a UNIX program to measure the area of the Mandelbrot Set by pixel counting. The source code is a single text file, luams-3.c. To get the source code, control-click or right-click this link and select "Save Link As...".

Philosophy and Method

luams uses systematic sampling because it has a far lower variance (error caused by the randomness of selecting pixels) than a pure Monte Carlo method.

In order to get a large number of area measurement "experiments" which can be averaged together to get a mean and standard error, luams uses grids with slightly different pixel spacings:

4 different grids

The picture depicts 4 grids of points using 4 different colors. For each of the grids, an area estimate is based on the number of grid points that fall within the Mandelbrot set, multiplied by the area of a grid square. Only points above the real axis are scanned, and special care is made to compute the effective "height" of the bottom row of grid points (the ones closest to the real axis).

Each of these grids will give a different area estimate, and there is an element of chance that affects the accuracy of the answer.

To Compile

How to compile:

MacOS:
gcc -DMACOSX -O3 -fomit-frame-pointer -ffast-math luams-3.c -lm -o luams

Linux on x86:
gcc -m486 -malign-double -DLINUX -O3 -fomit-frame-pointer -ffast-math luams-3.c -lm -o luams
or, if you wish, replace "-m486" with "-mcpu=pentium" (which will work on most, but not all, non-Intel processors)

If you run Windows, remove it (-: or install Cygwin and use a compile line like that for Linux.

How to run:

./luams

It will create a directory within the current directory called "cache". Within this directory, it will save its work so that if you abort it (or if the machine gets rebooted) it will be able to continue from where it left off. The cache is in the form of a lot of little files, each corresponding to a single pixel-counting run. The files are given names that indicate the number of pixels and dwell limit used for the count in that file. The contents of the file are in binary (not text) so you can't make much use of it except to just delete a file if you want luams-3 to recompute that one.

The output looks like this:

LUAMS-3, 2003 Sep 25 Gridsize 32 (512 pixels) .................... Gridsize 32, itmax 16384 Area 1.511458647 +- 0.037221916 Its: 27240510 Center of gravity -0.2925657871 +- 0.0146405626 Actual: 327542 Total computation time: 0 msec, 0 KFLOPs Gridsize 64 (2048 pixels) .................... Gridsize 64, itmax 32768 Area 1.502262045 +- 0.019566193 Its: 167508374 Center of gravity -0.2876303644 +- 0.0046187808 Actual: 1230747 Total computation time: 40 msec, 215380 KFLOPs

For each gridsize it is giving the width of the grid, total number of pixels in the grid, and iteration limit. The dots "...................." are printed as it completes each individual grid. After it has computed all 20 grids of a given size it prints the statistics.

Area 1.502262045 +- 0.019566193 : The average area of the 20 runs, and the standard error of the mean, which is the standard deviation of the 20 area values divided by sqrt(19).

Center of gravity -0.2876303644 +- 0.0046187808 : Average of the center-of-gravity value, and standard error of the mean.

Its: 167508374 : Number of iterations it would have taken to do the 20 runs, if period detection had not been used.

Actual: 1230747 : Actual number of iterations performed.

215380 KFLOPs : Amount of floating point operations per second your computer was able to achieve while doing the pixel counting.

Utilizing Multiple Processors

luams has an optional -slice parameter that makes it compute only some of the grids for each grid size. The argument of -slice should be a fraction like "1/4" or "0/8", where the numerator is smaller than the denominator.

Normally luams computes 20 grids for each grid size, the 20 grids are numbered 0 through 19. When -slice is used to specify slice N/M, luams only computes the grids whose number is equal to N modulo M. For example, with the parameter -slice 1/4 it computes grids 1, 5, 9, 13 and 17 because these are the only ones whose number is equal to 1 modulo 4.

Here is an example using 4 simultaneous copies of luams on 4 CPU cores:

1. Create 4 shell sessions (typically in 4 separate windows). Use the cd command to put all 4 shells in your luams work directory.

2. Launch 4 copies of luams, one in each shell session, and each with a different slice numerator:

./luams -slice 0/4

./luams -slice 1/4

./luams -slice 2/4

./luams -slice 3/4

3. Allow the 4 luams processes to proceed through whatever gridsize you want. Each will save calculation results in the cache, print its own statistics including area estimate, and so on.

4. After they have completed the desired grid size, stop all of the luams processes.

5. Invoke a single luams without the -slice option.

6. The single luams will read all the cached results produced by the 4 slices, averaging them together to produce a result with full accuracy.

This page was written in the "embarrassingly readable" markup language RHTF, and was last updated on 2012 Feb 08.

s.27