On Fractals

In your labs this week, you’ll be playing with two very different types of code: one works with images in the BMP format, and one acts as a HTTP server. There’s a very good reason for that… but first, the back story.

COMP1511, in Colour!

When we look at an object, our eyes are bombarded with billions of photons, particles of moving light. A photon rolls up a quantity of energy that has a certain frequency, and because photons are so small, they can behave in rather strange ways, and sometimes act like particles or waves, depending on what mood they’re in (and how we observe them).

At a higher level of abstraction, our eyes receive light of a huge range of wavelengths. Visible light has a wavelength of between 400 nm and 700 nm (one nanometer, or nm, is one billionth of a meter).

At a higher level of abstraction, the eye has developed cells that are sensitive to light. Somewhere between 500 and 600 million years ago, the first evidence of photosensitive organisms appeared, and since then, two important features have developed: resolution, and specialisation. The resolution of the eye – the ability for the eye to usefully detect and resolve regions of non-uniform brightness – has developed. And this improved resolution also led to different types of cells that are sensitive to different wavelengths of light.

At a higher level of abstraction, these photosensitive cells, usually referred to as “cones”, produce a small electrical excitation when light they are sensitive to is shined on them. The three common sensitivities are 550 nm to 600 nm, which we call red; 450 nm to 550 nm, which we call green; and 400 nm to 450 nm, which we call blue.

At a higher level of abstraction, the distribution of photosensitive cells is roughly uniform clusters of red-, green-, and blue-sensitive cones across the retina, the rear wall of the eye.

At a higher level of abstraction, the projection of light across these photosensitive cells leads to patterns of electrical stimulus that clusters of cells in the human brain can interpret and feed into the experience of human perception.

Most importantly, though, we can assume that there are only three primary colours: red, green, and blue, and all other colours are only combinations of these. Everything you learned about colour in school tends to be a property of reflective colour, which is how paint behaves: paints are made of pigments that absorb or reflect certain frequencies of light that shine upon them. There are three “primary” reflective colours: cyan, magenta, and yellow (often taught as blue, red, and yellow; I’ll name them differently because it’s confusing otherwise).

We might also safely assume that there are only a finite number of levels of sensitivity in the human eye… perhaps only 256 of them.

And so, we have the idea of a particular point on the mess of cells that is the retina at the back of the human eye, which may respond to three colours at different intensities:

typedef unsigned char sensitivity;
typedef struct _retinaPoint {
    sensitivity longwaveOpsin;
    sensitivity medwaveOpsin;
    sensitivity shortwaveOpsin;
} retinaPoint;

This model is used nearly everywhere else, too, though usually we call this a picture element, or pixel:

typedef struct _pixel {
    unsigned char red;
    unsigned char green;
    unsigned char blue;
} pixel;

And, if we have an array of arrays of pixels, we have an image!

The BMP format, which you’ll explore in the Pacman and Chessboard exercises, is a way to encode an image, a simple, two-dimensional array of pixels, as a perfectly ordinary file.

A Tangled Web

One very good idea that arose in the early days of computers was the prospect of connecting them together for the purpose of sharing important data (like images of cats). Early links tended to be point-to-point connections, though some systems had multiple connections, and the result was a network of computers.

By connecting these networks together into larger, more complex structures, we formed a network of networks, which we referred to as an Internetwork. That name didn’t sell well, and was renamed the Internet.

One particular physicist, who wanted to share a linked network of documents in the late 1980s and early 1990s came up with an interesting idea: by connecting to a particular network port, and sending a particular request you could receive information:

GET /pub/phys/experiments

He also constructed a server that listened on that port, and responded to these requests:

200 OK

Experiment list:
 - /pub/phys/experiments/1911-00
   Geiger, Marsden, Rutherford (UManchester)
...

Of course, these had to be more than just plain text: you can’t really express, in a machine-readable way, the information about a link between documents, or about style and formatting. So, he also proposed a new language, a language for encoding this powerful, expressive idea, by adding, or “marking up”, regions of text with tags, giving us a hypertext markup language.

The result, then, is a protocol for transferring hypertext, and a language for encoding it. This group of technologies, HTTP and HTML, which haven’t radically changed since their inception in the very early 1990s, are often known as the World Wide Web. People often conflate the World Wide Web technologies with servers that provide pages and services on the Web, and with the Internet itself, all of which are very different.

This week, we’ve also given you some very simple web servers, which you can play with in the Simple Server and Poetry Server exercises. These use many library functions and system calls that we haven’t yet explored, and you might like to research more.

Simple Rules, Beautiful Complexity

We’ve played a little with systems of simple rules, like the Wondrous numbers: for an even number, we halve it; for an odd number, we triple it and add one. These rules are deceptively simple in their expression but have overwhelming emergent complexity.

Systems like the Wondrous numbers, the multi-state cellular automatons in one, two, and more dimensions, and others have a very simple basis: a small, simple set of rules that are applied again and again.

Here’s another one: if I pick a complex number μ, let z be equal to μ, and now take a new value, z′ = z² + μ. If the magnitude of this new value z′ is greater than two, the point has escaped.

This may look like a complex rule, but it’s very simple when you remember that μ won’t ever change, and that z² is just z × z.

Now, we apply the rule repeatedly, by setting z to z′ after each step, and count the number of times we apply it before it escapes. This could, potentially, go on forever, so we limit it to 256 iterations, just in case…

And now, if I were to plot this on an Argand diagram, where the horizontal axis is -2 ≤ Re(z) ≤ 2, and the vertical axis -2 ≤ Im(z) ≤ 2, and at each new point, make that point be μ…

For your next assignment, you’ll be building an explorer for this beautiful object, the Mandelbrot set.

Now, go and explore the Mandelbrot set!

almondbread.cse.unsw.edu.au