Machine Problem 3, due October 29

Background:

The Sierpinski gasket is a fractal made up of triangles nested within triangles nested within triangles. The Wikipedia writeup is decent:

http://en.wikipedia.org/wiki/Sierpinski_triangle

The an approxiamatiomn of a Sierpinski gasket can be rendered using just the slash and backslash characters or using slash, backslash and underline as follows:

               /\                   /\         
              /\/\                 /__\       
             /\  /\               /\  /\      
            /\/\/\/\             /__\/__\     
           /\      /\           /\      /\    
          /\/\    /\/\         /__\    /__\   
         /\  /\  /\  /\       /\  /\  /\  /\      
        /\/\/\/\/\/\/\/\     /__\/__\/__\/__\ 

The version with the underline requires a slightly more complex algorithm to produce, but the smallest triangles it shows are two characters high, versus the one-character-high triangles you get without using dashes.

All Sierpinski triangles rendered using this approximation will have a height of 2ⁱ lines of text and a width of 2ⁱ⁺¹ characters, for some integer i.

The Assignment:

Write a Hawk program that outputs the largest possible Sierpinski gasket on the screen of the Hawk emulator. Note that if you set the font small and then resize the window so that it's very big before you launch the emulator, you should be able to make very big gaskets, while the default window size may limit you to very simple gaskets. Obviously, debug your code using a relatively small window!

Suggestions:

There are two problems hidden in this assignment: First, finding the dimensions of the largest Sierpinski gasket that fits on the screen, and second, generating that gasket. Treat these as separate problems! They can be solved independently.

Finding the largest gasket:

The DSPINI routine returns the width and height of the screen. The first step in finding the largest gasket is to find the largest power of two less than or equal to each of these. The dumbest way to do this is perfectly good. Consider something like this:

        int max( int x ) {
            int i = 1;
            while (i <= x) { i = 2*i; }
            return i/2;
        }

Of course, once you have the largest power of two less than or equal to the height and the largest power of two less than or equal to the width, you must figure out which of these sets the limit on the display.

Displaying the gasket:

The most straightforward way to display the gasket is with a recursive subroutine that takes the coordinates of one corner of the gasket and the size of the gasket as parameters and outputs that gasket. Consider this framework for displaying the gasket:

        gasket( int x, int y, int height ) {
            if (height < min) { /* plot one triangle */
                dspat( x, y );
                dspst( "/\" );
            } else {
                gasket( x, y, height/2 );
                gasket( x + height, y, height/2 );
                gasket( x + height/2, y - height/2, height/2 );
            }
        }

This example code has not been debugged. Many details are missing, such as where you should start on the screen. Make sure you understand this code before turning it into assembly language!

A broad suggestion: All of the multiplication by two and division by two in this code can be replaced by left and right shift operations.

Submission and Grading:

As usual, submit your source code using Icon. If the code executes perfectly and displays the simple version of the gasket on the screen for several different window sizes, this will be worth half credit. The other half of the score depends on the clarity and cleanliness of your code, including appropriate commentary and readable formatting.

Extra Credit:

An additional 1/2 point will be granted to assignments that print the more difficult version of the triangle, using underlines as well as diagonal slashes.

An additional 1/2 point will be granted if you can approximately center your gasket in the available display area instead of leaving it wedged in the upper left corner -- that being the easiest place to leave it.