mathr / blog / #

Automatically finding external angles

Here's a view in the Mandelbrot set, it has coordinates:

real: -1.257107069309473385006
imag: 3.792595459480247177508e-1
radius: 1.6858739404357617e-07

Using programs I wrote some time ago, it's possible to find the period and nucleus of the cardioid:

$ ./mandelbrot_box_period \
  -1.257107069309473385006 3.792595459480247177508e-1 \
  1.6858739404357617e-07 1000
37
$ ./mandelbrot_nucleus 100 \
  -1.257107069309473385006 3.792595459480247177508e-1 37 1000
-1.2571070728359768903025167466887 3.7925954601914527110428094866064e-1

And it's also possible to find its atom domain size estimate. I ported the algorithm there from native C99 types to arbitrary precision MPFR and added it to my slowly-growing library. Using this, we can calculate a few external rays out from near the edge of the atom domain of the given nucleus and period, to calculate the distinct ordered external angle pair landing at the root of the nucleus' component. Asymptotic complexitiy is O(period^2) (because tracing an external ray out is O(dwell^2) and the maxiter for the probe points is limited to a multiple of the period). There'll certainly be enough bits in each traced ray by the definition of atom domains.

I wrote an implementation of this algorithm, here's the output:

$ ./mandelbrot_external_angles 53 \
  -1.2571070728359768903025167466887 \
  3.7925954601914527110428094866064e-1 \
  37
.(0101101011010110101101011010110101101)
.(0110001100011000110001100011000110010)

The implementation first calculates the dwell at 64 probe points in a circle near the atom domain edge, then chooses the lowest and calculates the angle by tracing an external ray out to get a bitstring of length dwell, which is truncated to length period and made periodic. It repeats choosing the next lowest, until it finds a different angle to the first one. This is then the desired ray pair. In practice it needs to trace only a few of the 64 probe points, typically 5 or less. Here's an image with all the probe points traced, with the chosen ones in red. The view radius is 3.52e-6:

Sanity check: tracing those rays inwards do land on the desired component:

In the image below the correct rays are green, the rays differing in the last periodic bit are red, and the rays in blue are in between (the rays which differ in the 38th bit such that any ray to one side would be good and the other side bad - but I'm not 100% sure I calculated them correctly):

Anyway, it's clear that the red rays would be disasterous (they're way out - the view in this image has a radius of 4.24e-4 which is huge compared to the initial view), and hopefully clear that all the probe rays are so much closer to the desired rays that it's not possible to get a wrong result easily.

Caveat. I haven't tried this for child bulbs yet, but I suspect it might fail. In any case, it might be quicker to modify the algorithm: use shape estimates to check if it's a child bulb, if it's a child bulb then trace the internal ray to its root and find the internal angle at the bond with its parent. Repeat until finding a cardioid, perform the original algorithm as described, then iteratively use the well known tuning algorithm to find the desired angles of the descendant bulb.

Appendix. Here are the bitstrings of all the probes, sorted. I inserted spaces every 37 bits, and hopefully it's easy to see that there are only two distinct values for the first 37 bits (and the second set of 37 bits has a strong pattern too - either resembling the first 37 bits, or the first 37 bits of the other set of bitstrings):

