Data Structures and Discrete Mathematics Learning Community

Stonehill College

Data Structures and Discrete Mathematics Learning Community

Professors Ralph Bravaco and Shai Simonson

Lab 1

Chaos, fractals, and computer graphics

Recently, mathematics has been the backdrop to some very successful plays and films including A Beautiful Mind, Good Will Hunting, and the Pulitzer prize winning play Proof. In Tom Stoppard’s hilarious and award winning play, Arcadia, mathematics is not only a backdrop but a major player. In a British manor house, during both the nineteenth century and the present day, and sharing the stage with sex and satire, fractal geometry, chaos, thermodynamics and even Fermat’s last theorem play starring roles in Stoppard’s captivating, yet sometimes inscrutable, comedy..

Since its premiere in 1993, mathematicians have been fascinated with Arcadia. Indeed, Arcadia was the only play ever to be reviewed in Scientific American. Allyn Jackson, in a review published in Notices of The American Mathematical Society, noted that “Stoppard has understood something of the poetic heart of this area of mathematics” and praised the playwright for “the thoroughness with which [he] has integrated these mathematical ideas into the action of the play.”

For this lab, we’ll use “Arcadian mathematics” as our starting point. We will touch upon fractal geometry and chaos as well as how computers and technology have helped these fields grow and mature. In the process, you will see a wonderful symbiotic relationship between mathematics and computer science.

We begin in a large country estate in Derbyshire, England. The time is April 1809. In this scene, thirteen year old Thomasina is engaged in conversation with her tutor Septimus Hodge:

THOMASINA:

...Each week I plot your equations, dot for dot, x’s against y’s in all matter of algebraical relation, and every week they

draw themselves as commonplace geometry, as if the world of forms were nothing but arcs and angles. God’s truth, Septimus, if there is an equation for a curve like a bell, there must be an equation for one like a bluebell, and if a bluebell, why not a rose? Do we believe nature is written in numbers?

SEPTIMUS:

We do

THOMASINA:

Then why do your equations only describe the shapes of manufacture?

SEPTIMUS:

I do not know.

THOMASINA:

Armed thus, God could only make a cabinet.

SEPTIMUS:

He has mastery of equations which lead into infinities where we cannot follow.

THOMASINA:

What a faint heart! We must work outward from the middle of the maze. We will start with something simple. I(She picks up an apple leaf.) I will plot this leaf and deduce its equation. You will be famous for being my tutor when Lord Byron is dead and forgotten.

We time travel to the present day – same house, same room, in fact, same props. . Thomasina’s notebook has been discovered by writer Hanna Jarvis, who questions Valentine, a mathematician and biologist, as to its meaning:

HANNAH (reading from Thomasina’s notebook)

‘ I, Thomasina Coverly, have found a truly wonderful method whereby all the forms of nature must give up their numerical secrets and draw themselves through number alone. The margin being too mean for my purpose, the reader must look elsewhere for the New Geometry of Irregular Forms discovered by Thomasina Coverly.’ (To Valentine) Does it mean anything?

VALENTINE:

I don’t know. I don’t know what it means, except mathematically.

HANNAH:

I meant mathematically.

VALENTINE:

It’s an iterated algorithm.

HANNAH:

What’s that?

VALENTINE:

Well it’s...Jesus...it’s an algorithm that’s been...iterated. How am I supposed to...? (He makes an effort.) The left hand pages are graphics of what the numbers are doing on the right hand pages. But all on different scales. Each graph is a small section of the previous one, blown up, like you’d blow up a detail of a photograph, and then the detail of a detail, and so on, forever. Or in her case, till she ran out of pages.

HANNAH:

Is it difficult?

VALENTINE:

The maths isn’t difficult. It’s what you did at school. You have some x-and-y equation. Any value for x gives you a value for y. So you put a dot where it’s right for both x and y. Then you take the next value of x which gives you another value for y any when you’ve doe that a few times you join up the dots and that’s your graph of whatever the equation is.

HANNAH:

And, is that what she’s doing?

VALENTINE:

No. Not exactly. Not at all. What she’s doing is, every time she works out a value for y, she’s using that as her next value for x. And so on. Like a feedback. She’s feeding the solution back into the equation and then solving it again. Iteration, you see.

HANNAH:

And that’s surprising, is it?

VALENTINE:

Well, it is a bit. It’s the technique I’m using on my grouse numbers, and it hasn’t been around for much longer than, well, call it twenty years.

HANNAH:

Why would she be doing it?

VALENTINE:

