Mandelbrot
Wednesday, 1. July 2009, 23:22:05
I was busy with other projects and really wanted to quench my thirst for programming due to withdrawal symptoms. I needed something quick, but fun. So Mandelbrot it was. I think the last time I programmed a Mandelbrot set was way back in my University days when computers available there went from 8088 to Pentiums and video cards went from CGA to SVGA. The very first Mandelbrot set I did at University was in CGA with a monochrome monitor in a computer lab for first year students. (edit: I should add that I wrote this in Modula-2, awful language that it is.) These machines were ancient. I also wrote a program to compute Julia sets. Most people had no clue that these machine could do graphics at all. The reaction from others in the computer room was quite entertaining because normally, the ambiance in there is somewhat like the movie Das Boot. Tons of people in a large, but confined space. So when someone did something to change the monotony of working on assignments, it was often very motivating since people wanted to know how it worked. Oh yeah, back then, it was direct access to the video card. No fancy API's.
The Mandelbrot set itself is VERY easy to program. All of the coordinates are found in a grid from (-2,-2) to (2,2). Most of the fun stuff is in the grid (-2,-1) to (1,1). Here is one image I did (in C++). It only uses 50 iterations, so the border areas aren't very well defined. I could have made my program faster, but this was only to whet my appetite with a couple hours of programming trying out different gradients and other things.
(click on image for larger version)
One thing I like about this image is that it uses a continuous color gradient. I found this on wikipedia.
v = n + (ln(2 ln(B)) - ln(ln(|zn|)))/ln(P)
B is the escape threshold and has to be larger than 2.0, but works better if it's larger than 4.0. n is the number of iterations and zn is the last z value computed. P should be left to 2.0 since P is set to the power of the equation. Since z is squared, then P = 2.0. v will give the same iteration number, but with an added fraction so that you have a smooth transition between colors.
This is the Mandelbrot set equation.
zn = zn-12 + C
C is the coordinate of the pixel. Set z to 0.0 to start things off.
To determine the color of the pixel, you continue squaring until the modulus is larger than 2.0 (or 4.0 if you use the continuous color function). The number of iterations is what you use as an index in a color gradient.
Many coordinates will never go larger than 2.0. To detect these, you can use the same technique used to detect circular linked lists. One index is incremented by one step and another index is incremented by two steps. For the Mandelbrot set, you use two z values. One value is squared once. And the other value is squared twice. If they are equal up to a certain amount of precision, then you've found a loop and can set the pixel to black. The more you zoom in, the more precision you need in the comparison.
There are plenty of other things you can do to speed things up. Each of them is a lot of fun to implement. For example, many Mandelbrot sets are computed a small section at a time. This is done because operating on a smaller amount of data at a time means that you don't pollute the cache as much. You could also implement the Mandelbrot set as a pixel shader on your video card if you have support for floating point textures. You could use SSE registers to compute four (or more) pixels at a time.
For very large images, it's often better to compute the image in sections regardless of the optimization benefits. The reason is memory usage. By using a small amount of memory for each segment, you don't need to store variables for the entire image. It's also better for parallel processing where you can send each segment to a different core.
Anyways, the point is that whenever I need something to get me back into the swing of things, I pick something small, fun and easy to do. And having something graphical is a bonus since you are rewarded for your work unlike most programming tasks. And as with anything graphical, most of the time is usually spent setting up the API calls so that you can display your images. With my Project V GUI, I could skip that step almost completely by using an Image GUI component. I just compute the pixels and transfer the data to the image texture. The GUI takes care of displaying it. The really fun part is that since the display is a virtual canvas, I can show many different images at once and scroll around to see each one. I'll keep Julia sets for a later date just in case I need another quick project.
Here are some more images. I used a gradient to black for the borders to make them look smoother. (Again, click on images to get larger versions)
10 iterations
20 iterations
30 iterations
40 iterations
50 iterations
60 iterations (different size, same gradient but scaled a little differently)
(-0.17225,0.66038683) to (-0.17115,0.66112017)
90, 100 iterations
110, 120 iterations
130, 140 iterations
150, 160 iterations
170, 180 iterations
200, 220 iterations
250, 300 iterations
350, 400 iterations
450, 500 iterations
WIDGETIZE
Anonymous # 14. July 2009, 15:12
Hi Vorlath! I found this link over at EP. I took a look in the user list and found this link. I hope you don't mind.
personally I was suprised how interesting this was. I've read the vigenere decoding and cantor set discussion, all to complicated for me at this moment, and I didn't quite follow how it would be possible to use a probabilistic letter decoding.... yeah,about there, I came to a halt, I need more time with that I guess. It seems too easy?
Anyhow, these Mandelbrot sets in the end of your post, not only would make great gifs, but they also display a very distinct property. namely that the higher the definition, the more they invade another area. And maybe cantor set and all you wrote its all cooked up in my mind, but I was thinking about solid and void, and how to deal with something that is increasing in definition. If the definition is increasing and the graph is developing in a certain direction, it must be able to put it in a category of something that is 'solid' and 'void', and in your graph, what is colored must actually be void? and the solid is black.
for example, If I trace a star, the edges of the star is first recognized, and only later - as the definition increases, the valleys of the star is found... if you understand what i mean?
well, just a thought, not totally waterproof, but workable...
/Linus
Vorlath # 14. July 2009, 16:44
Vigenere decoding normally uses a repeating key. So each x letters are decoded with the same letter. Take those decoded letters and they should still have a distribution like English. So what you do is take all 26 possible decodings by setting x to each of the 26 letters. One of them has got to be right. The one that gives the decoding most similar to English is usually the correct one. Doesn't always work, but for a lot of text, it pretty much does.
For autokey, it's essentially the same problem. But instead of using the same key letter x, you use the decoded plaintext letter as the key to decode the next letter (at equal intervals). This causes a chain reaction where each letter is decoded with a prior plaintext letter (each of which are equal distance from each other). So again, you will get ONE decoded sequence for each initial key letter x. So you then apply the same technique as before and see which of those 26 sequences looks the most like English.
Then there's other things like chi tests, but that's just a way of comparing the distribution of each decoded group. IOW, if your key is 6 letters long, you will get 6 groups. Each of the letters in those groups will be 6 letters apart in the plaintext and ciphertext (group 1 is letter 1,7,13,... group 2 is letter 2,8,14,...). So chi tests allow you to find the best distribution that matches all 6 groups (instead of matching to English).
About Mandelbrot... yeah, I was surprised that it would actually invade areas like that. I always thought each section just got bigger. But no. It actually grows.
At the end, I think you're talking about what is termed high frequency data in image compression circles. The smooth areas and large details are low frequency data. The smaller the details, the higher the frequency (and hence takes more data and more iterations within Mandelbrot to calculate).
Don't know about solid and void. Mandelbrot is calculated by knowing which ones loop back forever and which ones go to infinity. Yeah, ok, I guess your description works too.
Anonymous # 15. July 2009, 15:13
yes that would be the artist forum EP. I'm sorry, you think to fast, I need more time with the decoding of vigenere. :)
I got stuck with the listing of possible usage of each 10 groups. ("Here is a table representing each possibilities usage for the above cipher text of K1 in Kryptos for each of our 10 groups.") ; I'm sorry, I'll just need time to study this more. I will surely consider this extra information. I've actually not walked the walk yet, so to speak.
I've thought a bit further on the subject 'solid' and 'void' and perhaps all it means is that, if found, there is at least one more dimension to a graph, presenting a behavior like this?
So, as a method, I could for example blur an ordinary photo image and retrieve object data, by blurring in and out in a 2 dimensional image definition(and it would behave in a manner similar to a graph invading new areas - as the definition increases), still, the 2d representation captures a higher 3d object? maybe it's the same as high frequency data in image compression circles? I don't know?
I get back.
Vorlath # 15. July 2009, 22:57
The 10 groups are simply each 10th letter.
Group 1 is {1,11,21,31,41,51,...}
Group 2 is {2,12,22,32,42,52,...}
Group 3 is {3,13,23,33,43,53,...}
...
Group 10 is {10,20,30,40,50,60,...}
Since Vigenere uses a repeating key, then each group will be decoded with the same letter. Group 1 will be decoded with the 1st letter of the key. Group 2 will be decoded with the 2nd letter of the key. Group 3 will be decoded with the 3rd letter of the key.
So to know what the key letter is for each group, we simply try all 26 letters of the alphabet. That's what the diagram is. The first column lists all 26 possible decodings for group 1. Beside each entry is a number representing how close it is to English. The higher the number, the more it looks like English. To calculate this number, simply add the respective value for each letter of the decoding from the alphabet above the diagram.
After that, I start listing the groups with the highest value in a single column where it is WAY above all other values. Once you have a few groups selected, words should form vertically and you can more easily select groups from other groups where the top candidates might be too close to call. For example, I had BETW listed vertically. So BETWEEN is the word that is most likely. We select those groups from grid column 5,6 and 7 that will complete the word BETWEEN. Specifically, we look for E in the correct location in the next two groups (in the 5th and 6th group column), and N in the third new group (in the 7th group column). After this, more partial words should be visible vertically. Don't forget that words wrap from the bottom to the top one over to the right.
Mandelbrot is definitely 3D. The complex number is 2D. And the iteration index is the other axis. It even has two directions. Those that head toward a circular loop and those that head toward infinity. Both have an index where you can tell for certain that it's in one group or the other. That index is what we use for the color, though I did not display it for the interior.