Trustworthy Mandelbrot

Mathematically proven images:


100% exterior


100% interior


not yet determined (zone of unknown)

1 References

Images of Julia sets that you can trust. Luiz Henrique de Figueiredo, Diego Nehab, Jorge Stolfi, João Batista S. de Oliveira. 2013.

Rigorous bounds for polynomial Julia sets. Luiz Henrique de Figueiredo, Diego Nehab, Jorge Stolfi, João Batista S. de Oliveira. Journal of Computational Dynamics, 2016, 3(2): 113-137. doi: 10.3934/jcd.2016006

2 Algorithm

The Julia set algorithm works by interval arithmetic and cell mapping graph traversals.

The Mandelbrot set algorithm works by classifying Julia sets: if the critical point 0+0i is exterior/interior to the filled Julia set for the interval of the pixel, then the interval is exterior/interior to the Mandelbrot set.

2.1 Optimisations

  • bit-packed quad tree saves memory (to be investigated if it saves/costs time vs byte-packed quad tree)
  • storing edges as pairs of node ids in two sorted arrays (for binary search) saves memory compared to pointers and linked lists
  • when constructing the graph, use one unique node for all exterior targets
  • speculatively allocate a large graph and fill it in one pass, giving up on overflow, instead of calculaing size first in another pass
  • uint24 for node ids in edge arrays is too slow, uint32 is less frugal space-wise but much faster
  • glibc qsort() may allocate up to 1/4 of physical memory, which is highly undesirable when there are many threads
  • naively-implemented binary most-significant-digit radix sort with uint32 keys is very competitive time-wise with glibc qsort()
  • each thread allocates all its memory up-front, and manages it internally (memory allocation/deallocation mostly follows a stack pattern, the remainder can be solved by moving the top item(s) to another stack at the other end of memory)
  • store Julia sets (compressed) on OOM, to avoid having to recalculate when the concurrency is reduced and more memory is available per thread

3 Images

level 0

level 1

level 2

level 3

level 4

level 5

level 6

level 7

level 8

level 9

level 10

level 11

4 Data

4.1 Dump

0 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11

This represents about 5 days of computation (wall-clock time; mostly with 16 threads active) on an AMD 2700X CPU with 32GB RAM.

4.2 Format

File format:

  • ASCII header contains
    • magic data format identifying string
    • complex interval that the image represents (currently always [-2.75,1.25]+[-2,2]i)
    • number of branch nodes in the quad tree, from which the number of size bits for branch nodes is determined (see TREE_size_size_for_tree_size() in tree.h, it would be better for archival if the actually used size size were stored in the file directly)
    • indication that binary data follows
    • header terminated by \n\f (new line followed by form feed)
  • uncompressed bit-packed binary quad tree follows
    • sequence of 8-bit bytes, bits in little endian order in each byte

    • last byte may have unused trailing bits with arbitrary values

    • 2 bits per node

      • 00 red (zone of unknown)
      • 01 black (100% interior)
      • 10 white (100% exterior)
      • 11 branch (size in units of 2 bits in even number of following bits)
    • following a branch node and its size, the 4 quadrants follow in order (bottom left, bottom right, top left, top right)

    • last two nodes of tree are unused (set to black) when the interval is symmetric about the real axis (redundancy elimination)

5 Area

graph of proven bounds on the area of the Mandelbrot set

Download the data for the plot.

Level 11’s proven bounds on the area of the Mandelbrot set:

\[1.416492462158203125 \le \text{area}(\mathcal{M}) \le 1.84781646728515625\]

6 Source (subdirectory mandelbrot-trustworthy)

git clone
cd fractal-bits/mandelbrot-trustworthy

Source code dependencies:

include graph