I have no idea.....

When your Thomasina was doing maths, it had been the same maths for a couple of thousand years.Classical. And for a century after Thomasina. Then maths left the real world behind, just like modern art, really. Nature was classical, maths was suddenly Picassos. But now nature is having the last laugh. The freaky stuff is turning out to be the mathematics of the natural world.

......

HANNAH:

What I don’t understand is ...why nobody did this feedback thing before—it’s not like relativity, you don’t have to be Einstein.

VALENTINE:

You couldn’t see to look before. The electronic calculator was what the telescope was for Galileo.

HANNAH:

Calculator?

VALENTINE:

There wasn’t enough time before. There weren’t enough pencils! This took her I don’t know how many days and she hasn’t scratched the paintwork. Now, she’d only have to press a button. Iteration. A few minutes.

Thomasina’s discovery anticipated a new field of mathematics called fractal geometry. Fractal geometry has been able to model complex objects like leaves, clouds, ferns, mountains, or even the coastline of England. – objects that Euclidean geometry’s lines, circles and spheres could not explain. Fractal geometry has ushered in a new way of looking at nature. Fractals have found their way into the realms of abstract art. Fractal images have even been used in popular films: Star Trek II used fractal images to create computer-generated images of outer space. Here are a few pictures of these strange geometric objects – fractals:

Obviously, fractals are detailed, intricate objects. One noticeable property of a fractal image is “self-similarity,” a characteristic described by Valentine:

The left hand pages are graphics of what the numbers are doing on the right hand pages. But all on different scales. Each graph is a small section of the previous one, blown up, like you’d blow up a detail of a photograph, and then the detail of a detail, and so on, forever. Or in her case, till she ran out of pages.”

On the same subject, Ivars Peterson, in The Mathematical Tourist, writes;

Fractal objects contain structures nested within one another. Each small structure is a miniature, though not necessarily identical, version of the larger form. The mathematics of fractals mirrors this relation between patterns seen in the whole and patterns seen in parts of the whole.

If the idea seems confusing, a single picture should clear things up.

Below is a picture of what is called Sierpinski’s gasket.

To generate Sierpinski’s gasket, begin with an equilateral triangle.

Now , find the midpoint of each side and form three more triangles as in the diagram, discarding the triangle in the center.

Repeat the process—giving 9 triangles.

And continue or iterate...... forever producing 1,2,9,27, 81,243,729....triangles. The Sierpinski gasket is the set of points that remain if the process is carried out indefinitely. Self-similarity is an apparent property of the Sierpinski gasket. However, the truly amazing thing about the Sierpinski gasket is that Sierpinski’s gasket has zero area.

Note: to draw a point, you can draw a circle with radius 1 or draw a rectangle of size 1.

Exercise 1:

Write a program that will draw the Sierpienski gasket. You might write this as an

iterative procedure--- but don’t. Use a recursive function:

void sierpienski(int x1,int y1, int x2, int y2, int x3, int y3, int depth, window & w)

where (xi,yi) are the vertices of a triangle and depth is the maximum level of recursion.

Remember: The top left hand corner of your window is (0,0).

Exercise 2:

In the play Valentine remarks:

You never know where to expect the next dot. But gradually you start to see this shape.....The unpredictable and the predetermined unfold together to make everything the way it is.

This exercise, should give you an idea of how the unpredictable and the predetermined do unfold together.

Write a program which implements the following iterative algorithm.

1. Hard wire into your program three points of an equilateral triangle (x1,y1), (x2,y2) (x3,y3). These can be screen coordinates. Remember (0,0) is at the top left corner.
2. Pick one of the three vertices at random, call it (x,y)
3. Repeat

Pick a vertex, (x1,y1), (x2,y2) or (x3,y3) at random. Call it v.

Place (draw a pixel) a point p exactly halfway between (x,y) and v

Set (x, y) equal to p

Forever ( or until 10000 points have been drawn)

Describe the figure and explain how the algorithm produced such a figure.

Exercise 3:

Write a program to implement the following iteration. The result should be another self-similar graphic.

1. Hardwire the coordinates of four corners of a square into a graphics program.
2. Find the midpoints of the four sides of the square
3. Use a random number generator to select one of these eight points, call it (x,y)
4. Use a random number to select one of the four vertices, v.
5. Draw a point p between (x,y) and v such that the distance from p to the vertex is 1/3 the distance from (x,y) to the vertex.
6. Call the new point (x,y)
7. repeat 4-6 indefinitely

Exercise 4.

