Pixel Counting, Mu-Ency at MROB

Pixel Counting

Robert P. Munafo, 2003 Sep 25.

The Pixel Counting method is a method of estimating the area of the Mandelbrot Set and the location of its center of gravity. The technique amounts to little more than drawing the Mandelbrot Set on a very high-resolution grid and noting how many pixels fail to "escape".

Currently (as of fall 2003) the best pixel-counting estimate for the area is 1.506 591 77 +- 0.000 000 08.

The best estimate for the center of gravity is -0.286 768 44 +- 0.000 000 025.

These estimates were produced by this program, a brute-force pixel-counting program that properly handles the sources of error described below. It counted 20 grids each with approximately 262144 by 131072 pixels, with a dwell limit of 134,217,728.

It is not known whether either the area or the center-of-gravity has an exact value computable by a simple formula, but if they do the best candidate formulas appear to be:

sqrt(6 ^. pi - 1) - e ?= 1.5065916514855032852705345... ?? hypothesis

for the area (found by Cyril Soler), and (far less likely):

-((ln(3) - 1/3)^F) ?= -0.2867682633829350268529586... ?? hypothesis

for the center of gravity, where F is the Feigenbaum Constant. This second formula is now considered wrong based on the margin of error in the pixel-counting estimate, but there is also the chance that it is just an error in the pixel-counting.

Pixel Counting is susceptible to the following sources of error:

The dwell limit is too low. Extra pixels that do not belong to the Mandelbrot Set will be counted. This can be fixed by using the infinite dwell limit method, or by using steadily larger dwell limits as you increase the grid size.

Insufficient precision. If using integer math or single-precision floating-point, the roundoff error can throw off the results. IEEE double-precision is more than sufficient for pixel counting.

Each pixel represents a square region of the plane and (generally speaking) a single corner of the square is evaluated. For pixels near the boundary, each pixel will be either an overestimate or an underestimate. The net effect of the overestimates does not necessarily cancel out the net effects of the underestimates. This results from aliasing errors and simple statistical sampling error. In theory it could also result from actual geometric properties of the Mandelbrot Set itself, but no-one has found any such structure which would contribute any significant amount to error in pixel counting (excepting those cases which are simple aliasing errors).

The features which most often cause aliasing errors are R2F(1/2B) (colloquially called the Spike) and R2.C(1/2) (known better as Seahorse Valley). Because the Spike is horizontal and Seahorse Valley is vertical, the grid can be easily aligned in such a way as to cause aliasing errors.

To determine the actual amount of error from aliasing and statistical sampling, it is best to compute a mean and a standard deviation from many seperate runs. In order for the standard deviation to be an accurate measure of error, the runs should all differ from each other by having slightly different grid spacing, being shifted slightly along real and imaginary axes, etc.

Here are the results of a set of such averaged runs. For each grid size, 20 runs were computed and averaged together. The standard deviation measures how much (on average) each run differs from the average. The average itself varys even less from the true area.

grid dwell average size limit area std deviation compute time ----- ------- ------------- ------------- ------------------ 32 8192 1.511 4 0.037 2 904,123 64 16384 1.502 6 0.019 4 3,133,053 128 32768 1.504 84 0.005 68 11,973,129 256 65536 1.506 34 0.002 26 51,835,404 512 131072 1.506 88 0.001 37 225,038,584 1024 262144 1.506 783 0.000 493 971,556,504 2048 524288 1.506 674 0.000 152 4,248,279,832 4096 1048576 1.506 585 0 0.000 074 1 18,687,285,458 8192 2097152 1.506 593 8 0.000 027 5 83,170,102,744 16384 4194304 1.506 588 0 0.000 012 6 368,748,991,052 32768 8388608 1.506 591 54 0.000 004 48 1,416,385,072,113 65536 16777216 1.506 592 30 0.000 001 90 3,728,239,546,503 131072 33554432 1.506 591 734 0.000 000 624 18,173,551,931,685 262144 67108864 1.506 591 77 0.000 000 2

See also Laurent series and Monte Carlo, the other methods of estimating the area of the Mandelbrot Set.

History of Area Estimate Results

See the Area History page.

Acknowledgments

Formula for Mandelbrot area: Cyril Soler.

Area estimate (Pixel counting method): Jay Hill

Old USENET articles: G. A. Edgar (edgar at math ohio-state edu)

From the Mandelbrot Set Glossary and Encyclopedia, by Robert Munafo. Mu-ency index

This work is licensed under a Creative Commons Attribution 2.5 License .
WWW: http://www.mrob.com/
EMail: mrob at mrob com (If you aren't a spambot you can rewrite this yourself)
© 1996-2008 Robert P. Munafo.s.13