0101101011010110101101011010110101101 0101101011010110101101011010110101100 101
0101101011010110101101011010110101101 0101101011010110101101011010110101100 10101000
0101101011010110101101011010110101101 0101101011010110101101011010110101100 11
0101101011010110101101011010110101101 0101101011010110101101011010110101101 01
0101101011010110101101011010110101101 0101101011010110101101011010110101101 011
0101101011010110101101011010110101101 0101101011010110101101011010110101101 011
0101101011010110101101011010110101101 0101101011010110101101011010110101101 0110101
0101101011010110101101011010110101101 0101101011010110101101011010110101101 01101010
0101101011010110101101011010110101101 0101101011010110101101011010110101101 01101010
0101101011010110101101011010110101101 0101101011010110101101011010110101101 0110101000
0101101011010110101101011010110101101 0101101011010110101101011010110101101 01101010010100
0101101011010110101101011010110101101 0101101011010110101101011010110101101 011011
0101101011010110101101011010110101101 0101101011010110101101011010110101101 0110110
0101101011010110101101011010110101101 0101101011010110101101011010110101101 0111
0101101011010110101101011010110101101 0101101011010110101101011010110101101 011101
0101101011010110101101011010110101101 0110001100011000110001100011000110001 1
0101101011010110101101011010110101101 0110001100011000110001100011000110001 10
0101101011010110101101011010110101101 0110001100011000110001100011000110001 1001
0101101011010110101101011010110101101 0110001100011000110001100011000110001 100101
0101101011010110101101011010110101101 0110001100011000110001100011000110001 10010101
0101101011010110101101011010110101101 0110001100011000110001100011000110001 10010101
0101101011010110101101011010110101101 0110001100011000110001100011000110001 1001010101
0101101011010110101101011010110101101 0110001100011000110001100011000110001 10010101010
0101101011010110101101011010110101101 0110001100011000110001100011000110001 10010101010111
0101101011010110101101011010110101101 0110001100011000110001100011000110001 1001011
0101101011010110101101011010110101101 0110001100011000110001100011000110001 10011
0101101011010110101101011010110101101 0110001100011000110001100011000110001 101
0101101011010110101101011010110101101 0110001100011000110001100011000110010 0
0101101011010110101101011010110101101 0110001100011000110001100011000110010 1
0101101011010110101101011010110101101 0110001100011000110001100011000110011 00
0101101011010110101101011010110101101 0110001100011000110001100011000110011 000111
0101101011010110101101011010110101101 0110001100011000110001100011001001011 00101001
0110001100011000110001100011000110010 0101101011010110101101011010110101100 101
0110001100011000110001100011000110010 0101101011010110101101011010110101100 101011
0110001100011000110001100011000110010 0101101011010110101101011010110101100 11
0110001100011000110001100011000110010 0101101011010110101101011010110101101 01
0110001100011000110001100011000110010 0101101011010110101101011010110101101 011
0110001100011000110001100011000110010 0101101011010110101101011010110101101 011
0110001100011000110001100011000110010 0101101011010110101101011010110101101 0110101
0110001100011000110001100011000110010 0101101011010110101101011010110101101 01101010
0110001100011000110001100011000110010 0101101011010110101101011010110101101 01101010
0110001100011000110001100011000110010 0101101011010110101101011010110101101 011010100
0110001100011000110001100011000110010 0101101011010110101101011010110101101 011010100100
0110001100011000110001100011000110010 0101101011010110101101011010110101101 011011
0110001100011000110001100011000110010 0101101011010110101101011010110101101 0110110
0110001100011000110001100011000110010 0101101011010110101101011010110101101 0111
0110001100011000110001100011000110010 0101101011010110101101011010110101101 01110
0110001100011000110001100011000110010 0110001100011000110001100011000110001 1
0110001100011000110001100011000110010 0110001100011000110001100011000110001 10
0110001100011000110001100011000110010 0110001100011000110001100011000110001 100
0110001100011000110001100011000110010 0110001100011000110001100011000110001 1001
0110001100011000110001100011000110010 0110001100011000110001100011000110001 10010
0110001100011000110001100011000110010 0110001100011000110001100011000110001 100101
0110001100011000110001100011000110010 0110001100011000110001100011000110001 1001010
0110001100011000110001100011000110010 0110001100011000110001100011000110001 10010101
0110001100011000110001100011000110010 0110001100011000110001100011000110001 100101010
0110001100011000110001100011000110010 0110001100011000110001100011000110001 1001010100
0110001100011000110001100011000110010 0110001100011000110001100011000110001 10010101010
0110001100011000110001100011000110010 0110001100011000110001100011000110001 100101010101101
0110001100011000110001100011000110010 0110001100011000110001100011000110010
0110001100011000110001100011000110010 0110001100011000110001100011000110010 0
0110001100011000110001100011000110010 0110001100011000110001100011000110011 0010101101
0110001100011000110001100011000110010 0110001100011000110001100011000110011 1
0110001100011000110001100011000110010 0110001100011000110001100011001001011 00100

Here's some hacky script that I used to generate the images - most of it is commented out as running the whole thing would clobber files or recalculate needlessly. The real code you want to get is in the maximus/book repository on gitorious book repository on mathr.co.uk :

git clone http://code.mathr.co.uk/book.git