Design and implement an algorithm, similar to the algorithms of either exercise 1,2, or 3. Your output should be some self-similar geometric figure. Use your imagination.
Some colorful fractals.

While the Sierpinski gasket simply and effectively illustrates the notion of similarity, the last decade has produced some amazing, and quite, beautiful computer-generated pictures of fractals . Two of the most famous fractal images are pictures of the Julia set and the Mandlebrot set

Julia Set / Madlebrot Set

Ivars Peterson describes the Mandlebrot set:

...It has the appearance of a snowman with a bad case of warts...On superficial inspection, the Mandlebrot set looks like a self-similar fractal, with infinitely many copies of itself within itself. On detailed investigation, however, the set is extraordinarily complicated. The baby Mandebrot sets within the parent Mandlebrot sets are fuzzier than the original. They have more hair and other curious features. ... Fractals such as the Mandlebrot set are called nonlinear fractals. For self-similar fractals, lines that show up within a figure, whether blown up or reduced in size remain lines. For nonlinear fractals such a change in scale doesn’t preserve the straightness of individual lines.

Note:

In order to understand the basics of the Julia and Mandlebrot sest you must know a little bit about complex numbers. If complex numbers are new to you or somewhat hazy, you should read Appendix A of this lab.

THE JULIA SET:

Iteration (Thomasina’s Discovery!)

The first step to understanding these remarkable computer generated images is the concept of an iterated algorithm. After his initial attempt (“It’s an algorithm that’s well...iterated), Valentine provides us with a perfectly reasonable explanation:

You have some x-and-y equation. Any value for x gives you a value for y. So you put a dot where it’s right for both x and y. Then you take the next value of x which gives you another value for y any when you’ve done that a few times you join up the dots and that’s your graph of whatever the equation is.

We illustrate the process of iteration by looking at y = x2 (f(x) = x2) with various starting/initial values for x.

Initial value x = 0.
x y
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
table 1 / Initial value x = -1
x y
-1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
1 1
table 2 / Initial value x = .5
xy
0.5 0.25
0.25 0.0625
0.0625 0.00390625
0.00390625 1.52588e-05
1.52588e-05 2.32831e-10
2.32831e-10 5.42101e-20
5.42101e-20 2.93874e-39
2.93874e-39 8.63617e-78
8.63617e-78 7.45834e-155
7.45834e-155 5.56268e-309
table 3
Initial value x = .99
x y
0.99 0.9801
0.9801 0.960596
0.960596 0.922745
0.922745 0.851458
0.851458 0.72498
0.72498 0.525596
0.525596 0.276252
0.276252 0.076315
0.076315 0.00582398
0.00582398 3.39187e-05
3.39187e-05 1.15048e-09
1.15048e-09 1.3236e-18
1.3236e-18 1.75192e-36
table 4 / Initial value x = 1.01
x y
1.01 1.0201
1.0201 1.0406
1.0406 1.08286
1.08286 1.17258
1.17258 1.37494
1.37494 1.89046
1.89046 3.57385
3.57385 12.7724
12.7724 163.134
163.134 26612.6
26612.6 7.08229e+08
7.08229e+08 5.01588e+17
5.01588e+17 2.5159e+35
table 5 / Initial value x = 2
2 4
4 16
16 256
256 65536
65536 4.29497e+09
4.29497e+09 1.84467e+19
1.84467e+19 3.40282e+38
3.40282e+38 1.15792e+77
1.15792e+77 1.34078e+154
table 6

We first need a little terminology.

Definition.

Let y = f(x). Let x0 be a given initial value for an iterative process. The set { x0, y1, y2, y3...} where y1=f(x0), y2=f(y1), y3 = f(y2) ....yn+1 = f(yn)... is called the orbit of x0.

Let y = x2.

x0 = 0orbit(0) = {0}(table 1)

x0=-1, orbit(1) = {-1,1}(table 2)

x0 = .5 orbit(.5) = {.5,..25,.0625,.00390625.....} (table 3)

x0 = 2 orbit(2) = { 2,4,16,256,65536.....} (table 5)

It is not too difficult to see that for y= x2, if the starting point in an iteration (x0) is greater than 1 ( see table 5) or less than –1 then orbit (x0) “escapes” to infinity, that is the orbit is unbounded. For starting a point x0 in the interval (-1,1), orbit(x0) gets closer and closer to 0 . In this case we say 0 is an “attractor” and the orbit is bounded (tables 1,3,5). If the starting point is x0 = 1 or x0 = -1, then 1 is an attractor (table 2).

