Accuracy of Generated Fractals

Note: I refer to the Mandelbrot set in general as the M-set for short.

When I was writing the post on Rough Mandelbrot Sets I tried out some variations on the rough set. One variation was to measure the generated M-set against a previously calculated master M-set of high precision (100000 iterations of z = z^2 + C). In the image below the master M-set is in white and the generated M-sets are in green (increasing in accuracy):

50 Against MasterHere instead of approximating with tiles I measured the accuracy of the generated sets against the master set by pixel count. Where P = \{ \text{set of all pixels} \} the ratio of P_{master} / P_{generated} produced something that threw me, the generated sets made sudden but periodic jumps in accuracy:

Graph OneLooking at the data I saw the jumps were, very roughly, at multiples of 256. The size of the image being generated was 256 by 256 pixels so I changed it to N by N for N = {120, 360, 680} and the increment was still every ~256. So I’m not really sure why, it might be obvious, if you know tell me in the comments!

I am reminded of the images generated from Fractal Binary and other Complex Bases where large geometric entities can be represented on a plane by iteration through a number system. I’d really like to know what the Mandelbrot Number System is…

Below is a table of the jumps and their iteration index:

Iterations Accuracy measure
255
256
0.241929
0.397073
510
511
0.395135
0.510806
765
766
0.510157
0.579283
1020
1021
0.578861
0.644919
1275
1276
0.644919
0.679819
1530
1531
0.679696
0.718911

Fractal Binary

I have previously talked about Complex Bases but I wanted to look again at Base (-1+i). It’s a really hefty number system so the length of the bit-strings increase very quickly, I’d quite like to know if there is a way to assess Radix Economy for complex and negative bases, so if there are any mathematicians out there who know – Please tell me!

Base (-1+i) to Base 10.Visualising Numbers
Today I wrote a little C++ program to act on Base 2 arithmetic but convert to decimal as if it was Base (-1+i), this meant I could increment through the bits in an ‘ordered’ fashion. The image to the left is the text output of the program, it doesn’t have a very obvious pattern to it – infact the pattern-order we derive from it is somewhat an imposed one. This is because complex numbers do not have a linear order (or Total Order) and I’m trying to list them in a linear manner. They can, on the other hand, be Well-Ordered in correspondence with the natural numbers like we’re doing here.
If we take the real and imaginary values of each number and use them as the x and y co-ordinates (like I did for generating the Mandlebrot Set fractal) then the fractal “Twindragon” appears:

Colour maps of number length in Base (-1+i).

The program I wrote runs through binary numbers starting at 0 colouring the pixel (x=r, y=i) discretely depending on number length. The result shows all Gaussian integers representable by all possible 16,12 and 8 bit complex binary strings in base (-1+i). The colour mapping relates to the position of the Most Significant Bit (essentially the bitstring length). 0 and 1 are both of length one and are the dark blue in the center of the fractal. The 12-bit and 8-bit fractal maps have been zoomed in on to emphases  the self-similarity of the shape.

Colouring the fractals like this is a nice way of showing the distribution of numbers in the complex system but, going back to the math, a number system isn’t useful without arithmetic. Luckily the (-1+i) system is closed under addition, subtraction and multiplication. For addition and multiplication it is the same as normal binary with the difference being in the carry. Below is a table of all possible carry situations:

1+1 = 1100
1+1+1 = 1101
1+1+1+1 = 111010000
1+1+1+1+1 = 111010001
1+1+1+1+1+1 = 111011100
1+1+1+1+1+1+1 = 111011101
1+1+1+1+1+1+1+1 = 111000000

Division in the systems is rather complex, an explination of that and examples of addition/subtraction/multiplication can be found in a short paper called “Arithmetic in Complex Basis” by William Gilbert. The paper also talks about an equivalent to decimal which is base (-3+i) using the digits [0,1,2,3,4,5,6,7,8,9].

Complex Bases

Bellow is Donald Knuth, his most famous work is probably The Art of Computer Programming for which the content won him a Turing Award in 1974. He also came up with the Up Arrow notation used in my posts on Large Numbers and God. Those posts were inspired by one of Knuth’s books, this post was inspired by his number system.

The Quater-Imaginary System
As a student at High School he entered into a science talent search and his submission was the Quater-Imaginary system, or Base 2i. It’s interesting because it uses the digits {0,1,2,3} for representation so it would seem at first glance to be quaternary (Base 4) – but it’s not!

It is actually an imaginary base, as the complex version is (0r±2i). Like the decimal system, quater-imaginary can finitely reperesent all positive real integers -but it can do more- it can finitely represent all positive AND negative real AND imaginary integers without signs (i.e., 3i, -8). Which can be seen in this table:

Base 10 Base 2i Base 10 Base 2i Base 10 Base 2i Base 10 Base 2i
1 1 -1 103 1i 10.2 -1i 0.2
2 2 -2 102 2i 10.0 -2i 1030.0
3 3 -3 101 3i 20.0 -3i 1030.2
4 10300 -4 100 4i 20.0 -4i 1020.0
5 10301 -5 203 5i 30.2 -5i 1020.2

 

 

The Dragon System

The Twindragon also known as the Davis-Knuth dragon!

It’s not offically called that, but the second most known complex system is Base (−1±i) which has an associated fractal shape (twindragon). It uses the numbers {0,1} for representation. It’s a very clean and eligant number system that was created by Walter F. Penney in 1965. As with quater-imaginary, this number system can be used to finitely represnt the Gaussian Integers.

