Collatz Exercise

 

Objective

To get experience writing ARM assembly code for the GBA.
 

The Collatz Conjecture

The Collatz conjecture states that if you take any positive integer $N$ and repeatedly follow the following process:
  1. If $N$ is even, divide it by 2.
  2. Otherwise multiply it by 3 and add 1.

Eventually $N$ will reach 1.

For instance, if we start with $N = 10$, then we get the following sequence of numbers:

10
5
16
8
4
2
1

The number of steps it takes for 10 to reach 1 is 6.

This conjecture has been shown to hold true for numbers up to $2^{60}$ but has never been proven.

 

Task

For this lab, you will write an ARM assembly function to calculate the number of steps it takes any number to reach 1.

  1. Start by downloading a GBA skeleton program with an empty collatz function: 
    wget https://ianfinlayson.net/class/cpsc305/labs/collatz.tar.gz
tar xvf collatz.tar.gz
  2. Compile the program so that you can see you have everything set up correctly: 
    gbacc collatz.s main.c
  3. Run the program.gba program this creates. It should print a list of 20 results "1 -> 1", "2 -> 2" etc. The empty collatz function just returns its argument unchanged.
  4. Edit the collatz function in collatz.s to do the calculation as described above.

When you are done, your program should produce the following output:

The output of this lab showing the function called for 1 through 20. The outputs are: 0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7
 

Submitting

When you are done, please submit the assembly code under the assignment in Canvas.