The set of all points with unbounded orbits is called the escape set for f(x). The set of points with bounded orbits is called the prisoner set for f(x).

In our simple example, if y = x2, the escape set is the set of all numbers greater than 1 or less than –1; the prisoner set is the set of all numbers between 1 and –1 inclusive.

escape set -1 prisoner set 1 escape set

Complex Numbers

The story becomes a bit more interesting when we consider complex rather than real numbers. Recall that complex numbers have two parts – a real part and an imaginary part. We would write a complex number z = x+yi, where x and y are real numbers and i is the square root of –1. Please see for a very brief and simple introduction to complex numbers.

Note: Even if you have never heard of complex numbers, you can still write the code for the exercises below, using the hints and examples given below.

Let’s use the same quadratic function, w = z2 (f(z) = z2) but now assume that z is a complex variable of the form z = x + iy.

Suppose that we iterate with initial value z0 = i

z w = f(z)

i-1

-1 1

1 1

1 1 etc.

Here the orbit(i) is {i,-1,1,1,1,1...... }. Consequently, i is a member of the prisoner set.

Now suppose that the initial value is z = 1+ i

z w |w|

1+i (1+i)(1+i) = 2i 2

2i-4 4

-416 16

In this case, the orbit(1+i) = {1+i,2i,-4, 16, 256...}

Notice with initial value, z 0 = 1 + i, orbit(z0) escapes to infinity. (Look at the absolute values.). Thus, 1+i is a member of the escape set.

With those ideas in mind, now describe the Julia set.

Let f(z) = z2 + c , where z is a complex variable and c is some complex constant.

The escape set and prisoner set for f(z) together cover the complex plane and are complementary. The Julia Set is the boundary of the escape set. In other words, the Julia set is the boundary of the set of starting points z0 whose orbits escape to infinity.

Exercise 5.

Write a computer program which draws the Julia set for w = z2.

Color all points in the prisoner set black. Vary the colors in the escape set depending on how fast the iterations go to infinity.

Theorem.

Let f(z) = z2 + c. Let z0 be an initial point in an iterative process. If any point in orbit(z0) has absolute value greater than max(|c|, 2) then z0 is in the escape set.

In other words, if the absolute value of any one point in orbit(z0) exceeds max(|c|,2), then the orbit escapes to infinity, it is unbounded, and z0is in the escape set.

Hints:

1. Design a class Complex to represent the complex numbers. Your class should have

1. constructors
2. addition add (Complex c)

Example: (x,y) + (u,v) = (x+u, y+v)

1. subtraction : sub (Complex c)

Example: (x,y) – (u,v) = (x–u, y–v)

1. multiplication: Mul (Complex c)

Example: (x,y) * (u,v) = (xu–yv, xv+yu)

1. absolute value – abs()

Example: abs((x,y)) = sqrt(x2 + y2)

1. real() – returns real part

Example: real((x,y)) = x

1. imaginary() – returns imaginary part

Example: imaginary((x,y)) = y

1. set(real,im) – sets the real and imaginary parts of a complex number

2. Write your function f(z):
complex f(complex z)

3. Decide what part of the plane you will examine, perhaps the rectangle defined by the points –2-2i and 2+2i. So define constants like lower_x = -2, lower_y = -2

upper_x = 2, upper_y = 2. (Strictly speaking, to use our theorem, we should choose a circle with radius 2, but these extra points will not make a difference in our picture)

You will have to use “each” of these points as a starting point. Obviously, you cannot use ever, single point in this region of the complex plane. So, loop through the points with loop such as:

for (double x = lower x; x < upper_x; x += .005)

{

for (double y = l_lower_y; y < upper_y; y += .005)

{

4. Given a starting point, you need to determine whether it is in the escape set or the prisoner set. Obviously, you need the orbit of the point. We need to examine the size (absolute value) of each point in the orbit. If the size of a point exceeds max(|c|, 2,) we know it is in the escape set and we can stop iterating. On the other hand, let’s set a maximum number of iterations, say Maxi = 50. If the orbit does not escape to infinity after Maxi iterations, we will assume it is in the prisoner set. (Of course, there is always the chance of error, here).

5. Iterate. If a value in the orbit has absolute value max(|c|, 2), the starting point is in the escape set and stop iterating. If the number of iterations reaches Maxi, assume the starting point is in the prisoner set.

6. Here is the fun part. Color the starting point. If it is in the prisoner set, color it black. If it is in the escape set, color it with RGB values based on the number of iterations it took before “escaping”. For example,