This is not a group project.
Do not accept code from other students or tutors.
Do not have the code of other students in your own directories.

REQUIRED:

Put your project file in a directory named:

/home/stu/you/2240/project/

(replace you with your username)


You have to make the folder yourself.
mkdir project

Not: /224/p224/project/
Not: /224/p224/

Your project filename must be one of the following:

50.s
65.s
70.s
80.s
90.s
95.s
100.s

# 95.s 
# larry coder
# CMPS 2240 final project - Fall 2016
# this code displays the nth row of pascal's triangle
# usage: spim -f 95.s n k 

$ cd ~/2240
$ mkdir project

Week  Grade  Milestone
----  -----  ---------------------------------------------------------
  4    50%   Read n,k from cmdline; convert to ints; swap if n < k.
  5    65%   Set n=6, k=4 as default; exit if args are not numbers
  6    70%   Compute n! and k!
  7    80%   Compute C(n,k) = n!/((n-k)!k!).
  8    90%   Display row n of Pascal's triangle for k = 0 to n.
  9    95%   Display all rows i of Pascal's triangle, i = 0 to n.
 10   100%   Write a recursive function to compute C(n,k), named Cnk_r.
----------------------------------------------------------------------

Phase 50

Objective: Read n, k from cmdline, convert and swap if n < k

Deliverable: 50.s

Description:

For 50% write a MIPS program to grab two numbers n and k from the command line. Call atoi to convert the numbers (which are really strings) to integers. Swap the integers if n < k. Display args followed by a line feed.

Refer to gcd.s from Week 3 for how to grab and use two numbers from the command line and convert them from a string to an integer. You may want to start your project with gcd.s and remove things you do not need.

For now you can assume valid arguments (i.e., two numbers) will be passed. Thus you do not need to do any error checking in this phase. In Phase 65 you will code two default arguments so your program will work if the user does not pass two arguments.

To copy the project example files into your current directory do this:

