CPS 104 Homework 3
Due February 18
Total Points 100
PART I (40 pts) Written Part, due in class
1. (10pts) Write a sequence of MIPS instructions for this C statement:
x[10] = x[13] + c;
Assume that c corresponds to register $t0 and the x is an array of words
and has a base address of 0x10001000.
2. (10pts) Book problem 3.9
3. (20pts) Pseudoinstructions are not part of the MIPS instruction set
but often appear in MIPS programs. For each pseudoinstruction below,
produce a sequence of actual MIPS instructions to accomplish the same thing.
You may need to use $at for some of the sequences. In the following,
big refers to an immediate number that requires 32 bits to represent
and small to a number that can be expressed using 16 bits.
a. (5pts) move $t5, $t3 # copy the content
in $t3 to $t5
b. (5pts) lw $t5, big($t3) # $t5 = Mem[$t3+
big]
c. (5pts) beq $t5, small, L # if ($t5 ==
small ) go to L
d. (5pts) bgt $t5, $t3, L # if ($t5
> $t3) go to L
A full list of real MIPS instructions can be found on the last page of
the textbook.
PART II (60 pts) Programming Part, due at midnight
1. (25pts) Collatz Conjecture
This problem has a mysterious history and it is not easy to explain
the attraction of mathematicians for it. Consider the following rule
that transforms a given positive integer n to another: if n
is even, it becomes n/2; if n is odd, it becomes
3n+1 . Starting at an arbitrary integer, we can repeatedly apply
the rule. For example: 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. It
has been conjectured that all integers eventually yield a 1. This is referred
to as the ``Collatz conjecture'', a.k.a. the ``3x+1'' problem. The conjecture
has been verified by computer up to 5.6*10^13. In this assignment,
you are to write a MIPS program to verify this conjecture to some extent.
Your program will read a positive interger n from the user and
repeatedly apply the rule above until it reaches 1, and output the number
of steps taken.
The only constraint in this assignment is that you must use two procedures to implement
the two kinds of transformation: One procedure will take an input
x and return 3*x+1, while the other procedure divides its argument
by 2. You are assured that any intermediate result will not exceed
the limit of a 32-bit integer.
2. (35pts) Recursive Function
Write a MIPS assembly program that computes the following recursive
function:
A(n) = A([n/2]) + A([n/3]), for n>=1;
A(0) = 1,
where [x] denotes the largest integer that is no bigger than x.
Your program should read an integer n (0 < = n < = 100) and output
A(n).
The submit name for the programming part of this assignment is hw3.
Last modified: Tuesday, Feb 4, 2003