CS3410
Due: Upload your implementation of the Recursive Hailstone by noon on Saturday October 8, 2016
Optional: If you upload your memoized version, we will run it through the auto-grader, too.
(Only the recursive score counts for this lab grade, but both the recursive and the memoized versions will be turned in again and graded again as part of your next project, so it is in your best interests to get feedback early on.)
In this lab you will re-visit the hailstone programs that you worked on in a previous project.
A hailstone sequence is defined as follows: start at any
positive integer n; if n is even, divide it by 2 to
get n/2; else triple it and add one to get 3n+1; then
repeat with the new number. You will implement the hailstone
function, which counts how many steps it takes for the hailstone
sequence to converge to 1 from a given starting point. For instance,
hailstone(40) returns 8 because the sequence starting at
40 converges in 8 steps: 40, 20, 10, 5, 16, 8, 4, 2, 1. And
hailstone(31) returns 106 due to its long and chaotic
sequence: 31, 94, 47, 142, 71, 214, ..., 3077, 9232, 4616, 2308, 1154,
577, ..., 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1.
There are several ways to compute the hailstone function. You will implement two of the methods below (please do not submit MIPS code with any form of main function).
Recursive hailstone: Simple but inefficient. Logisim will be too slow to use this version except when the sequence converges quickly.
int r_hailstone(int n) {
if (n == 1)
return 0;
else if ((n % 2) == 0)
return 1 + r_hailstone(n/2);
else
return 1 + r_hailstone(3*n+1);
}Iterative hailstone: An efficient approach for computing the answer for just a single sequence. You already implmented this one, and do not have to do it again!
int i_hailstone(int n) {
int i = 0;
while (n != 1) {
i = i + 1;
if ((n % 2) == 0)
n = n/2;
else
n = 3*n+1;
}
return i;
}Memoization hailstone: For computing the answer for more than one sequence, it makes sense to remember previously computed answers since many sequences overlap. So if hailstone(40) has already been computed, then it is easy to compute hailstone(160) since its sequence is identical to the one for 40 after just 2 steps. This memoization version is essentially the same as the recursive version but takes two extra arguments: an array log_array of previously computed answers (should be initialized to all zeros), and the number of entries size in the array.
Note: the memoized hailstone does not allocate or initialize the array. It assumes that the function calling m_hailstone has already created an array of size size and initialized every entry to zero.
int m_hailstone(int n, int log_array[], int size) {
if (n < size && log_array[n] != 0) /* non-zero means we already computed this */
return log_array[n];
if (n == 1)
return 0;
else {
int i;
if ((n % 2) == 0)
i = 1 + m_hailstone(n/2, log_array, size);
else
i = 1 + m_hailstone(3*n+1, log_array, size);
if (n < size)
log_array[n] = i; /* save answer for reuse later */
return i;
}
}Implement these the recursive and memoized versions of the hailstone function using MIPS assembly code. They must all work on your processor in Logisim, though you will have be careful when testing to selecting starting values that converge in a reasonable time.
Your hailstone functions are just that: functions. They should get
their inputs from registers $a0 and $a1 and
they should return their results via register $v0. To
test the functions, you will nead to create a "main" program which
initializes the stack (by setting $sp
and $fp to something reasonable and usable), puts some
input in the argument registers, then calls the function
via JAL. The hailstone functions never make system calls
or any other function calls that could possibly read input from the
user. Your main program could if you managed to wire up a keyboard
though.
The MIPS Program ROM component has a built-in assembler that
understands all of the instructions you will implement. The syntax is
standard MIPS syntax. Labels are case sensitive, everything else
ignores case. Anything following a pound ('#') is a
comment. In project 1, you will only use a few of the instructions
listed here.
The instruction syntax is the same as given in the MIPS standard
(and different from the output of gcc and many other
tools). Registers are written as $0, $1,
..., $31, and the destination register goes on the left,
followed by source registers and immediate values on the right. Most
integer arguments (immediates, shift amounts, jump targets) can be
specified in hex (i.e. 0x12ab), in decimal (i.e. 1234 or -1234), a
label, or the special constant PC. The assembler will
replace PC with the address of the instruction
itself. Most constants have some restrictions: jump destinations must
have the same upper 4 bits as the PC+4, and must be a
multiple of 4; branch destinations must be a multiple of 4 and fit in
a signed 18 bit immediate; etc. As a special case, when a branch
target is specified symbolically as a label, the assembler will
automatically subtract the current PC value to obtain a signed
offset.
By default, the first instruction will be placed at address 0, and subsequent instructions are placed at at addresses 4, 8, 12, etc.
Assembler directives. The Program ROM assembler understands two standard MIPS assembler directives, .text and
.word, both of which take integer (hex or decimal) arguments. For example, .text 0x50000000 will
direct the assembler place subsequent instructions starting at address 0x50000000. And .word 0x24030005
directs the assembler to use the value 0x24030005 as the next machine instruction, which happens to be the machine
code for ADDIU $3, $0, 5.
Symbolic register names. The assembler built into the MIPS Program ROM accepts
standard MIPS register names: $zero, $at, $v0, $v1, $a0 - $a4, $s0 - $s7, $t0 -
$t9, $k0, $k1, $sp, $gp, $fp, and $ra.
Some examples of instructions are:
| Immediate Arithmetic | ADDIU $12, $0, PC |
| Register Arithmetic | ADDU $13, $0, $20 |
| Immediate Load | LUI $14, 0x123 |
| Shifts | SLL $13, $13, 2 SLLV $15, $14, $3 |
| Jumps | J 0x24 J my_label JR $5 JALR $31, $5 JALR $5 |
| Branches | BEQ $5, $6, -12 BEQ $5, $6, my_loop_top BLEZ $9, 16 BLEZ $9, my_loop_done |
| Memory Load/Store | LW $12, -4($30) SW $12, 0($30) |