IC220 Spring 2011 Project #1: Pernicious Pell? Due Fri Feb 11
This project must
be completed independently (unlike regular assignments).
This means
collaboration between students is not permitted. Online sources (aside
from IC220’s website) are also prohibited.
You may consult your notes, textbook, and the instructor. See the
instructor for help or clarification.
Background: You have already had experience with writing simple
MIPS programs and testing them with SPIM.
In this project you will review and integrate your understanding of:
1.
General MIPS programming
2.
Function calls
3.
Recursion
Task: Write a recursive MIPS
program that computes a term in the “Pell number” sequence, a famous
mathematical sequence. This sequence of
numbers (0,
1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, 13860, 33461, …) can be computed with
the following recursive function:
int pell
(int N) {
if (N == 0)
return 0;
else if (N == 1)
return 1;
else
return 2*pell(N-1) + pell(N-2);
}
Thus, pell(0) = 0, pell(1) = 1, pell(2) = 2, pell(3)
= 5, pell(4) = 12, …. pell(10) = 2378. Be
sure you aren’t off by 1 in the sequence!
There are much more efficient ways to compute the Pell
series, but to solidify your understanding of recursion and the stack you are required
to have a recursive solution.
Specifics: Starter code is provided: ProjectStarterCode.asm. (right-click and use
Save As) Start with this!!!! You should do the following with this code:
1. Modify the main function to:
Print a welcome message that
includes your name
Call the pell procedure to compute the Pell term
requested by the user
(NOTE: see the sample code at the
end of this writeup – shows complete program with functions. This code is NOT
the same as the starter code that is given to you.)
Print the calculated term after it
has been returned to the main function
2. Write a procedure called pell that:
Recursively
calculates the Nth Pell term, where N comes from the argument passed in
register $a0.
Returns
the value in $v0.
You do not have to write
this function from scratch – just translate the C code given above!
3. Test your code with SPIM.
Sample screen shot of completed program:
(more on back)
Tips:
1.
Start early! Recursion can be tricky. Allow time to get help from the instructor if
needed.
2.
But don’t make this harder than it needs to be! Your primary task is to simply translate the C code above to a
MIPS function. While this function is
recursive, really this is just another example of a nested procedure – follow
the rules for nested procedures and recursion will take care of itself.
3.
You
will need to use the stack.
Before you begin, make sure you understand how to do this and what will
need to be saved and restored with the stack.
4.
This
assignment requires you to write only about 30-40 carefully chosen assembly
instructions. If you have many more than that, you probably
are misunderstanding what should be done.
5.
The
following material may be helpful to you:
·
Lecture
notes on MIPS procedure calls, and SPIM
·
Homework,
especially exercises 2-35 thru 2-37
·
Lab
#1, where you first used SPIM
·
SPIM reference material: http://www.usna.edu/Users/cs/lmcdowel/courses/ic220/spim/
6.
Use
Alt-PrintScreen to generate a screenshot.
7.
An
error message like “Can’t add 8 bytes to Lstack” means you are stuck in
infinite recursion.
8.
Use
the starter code!
9. In SPIM,
the value of the registers are displayed by default in hex. You can change this
to decimal via the menu option:
Simulator->Settings, uncheck "General registers in
hexadecimal"
10. Debugging: if it doesn’t work, try running
your code for very simple cases (N=0,N=1,N=2,N=3,N=4,etc.). Then try single-stepping through the simplest
case that doesn’t work – what is wrong?
11. The next page contains another
useful example, demonstrating how to do function calls. Understanding this before you start will save
you time!
Deliverables:
(1 through 3 handed in, stapled together in the following order)
1) A cover sheet with your feedback. (10
pts)
2) Screenshot showing your program
computing pell(15) (10 pts)
3) Printout of your recursive assembly
code (60
pts)
4) .asm file saved to your X drive (20
pts)
Place this file in your IC220
directory. Name it
Project1-section-lastname.asm
(e.g., Project1-1001-smith.asm).
Extra credit (up to 5 pts each):
1. Write a new program to calculate the Pell numbers
in a non-recursive manner. Turn in this
program and a screenshot showing the calculation of Pell(30).
2. Read ahead about floating point registers, then write
a new program to calculate the Pell numbers using the floating point registers
to keep track of the calculations (you can assume that you only have to deal
with numbers with no fractional part).
Why might you want to do this?
# Example code
demonstrating how to call a function as part of
# a complete SPIM program.
.data
str_1: .asciiz
"Enter a number=> "
str_2: .asciiz
"Result=> "
.text
.globl main
main:
# Print the prompt
la
$a0, str_1 # 'load
address' of string to print
li
$v0, 4 # syscall
#4 = print string
syscall
# Read an integer from the user
li
$v0, 5 # syscall
#5 = read integer
syscall # read int, result
goes in $v0
# Call a function to add that number
together with 13
addi $a0, $zero, 13 # Set up first argument to
function (13)
move $a1, $v0 # Set up second argument
(the number entered by user)
jal doAdd # do add, result now in
$v0
move $s0, $v0 # save result for later (b/c
v0 clobbered below)
# Print string announcing the result
la
$a0, str_2 # 'load
address' of string to print
li
$v0, 4
syscall
# Print actual result
li
$v0, 1 # syscall
#1 = print integer
move
$a0, $s0 # tell
syscall what # to print
syscall
# terminate the program
li $v0, 10
syscall
# Define the (very simple)
function we use
# Notice that this goes
OUTSIDE of main
doAdd:
add $v0, $a0, $a1 # add two arguments
jr $ra # return