Perse Studio

Independent-learning super-curriculum projects: reading, research and ideas shared by Perse students

Collatz Sequence using Assembly Language on Little Man Computer

Joshua S, Y10

The Collatz Sequence starts with any positive number and either halves it if it is even or triples it and adds one if it is odd, continuing until it reaches 1 after which it stops. The unproven theory says that for all positive integers this sequence should eventually reach one.

When I first looked at the collatz sequence problem for purposes of assembly language, the first thing I did was decompose the required algorithm into its component parts; an even/odd checker, a part that would triple a number and add 1, a part that would halve a number and a part that would stop the algorithm once one was reached. I then realised that it was nowhere near as hard as it seemed – each of the four main elements were fairly simple, the hardest being the division. Mr Gwilt demonstrated the method to achieve the odd/even checker in class. The triple and add one was easy – simply add the number to itself twice and add one, although this exact code isn’t demonstrated in my code below, as I also integrated the stop code into the odd function*. The division, however, required a more complicated algorithm, and two variables. It worked by loading the value of x and storing it as y​, then looping code that would load y, subtract one, and store the new value. It would then undergo a check in which y was doubled and then x​ subtracted – if y was half of x​, the program would divert to another label called output, which would output x​ and return to loop​, else it would continue looping until it got there.

* by subtracting one from the accumulator (which I had just loaded with the current value of x, the variable used to hold the current term) then using the BRZ command, I could check if x was currently 1, then divert to the stop code if it was. Since I had subtracted one, I had to add two to get the triple-add-one effect, and store a new x.

You can try out Little Man Computer (by Peter Higginson) online here:

https://peterhigginson.co.uk/lmc/

Comments are closed.