$ cp /home/stu/erangel/public_html/cmps2240-f16/project/* . 

The integers typed in by the user are the second and third argument in the cmdline structure (the name of the executable is the first). Before doing anything move the base address to the command line structure to a persistant register (such as $s0) for safekeeping. The integers are read in as strings so you must grab the address to the first string and call atoi to convert the string into an integer. Do the same thing with the second string.

Once you have successfully grabbed and converted the integers, swap their values if k > n. The swap algorithm looks like this:

if (n < k) {
    temp = n;
    n = k;
    k = temp;
}

To implement swap you need a temp register to ensure that you do not overwrite registers that hold n and k. Compare the values of n and k with the "set if less than" instruction:

slt rd, rs, rt   # set rd=1 if rs < rt else rd=0

You may also deploy an in-place swap like this...

if (n < k) {
    n = n ^ k;
    k = k ^ n;
    n = n ^ k;
}

No temporary register needed.

See loops.s for sample usage of slt. Display n and k after the swap. To test:

$ spim -f 50.s 6 10    # swap since n < k
10 6
$ spim -f 50.s 10 6    # do not swap if n > k 
10 6

Phase 65

Objective: Code default values for n and k

Deliverable: 65.s

Description:

Copy 50.s to 65.s. Modify your code to set n=6 and k=4 as default arguments if no args are passed. Load values n=6 and k=4 into the appropriate registers before doing anything. If the user has passed arguments, verify that the arguments are numbers (start with character 1...9). If invalid, exit with an error message. If valid, overwrite the default values and continue the program. A program that implements what you need for 65% is fib.s from the Lab 3 code examples.

Your code should work regardless of the number of arguments that are passed. If fewer than two are passed, use the default values. The purpose of default values is to be able to run your program using SPIM as a debugger. This allows you to find and fix problems. The algorithm for this specification is shown below. The code that implements this algorithm should be inserted at the very top of your program.

n = 6;
k = 4;
if (arg_count == 3) {
    n = atoi(argv[1];
    k = atoi(argv[2];
}

To test:

$ spim -f 65.s 5 10  
10 5
$ spim -f 65.s    # if two args are not passed use default values 
6 4 

Phase 70

Objective: Compute n! and k!

Deliverable: 70.s

Description:

For 70% you will compute the factorials for n and k. The factorial function you should implement for 70% is iterative (uses a loop) rather than recursive.

The pseudo-code below shows the iterative algorithm.

int fac(n)  {
    int product = 1;
    for (int i = 1 to n) 
        product = product * i;
    return product;
} 

Under normal circumstances you would want to use a 64-bit register to hold n! since factorials get large very quickly. Unfortunately, SPIM does not support 64-bit integers (a 64-bit integer is the LONG INT type in C). The largest integer value in SPIM is a positive signed int (a 31-bit positive integer). Since this is the case you do not need to use the HI and LO registers to store the product. Thus you can use the MUL instruction to compute the product. Lab 3 covers looping and all the MIPS code you need to know to complete this phase.
Call fac using the MIPS jal instruction. Follow parameter passing conventions; i.e., load n into $a0 before making the call and put n! in $v0 before returning. Return to main using the MIPS jr $ra instruction.
To test:

$ spim -f 80.s 4 5   
5 4
120 24

Phase 80

Objective: Compute C(n,k) = n! / ((n-k)! k!)

Deliverable: 80.s

Description:

For 80%, write a function Cnk that computes 'n choose k' (the combination of n things taken k at a time) using the definition for C(n,k):

C(n,k) = n! / ((n-k)! k!)

You will need to use the MIPS div instruction. The result of div is in LO so use mflo to grab it:

DIV    rs, rt   # the quotient is stored in LO
MFLO   rd       # grab the quotient 

To follow conventions you should pass 'n' to Cnk in $a0, pass 'k' to Cnk in $a1 and return C(n,k) in $v0.

Your Cnk function will call the fac function that you wrote in phase 80. Since you are calling one function (fac) from another function (Cnk), you must construct a stack frame for Cnk to prevent the $ra register from being overwritten. See fact.s from the project examples.

NOTE: You will be marked down if you do not construct a call frame. You can compute C(n,k) without a call frame but in doing so you will duplicate your code to compute n!. That is bad coding. Since you have a stack frame you might as well save the result from fac(n), fac(k) and fac(n-k) onto the stack. Make room for 3 words if you do this. Thus, you don't need to worry about registers being overwritten.

Sample code:

jal fac           # n is loaded into $a0 and n! returned in $v0
sw  $v0, 0($fp)   # store n! on stack for safekeeping  

This phase is a little bit tricky. Be careful with your registers! To test:

$ spim -f 80.s 4 6  
6 4
720 24
15

Phase 90

Objective: Display row n of Pascal's Triangle for k = 0 to n

Deliverable: 90.s

Description:

For 90% write a function displayRow that displays row n of Pascal's triangle for k = 0 to n. Ignore the value for k that is passed in. Since the displayRow function calls Cnk, you must contruct a stack frame. Within displayRow write a loop that goes from k=0 to n. Within the body of the loop display the return value for Cnk(n,k). If you coded phase80 well, phase90 should be easy to complete.

To test:

$ spim -f 90.s 4 6  
6 4
720 24
15
1 6 15 20 15 6 1 

Phase 95

Objective: Display Pascal's Triangle

Deliverable: 95.s

Description:

For 95% you will write a function to display Pascal's Triangle as a right triangle for rows 0...n on the screen. Here is what the triangle should look like for n=5. Note that the top of the triangle is for n=0, k=0.

(n=0) 1
(n=1) 1  1
(n=2) 1  2  1
(n=3) 1  3  3  1
(n=4) 1  4  6  4  1
(n=5) 1  5 10 10  5  1 

Phase95 assumes that phase80 is coded as a function; e.g, calling displayRow(n) will display row n of Pascal's triangle. To complete phase95 you call displayRow in a loop that executes from i=0 to n.

To test:

$ spim -f 95.s 13 2 
13 2
1932053504 2
24
1 4 24 88 221 399 532 532 399 221 88 24 4 1 
1 
1 1 
1 2 1 
1 3 3 1 
1 4 6 4 1 
1 5 10 10 5 1 
1 6 15 20 15 6 1 
1 7 21 35 35 21 7 1 
1 8 28 56 70 56 28 8 1 
1 9 36 84 126 126 84 36 9 1 
1 10 45 120 210 252 210 120 45 10 1 
1 11 55 165 330 462 462 330 165 55 11 1 
1 12 66 220 495 792 924 792 495 220 66 12 1

The algorithm for this phase is as follows:

/* assume n is either the default value or has been read in from cmdline */ 
for (int i=0; i <= n; i++)
    displayRow(i);

Phase 100

Objective: Write recursive version of C(n,k)

Deliverable: 100.s

Description: For 100% you will replace the iterative version of C(n,k) with a recursive function. The recursive algorithm is shown below:

int C(n,k) {
    if (k==0) return 1;
    if (k==n) return 1;
    if (k==1) return n;
    return C(n-1,k) + C(n-1,k-1);
}

You should write a separate function for recursive C(n,k).
Name it Cnk_r:

Note that in this algorithm computing a factorial is not necessary. See pascal.cpp in project code for an implementation of the algorithm in C. Try to optimize the code as much as possible by not constructing a call frame for terminal calls. The goal is to compare the iterative and the recursive version. Time both programs with n=14 and k=2. Note that your factorial values will be incorrect due to a limitation in SPIM (see notes below) but anything below 14 will not give you a valid comparison. At 14 2 the timing results will look similar to this:

$ time spim -f 95.s 14 2   # iterative

output is here
...
...

real 0m0.047s
user 0m0.004s
sys 0m0.040s

$ time spim -f 100.s 14 2  # recursive

output is here
...
...

real 0m0.873s
user 0m0.048s
sys 0m0.820s  

You should see that even with optimization recursion is always worse than iteration - in this case roughly 19 times worse.

Warning:
SPIM does not support long ints (64 bits) or unsigned ints (the most significant bit is always reserved for the sign).
Thus, the largest positive integer is 2³¹ - 1,
which is 2,147,483,647.
13! = 6,227,020,800.
12! = 479,001,600 and thus is OK.
factorial you can compute without overflow is 12!.