CS 3410 Spring 2017

**Due:** Upload your implementation of the Iterative and/or Recursive Hailstone by 11:59pm on Monday, March 13, 2017

**Optional:** If you upload your memoized version, we will run it through the auto-grader, too.

(Only the highest of the iterative, recursive, or memoized scores counts for this lab grade, but *all three* 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 3*n*+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 **one** (optionally, more) of the methods below (please **do not** submit
MIPS code with any form of main function).

**Iterative hailstone:**An efficient approach for computing the answer for just a single sequence.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; }

**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); }

**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 the iterative, 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.

It is an open question whether all starting points eventually converge to 1 or not. The Collatz conjecture states that all positive integers converge to 1, but this isn't yet proven. For this project, you can assume all numbers converge — if you find one that doesn't you get an automatic A for the project. You can watch this video or find links to more reading on the Wikipedia page for the Collatz conjecture.

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 this project, 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 to 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) |