Sierpinski Triangle in Fortran 95

I was assigned the task of writing a program (code) in Fortran (.f95) that would plot points according to X and Y and form a figure that resembled the Sierpinksi Triangle. For those of you who are not aware of what the Sierpinksi triangle is,I will give a brief description, but a quick web search will yield much more detailed results. The Sierpinski triangle is a fractal that consists of triangles, inside of triangles, inside of triangles and so on. Here is a basic image of what it looks like…
sierpinski triangle

Usually, when you think of this shape, you think of it as being built by small triangles in such a way that former larger and larger ones. But in computer code, there is a way to generate this figure using what’s called a “Chaos Game”. Not much of a game really, but it refers to ‘chaos’ due to the (pseudo)random number generation aspect.

Essentially, one can take a “random” number and run it through an algorithm to obtain a single input and output. Repeat this over and over and you will get different results most of the time but it will form a very recognizable pattern, that of the Sierpinski Triangle.

Without further adieu, I will display the snippets of code below and explain what it does in layman terms. The idea is that even someone with no programming knowledge will be able to understand the algorithm, and in theory, plot the graph by hand to achieve the same results, although it would be quite tedious because you would need at least a few hundred iterations to obtain a recognizable pattern.

Part 1: Declaring Our Variables

integer :: n,i
real :: c,x,y

Explanation: Nothing fancy here, we are simply telling the program what variables we will be using, most programs don’t require this, in fact I am actually not sure if version 95 of Fortran requires it but older versions did (77 and 90) so I have stuck with the syntax since it works anyway.

To further elaborate, I will explain why I use these variables and what they mean…

n – The number of iterations or points that you plot.

i – The starting point when you tell the program to complete an ‘n’ number of iterations. This value is usually just one, and each time you calculate another pair of x,y values, then i increases by one. The actual value of i is not used in the formula to compute x or y, it’s just for syntax purposes.

c – a random number between 0 and 1 (up to 8 decimals).

x,y – the value of the points we plot after each ‘iteration’ of the algorithm (in cartesian coordinates).

Part 2: Setting the Variable Values

n=1000
x=0
y=0

Explanation: Before we begin running our variables through the algorithm, some of them must be defined beforehand. Technically, x and y don’t HAVE to be 0,0 but allows us to obtain all x,y values between 0 and 1 which serves for a neater looking chart. n is also somewhat arbitrarily set at 1000, but it could be ANY number, it depends how many points you want to plot. I chose 1000 because it’s enough points to clearly display a Sierpinski triangle without going overboard.

Part 3: Finding x and y for a Single Point

call random_number(c)

if (c<.3333) then
x=0.5*x
y=0.5*y

else if (c>=.3333.and.c<.6666) then
x=.5*x+.25
y=.5*y+.433

else
x=.5*x+.5
y=.5*y

end if

Explanation: This is basically the formula for finding x and y. “If,then” statements are usually pretty self-explanatory even for non-programmers but I will go in to some detail anyway since you may not immediately see WHY this formula works.

The first statement is simply an “intrinsic function” in Fortran that generates a random value between 0 and 1. If this function didn’t exist, it wouldn’t be too complicated to compute our own random number using another algorithm or “sub-routine”, thankfully this is not necessary though.

After we get our random number, we have a series of “if,then” statements which lead us to choose 1 of 3 paths to compute the values of X and Y. Keep in mind that the first time through we start with x=0 and y=0, but later iterations we will not use those values any more, we will instead use the recently computed values of x and y to be our new starting points as we run through the algorithm again, and again, and again.

Once we choose which of the 3 paths to follow (determined by the random number) we can then use the simple formulas to compute our x and y values to be plotted for that particular iteration. By the way, since the random number only picks values between 0 and 1, and we need our 3 paths to be approximately equally likely to occur we set up a simple method of choosing the path. When c is between 0 and 1/3, we choose path 1. When c is between 1/3 and 2/3, we choose path 2. And when c is between 2/3 and 1, we choose path 3.

So what are paths 1,2, and 3?

Leave a Reply