AARCH64 has a lot of general purpose registers. How many? Lets see.

While multiplication is defined in the context of repeated addition, implementing it that way algorithmically is not nearly as efficient as some other approaches. One algorithm for multiplication that is an order of magnitude faster is to halve one number while doubling the other. I gave myself the challenge of implementing this algorithm in AARCH64 Assembly, and it was not too hard.

Now that I can run the Knuth version of the Insertion sort via MIXAL, I want to convert it to AARCH64 Assembly. What I am going to try to do here is a line by line translation. This is not necessarily how I would write the insertion sort in AARCH64 assembly, but rather a direct translation of the MIXAL version.

A debugger is a wonderful tool for understanding what actually happens in a piece of code. Donald Knuth’s coding in TAOCP is archaic enough that I do not understand it just by reading through. This is due to a combination of my unfamiliarity with MIXAL, as well as some of the coding conventions he’s chosen. So, I’m going to step through the MIXAL code in mixvm, and annotate what I find.

With the information gained in last posts investigations, I now know how to turn the smaple code of the insertion sort out of TAOCP into runnable code.

The examples in The Art of Computer Programming (TAOCP) are in the MIXAL programming language. In order to see these examples run, I want to install the tools on my Fedora box. They are packaged as RPMS, so this is trivial. Here are the steps to run and debug a sample program in MIXAL.

For the next couple tasks I want to do in assembly, I need to be able to inspect an array of numbers. This is useful for debugging searching and sorting algorithms. Since my last attempt to convert binary to ASCII was so ugly, I figured I would clean that up at the same time.

It turns out I can use the reverse code as well.

This is not my finest code. It is the worst case of “just make it work” I’ve produced all week.

But it runs.

What does it do? It takes the first binary number in an array, and converts it to decimal. It assumes that the number is no more than 3 digits long.

It divides that number by 100 to get the 100s digit. Then it multiples that number by 100, assuming that it has gotten truncated. It subtracts that value from the original number to chop off the 100s digit, and divides the result by 10 to get the 10s digit.