# Making a Sierpinski Triangle

The Sierpinski Triangle (also called the Sierpinski gasket or the Sierpinski Sieve) is a very simple fractal to make and it can be made in different ways. I am going to show some source code to make them using logical AND, logical XOR, an iterative method and one method using Pascal's triangle. The source code is shown in Java and for the Casio calculators. Note that the Casio programs are slow.

## Logical AND method

You can create a right-angled triangle by doing a logical AND of the coordinates of x and y of the screen.
Here is an extract in Java to draw it (it can be converted to C++):

void myDrawingMethod(Graphics g)
{
int x,y;
Rectangle r = getBounds();
for(y=0;y<r.height;y++)
{
for(x=0;x<r.width;x++)
{
if((x&y)==0)g.drawLine(x,y,x,y); /* x&y means do a logical AND of x and y
//the g.drawLine is used to plot a pixel (I do not have a plotpixel command) */
}
}
}

This produces:

I programmed a version in to my Casio CFX-9850G PLUS calculator:
AxesOff
Cls
For 0→T To 62
For 0→S To 125
S→A
T→B
Prog "BITAND"
C=0⇒PxlOn T+1,S+1
Next
Next
AxesOn
Remember the PxlOn command takes Row,Column rather than x,y and the upper-left corner is (1,1)
The above requires a program called BITAND which needs to be put in a BASE format or it will not work (I press F2 when I created the file)

AandB→C

## Logical XOR method

The image at the top of the page was produced with the logical XOR method (exclusive-or). You plot a pixel on the top of the screen then scan across underneath line by line, plotting a pixel if the upper-left and upper-right pixel produces a 1 when a XOR operation is performed.
 A B X
Plot at X when xor(A,B) produces a 1

Unfortunately in Java, I couldn't get the colour of the screen pixel so I had to use an array of bytes:

public void paintComponent(Graphics g)
{
int x,y,FrameWidth,FrameHeight;
FrameWidth=getWidth();
FrameHeight=getHeight();
byte CurrentLine[]=new byte[FrameWidth];
byte NextLine[]=new byte[FrameWidth];
CurrentLine[FrameWidth/2]=1;//set the initial pixel in the middle of the screen
g.drawLine(FrameWidth/2, 0, FrameWidth/2, 0);//plot it on screen
for(y=1;y<FrameHeight;y++)//start at y=1 (one line lower)
{
for(x=1;x<FrameWidth-2;x++)
{
/*start one pixel in because the array is looking at x-1 and x+1*/
if(((CurrentLine[x-1])^(CurrentLine[x+1]))>0)
{
/*A^B means perform an ExclusiveOr on A and B*/ NextLine[x]=1; g.drawLine(x,y,x,y);
}
else NextLine[x]=0; }
System.arraycopy(NextLine, 0, CurrentLine, 0,FrameWidth); //make the next line the current one
}
}

On my calculator:
AxesOff
Cls
64→G~H
PxlOn 1,G
For 2→T To 63
G-1→G
H+1→H
For G→S To H
PxlTest T-1,S-1
Ans→A
PxlTest T-1,S+1
Ans→B
Prog "BITXOR"
C⇒PxlOn T,S
Next
Next
AxesOn

Again this needs another file in the BASE format called BITXOR:
AxorB→C

## Iterative Function method (also called the chaos game)

There is a simple way of producing it by iterating multiple times. Given any three points of a triangle in complex number format, you choose one of them, choose another and halve the distance between them. Plot a point and then choose another point at random, repeating the process.
Here is a bit of pseudo-code to illustrate what I mean:

Set points P1, P2, P3 to the coordinates of your triangle in complex number format e.g. P1 = 30 + 20i
CurrentPoint = P1 (or any point)
StartOfLoop
{
R = a random point chosen from P1, P2, P3
CurrentPoint = (R  + CurrentPoint) / 2
PlotPixel (CurrentPoint)
}Loop until a key is pressed

The code can be simplified for speed purposes. My Java code halves by doing a bit shift right (which is FAR quicker than a division by two) and the points are halved at the start. It also does not use complex numbers. Here is the ENTIRE applet for a web page:

SierpinskiIT.class
import java.awt.Graphics;
public class SierpinskiIT extends java.applet.Applet
{
public void init(){}
public void paint(Graphics g){myDrawingMethod(g);}
void myDrawingMethod(Graphics g)
{
int x,y,iterations,decision;
x=0;y=0;//start at 0,0 in this case
/* The other points are at (400,600) and (800,0) which are already halved for speed */
for(iterations=0;iterations<100000;iterations++)
{
decision=(int)(Math.random()*3.0);//this makes "decision" equal to 0, 1 or 2
x=x>>1;y=y>>1; // halve the point
if(decision==1){x+=200;y+=300;}//(200,300) is half of (400,600)
if(decision==2){x+=400;}//(400,0) is half of (800,0)
g.drawLine(x,599-y,x,599-y); /*plot a pixel and invert the image (otherwise it displays upside-down) by 599-y which flips the y coordinate */
}
}//myDrawingMethod()
}

This produces (after 100000 iterations):

Here's the source code for the calculator (using complex numbers):
ClrGraph
0→P
For 1→K To 3000
Int (3Ran#)→N
.5×P→P
N=1⇒P+31+31i→P
N=2⇒P+62→P
PxlOn 63-Int ImP P, 1+Int ReP P
Next
Text 1,1,"FINISHED"

## Pascal's triangle

Pascal's triangle is a triangle formed by adding the numbers up on the upper left and the upper right of the number you are examining. I have programmed one way of doing it. It is not efficient but it is written in a way that you can see how it is done (I could have incorporated two loops in one, the for (x= ...)
I colour only the odd numbers black. I have also not put the triangle in the middle but squashed it to one side. You can modify the code if you wish but it will just look like the XOR method above.
Another modification is to use the combination equation to generate it (from the Binomial Theorem) but I did not use that because the factorial numbers would be very large.

class PascalSierpinskiPanel extends JPanel
{
public void paintComponent(Graphics g)
{
int x,y,FrameWidth,FrameHeight;
FrameWidth=getWidth();
FrameHeight=getHeight();
int CurrentLine[]=new int[FrameWidth];
int NextLine[]=new int[FrameWidth];

CurrentLine[0]=1;//The top of the triangle is a 1
g.drawLine(0, 0, 0, 0);//draw it

for(y=1;y<FrameHeight;y++)
{
NextLine[0]=CurrentLine[0];
/*This really is CurrentLine[0] + CurrentLine[-1] which would give an
error. The number at CurrentLine[-1] should be a 0
*/
for(x=1;x<FrameWidth;x++)
{
}
for(x=0;x<FrameWidth;x++)
{

if((CurrentLine[x]&1)==1)//if the number is odd
{
g.drawLine(x,y,x,y);
}
}
System.arraycopy(NextLine, 0, CurrentLine, 0, FrameWidth);
}
}//paintComponent
}//PascalSierpinskiPanel
Note: The symbol & here is a logical AND operation. CurrentLine[x]&1 means get bit 1. Bit one is a one if the number is odd.

There are other ways to generate the triangle. You could use a recursive method and divide it repeatedly. You can make one in 3D too. I have just provided some of the simple ones I know.