Projects may be done in a pair or individually and in accordance with the Projects: I&P$.$

Collatz: Project Description

For this project, you are to use subroutines to complete the LC$-3$ assembly language program template that we provide.

The Collatz Conjecture, also known as the $3$x$+1$ conjecture, is a popular math conjecture that's not yet proven $($see WikiLinks to an external site., online toolLinks to an external site.$).$ It states that any positive number can be reduced to $1$ using the simple algorithm mentioned in the COLLATZ$\_$STEPS description below.

First, download the program template: HERE Download HERE. Read the documentation in that text file after reading this page.

Subroutines You're to Complete

Complete the subroutines in the order listed below.

Note the COLLATZ$\_$STEPS subroutine is to be completed last since it uses subroutines MUL$3$ADD$1$ and DIVIDEBY$2.$

You must use the registers specified in the program template for each subroutine's argument and return value.

This ensures your code will work with our main program and testers.

Be careful to properly handle the return address in R$7$ or else your program will fail!

Properly preserve the register R$0$ wherever required or else the test harness will fail!

$1.$ MUL$3$ADD$1$ subroutine $(7$ pts$)$

$(6$ pts$)$ Implement the subroutine MUL$3$ADD$1$ as specified in the program template.

The subroutine should return the result $(3*$ A$)+1$ given A as the input.

$(1$ pt$)$ Properly preserve the register values as needed.

$2.$ DIVIDEBY$2$ subroutine $(11$ pts$)$

$(10$ pts$)$ Implement the subroutine DIVIDEBY$2$ as specified in the program template.

The subroutine returns the RESULT of N $/2$ given an even positive integer N as input

and using the following algorithm:

RESULT $=0$

while N $>=2$

subtract $2$ from N

increment RESULT by $1$

$(1$ pt$)$ Properly preserve the register values as needed.

$3.$ COLLATZ$\_$STEPS subroutine $(11$ pts$)$

$(10$ pts$)$ Implement the subroutine COLLATZ$\_$STEPS as specified in the program template.

This subroutine calculates the number of STEPS required to transform a positive integer X to $1$ using the following algorithm:

STEPS $=0$

while X is not equal to $1$:

if X is even $->$ decrease X to X$/2$

if X is odd $->$ increase X to $3*$ X $+1$

increment STEPS by $1$

You are to use the MUL$3$ADD$1$ and DIVIDEBY$2$ subroutines in this subroutine.

$(1$ pt$)$ Properly preserve the register values as needed.

Code We've Provided

We provide a program template file for you to complete. Please refer to the Project Description section above for the link to download the program template. The template file is structured as follows:

Header comments that you need to fill in and boxes you need to mark.

Descriptions of each subroutine, followed by a placeholder where you need to implement the subroutine's LC$-3$ assembly code. You are to implement each subroutine only within its designated regions.

Three helper subroutines $($PRINT$\_$DIGIT, PRINT$\_$INT, COLLATZ$)$ are provided to help you check your code.

The main section includes tester subroutines to test the subroutines you're coding. You can skim through this section to understand what the testers are doing. A sample output of our tester is provided below. Do NOT modify any lines beyond the start of the main section. Doing so can break our code.

Except for the labels to call the helper subroutines, DO NOT USE ANY OF THE OTHER LABELS in our code's main section.

Do not change the tester code in the main section to do additional tests. Additional tests can be done by editing the simulator's register and memory values instead of changing our tester code.

If you've successfully implemented all three subroutines, our testers will display the output below. If you see the message "Check for callee saving failed" as part of the tester outputs, then one or more registers are not being correctly preserved.

$32*3+1=97$

$196/2=98$

Steps for reaching $1$ from $1982=99$

Number of Collatz Steps for $15,14,13,...,1$

$17$

$17$

$09$

$09$

$14$

$06$

$19$

$03$

$16$

$08$

$05$

$02$

$07$

$01$

$00$

Grading and Submission

$(4$ pts$)$ The program has good commenting and a good coding style.

$(7$ pts$)$ The MUL$3$ADD$1$ subroutine is successfully completed.

$(11$ pts$)$ The DIVIDEBY$2$ subroutine is successfully completed.

$(11$ pts$)$ The COLLATZ$\_$STEPS subroutine is succ