Machine Problem 3, due Oct. 13

 
Some graphics: Conisder this sequence of figures:

__  ____  ________  ________________
\/  \/\/  \/\/\/\/  \/\/\/\/\/\/\/\/
     \/    \/__\/    \/__\/  \/__\/
1           \/\/      \/\/    \/\/
    2        \/        \/______\/
         3              \/\/\/\/
                         \/__\/
                    4     \/\/
                           \/

These figures are examples of a family of fractals known as Sierpinski triangles. As the Wikipedia article cited above shows, there are lots of ways of thinking about this figure, but note that here we are interested in constructing the figure out of typographical elements, specificall, the / (slash), \ (backslash) and _ (underline) characters. That possibility is not discussed in the Wikipedia article.

Some geometric observations: Figure 1 is 2 characters wide by 1 character high (plus some underlines on the line above).

A figure of order i (for any positive value of i) is 2ⁱ characters wide and 2^i–1 characters high (plus some underlines on the line above).

If we have a figure of order i greater than one, with its left upper corner (x, y), it is made up of 3 figures of order i-1 with their upper left corners at:

• (x, y)

• (x+2^i–1, y)

• (x+2^i–2, y+2^i–2).

If we have a figure of order i greater than one, with its left upper corner at (x, y), the center of the figure is at:

• (x+2^i–1, y+2^i–2).

Musing about programs to print these: A program to plot these figure on the screen would obviously be recursive. If asked to plot an order 1 figure at location (x, y), it would simply output two underlines, a left-slash and a right-slash, with appropriate calls to putat() mixed in to set the locations of the characters relative to the coordinates of the corner. If asked to plot an order i figure at location (x, y), it would make three recursive calls for order i–1 figures with appropriate corner coordinates.

You could, of course, pass 2ⁱ instead of the literal order i. This would eliminate a whole bunch of exponentiation and substitute multiplying and dividing by two.

If it weren't for the horizontal lines at the tops of the triangles, you could make the three recursive calls in any order at all. Because of the overbars, you end up having to plot one of the figures first in order to get output that looks like that given above.

An assignment: Write a program that prints the largest Sierpinski triangle that will fit on the screen. The triangle should within one character of being centered, both horizontally and vertically, in the drawing area.

Issues you may need to face: The width (x size) and height (y size) of the screen are passed as parameters to the main program by the Hawk monitor. You can use these dimensions to compute the largest triangle that will fit.

Centering is a matter of dividing x and y sizes by two to get the coordinates of the center and then offsetting from there to get the coordinates of the upper left corner, using the details discussed in the geometric observations section above.

Look up the SL and SR instructions for quick and dirty tools for multiplying and dividing by two. You certainly do not need to use the Hawk monitor's divideu routine here, no do you need routines to compute exponentials or logarithms.

Requirements: Your program must:

• Produce the correct output.
• It must begin with a TITLE directive giving (in compact form)
  • The program name (mp3.a)
  • Your name
  • The data you completed the assignment
• Cleanly readable code including
  • Consistent use of indenting; all the examples in the notes illustrate this.
  • Comments that tersely but adequately explain your code comments should not state what is obvious from reading the code, but should raise the level toward the level of high level languages and the comments you would add to a high-level language program.
  • Your main program is just a subroutine, and it should be documented like any other subroutine. You have graduated from relying on incomprehensible boilerplate by the time you are writing your own subroutines.

The above requirements should be taken seriously. We will not do detective work to determine who gets credit for what assignment. If your name is not in the title line for the source file, we will not grade your source file. This is partly a matter of professional ethics: Take credit for your work. It is also to defend an overloaded grader from having to do extra work.

Submission: As with MP1, use the on-line Online Coursework Submission tool provided by the Liberal Arts Linux server cluster. Your source file must be named mp3.a (the name is case-sensitive). This is the name you will type in response to the File/directory name prompt. When the submission tool prompts for Course type c_060. Select the assignment directory mp3.