Interestingly the radix starts with a negative number, but this isn’t a problem, negative bases work just aswell as positive ones. Infact in 1957 a Polish computer called BINEG was designed using negabinary!

Base 10 Base (-1±i) Base -2 Base 2
1 1 1 1
2 1100 110 10
3 1101 111 11
4 111010000 100 100
5 111010001 101 101


Base (-1±i√7)/2 and Others

Here the length of the numbers don’t increase monotonically, for example 12(11001100) and 13(11001101) are shorter than their predecessor 11(11100110011) which is the same length as 14(11100010110). It isn’t the only base to hold this attribute but it’s one of the quickest to show it. Source and explination here.

As well as whole-number radix systems it is possible to use fractions and even irrational numbers, one example I go over is Phinary (Base 1.61803…) also known as the Golden Ratio Base. On my Research Page I am looking at a series of systems, starting with the golden ratio, which I call the Metallic Series that can all be used under the same rules.

I find number systems quite interesting and I have started messing around modelling them in different ways, in a previous post (Numeral Automata) I look at them using cellular automata.

Beautifully Complicated

This post is a very brief introduction to the “Ternary Tau” number system.

Before I introduce the new system, let’s go over the basics:
Binary is a number system with radix 2 and two possible symbols {0,1}. Ternery is a number system with radix 3 and three possible symbols {0,1,2}. BALANCED Ternary is a number system with radix 3 and three possible symbols {1,0,1}. Examples:

Binary: {1011}_2 = 1*2^3 + 0*2^2 + 1*2^1 + 1*2^0 = {11}_{10}
Ternary:{120}_3 = 1*3^2 + 2*3^1 + 0*3^0 = {15}_{10}
Balanced Ternary: {1\underline{1}0}_3 = 1*3^2 - 1*3^1 + 0*3^0 = 6_{10}

Ok, got that? good. Let’s quickly touch on the intermediate:
Bergman’s number system (also known as phinary or the golden ratio base) has an irrational radix equal to (1+ √5)/2 or roughly 1.61803… Using the rules of beta expansion, phinary has two possible symbols {0,1}, example:

(Minimal representation only)
Phinary: {100.01}_\varphi = (1*\varphi^2) + (0*\varphi^1) + (0*\varphi^0) + (0*\varphi^{-1}) + (1*\varphi^{-2}) = 3_{10}
Phinary: {1000.1001}_\varphi = (1*\varphi^3) + 0 + 0 + 0 + (1*\varphi^{-1}) + 0 + 0 + (1*\varphi^{-4}) = 5_{10}

Now for the advanced stuff!:
In a paper in 2001 (link below), balanced ternary and phinary were molded into one very impressive number system, using properties already aparant in phinary the system was able to become balanced. With a radix of (1+√5)/2 and three posible symbols {-1,0,1} here is an example of Balanced Phinary:

{10\underline{1}01.0\underline{1}01}_\varphi = (1*\varphi^4) + 0 + (-1*\varphi^2) + 0 + (1*\varphi^0) + 0 + (-1*\varphi^{-2}) + 0 + (1*\varphi^-4) = 5_{10}

An example of the Ternary Tau System:
If the radix is changed to τ = (3+√5)/2 then a more efficient output is given:

1\underline{1}1.\underline{1}1_\tau = (1 * t^2) + (-1 * t^1) + (1 * t^0) + (-1 * t^{-1}) + (1 * t^{-2}) = 5_{10}
Which correspondes to radix e being the most efficient base for a number system.

Along with code redundancy, zero-property, double-property and negative representation the Ternary Tau System has some extremely interesting factors and is by far my favourite number system, I’d even go as far to say it’s more interesting than Donald Knuth’s Quater-Imaginary!

Useful links relating to this post:
All this information was from this paper apart from e (2.71828…) being the most efficient base which I got from the book.
http://en.wikipedia.org/wiki/Numeral_system
http://en.wikipedia.org/wiki/Golden_ratio_base
http://en.wikipedia.org/wiki/Balanced_ternary

U-value Number System

This is a proposal for a number system to be used in the computation/storage of complex numbers, the term U-value comes from the Universal set, in this case it is C but the system uses a lowercase c in notation.

U-value Binary holds { n, i, c, r }, that is:
[Naught = 0, Imaginary = 1i, Complex = (1+1i), Real = 1]

Example 1: irc == 3+5i == 4i + 2 + (1+1i)
Example 2: cnir == 9+10i == (8+8i) + 0 + 2i + 1
Example 3: ccnn == 12+12i == (8+8i) + (4+4i) + 0 + 0

If the system is balanced (negative elements analog to i, c & r) it could be used to represent all Gaussian integers. The letters used have obvious reasons but to a computer it wouldn’t matter and could be re-worked to parrallel binary, for example U-value holds { 00, 01, 11, 10 } or whatever transmutation is best suited. With that set up the three examples look like this:

Example 1: irc == 00011011
Example 2: cnir == 11000110
Example 3: ccnn == 11110000

Although this does half the storage and if the system was balanced three nibbles would be needed (the extra place indicating negative or not 010 = 1, 110 = -1). With a set of rules for arithmatic, This could be useful for modeling fractals in a virtual computer or simulating situations, like in engineering, where imaginary and complex mathematics are key.