COSC 065 Hardware Systems

Fall 2006

Homework Assignment #9

Intel Assembly Language
Due: Friday, Dec 8, 12:00PM CST
Work may be completed in groups of two students. I strongly recommend that you take the time to meet with your partner in person and work together on these projects, rather than work separately and try to integrate at the last minute.
Background:

Your work on Intel assembly language must be assembled and run on Pascal (pascal.mscs.mu.edu).

Assemble your programs on Pascal using the command:

gcc <myfile.S>

Run your programs on Pascal using the command:

./a.out
unless you have used the "-o" option to gcc to change the name of your assembled executable.

Few rules govern the format of assembly language programs. Make an effort to keep your programs readable and well-documented; sometimes the professor gives partial credit if he can tell what you were trying to do, even if it doesn't quite make it.
Pascal's Triangle

Write an assembler program that reads in a single integer from the user and outputs a properly spaced and centered Pascal Triangle of the requested size. Pascal's triangle is a triangular array of numbers (these numbers correspond to the binomial coefficients) whose left and right hand borders are all 1's and where each number is the sum of the two immediately above it. That is: 

                                1

                              1 + 1
                               \ /
                            1 + 2 + 1
                             \ / \ /
                          1 + 3 + 3 + 1
                           \ / \ / \ /
                        1   4   6   4   1
                                :
                                :
  • The first 6 rows of the Pascal triangle are the following:
    •                         1                  n=0

                      1   1                n=1

                    1   2   1              n=2
                     
                  1   3   3   1            n=3

                1   4   6   4   1          n=4

              1   5  10   10  5   1        n=5

            1   6   15  20  15  6   1      n=6
  • It turns out that you can find interesting patterns in the above sequence of numbers. If you draw the Pascal's triangle as a grid of squares, and color every square that corresponds to an odd number black and every square that corresponds to an even number white, you get the following pattern:
    • [fractal pattern]
  • You do NOT need to compute the numbers in order to decide which one is even and which odd.
  • Let n and k be the indices of the row and column respectively of a number in Pascal's triangle. Consider n and k in their binary representation. If every bit of n is greater than or equal to every bit of k, then the number in the position (n,k) is odd, otherwise the number is even.
  • For example, consider the position (4,2) (all indices start from 0). The binary representation of 4 is 100 and the binary representation of 2 is 010.
    •     1 0 0  (n = 4)
    0 1 0  (k = 2)
      ^
      |
    1 > 0
    You can see that there is a digit of k that is greater than the corresponding digit of n. Therefore, the number in the position (4,2) is even, which is indeed the case since this number is 6.

    The professor has provided an example program for your reference, runnable on Pascal as ~brylow/cosc065/bin/hw9-pascal.
    What to turn in:

  • E-mail your assembly source file to the professor with a subject header "COSC 065 HW#9".
  • Be certain to put all team member names on work submitted. It would be courteous to carbon-copy your teammate when e-mailing the final submission.
    Back