Due: Friday, Dec 05, 11:59PM CST
Submit: Turn in your source files using the turnin command on
Morbius. Please name your file "pascal.S". Failure to follow this
simple convention may significantly delay grading of your
assignment.
Work may be completed in teams of two. The names of both partners
must appear in a comment block at the top of your file for credit to
be given.
Take time to familiarize yourself with the UNIX environment, using the
tutorial here.
Intel x86 assignments are to be compiled and run natively on our Linux workstations in the systems lab. You will not require the MIPS Playground or the mipcon tool for this assignment. Instead, compose your program in an empty file, perhaps starting with the Intel x86 demo as a template.
Your work must be compiled on a machine with the proper tools, such as the dual-head Linux boxen in the Systems Lab (CU 310). Consult the professor for advice on connecting remotely if the lab is full or you must work from elsewhere. Intel x86 machines can be identified by running the command uname -p; look for machines that identify themselves as i586, i686 or x86_64. Your x86 programms will not compile or run on the PowerPC and MIPS hardware we have in the lab. You may also consult the Systems Lab machine list to check current architectures available. All of these machines are remotely accessible by secure shell. (E.g. ssh morbius.mscs.mu.edu, etc.)
In order to assemble your program, use the command "gcc -m32", followed by the name of your assembly file. In order to run your program, use the command "./a.out". If you do not want your compiled program to be called "./a.out", you may use the "-o" option to gcc to alter the outputed program. Runaway programs can often be killed using Control-C.
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.
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]](fractal.gif)
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 as ~brylow/cosc065/bin/hw11-pascal.