Machine Problem 2, due Jul. 1

Part of the homework for CS:2630, Spring 2015
by Douglas W. Jones
THE UNIVERSITY OF IOWA Department of Computer Science

A function

The Hawk has no multiply instruction, but the Hawk monitor does have a multiply function, TIMES. Later, we'll discuss efficient multiply algorithms, but for now, ignore the multiply routine built into the monitor and consider the following recursive definition of unsigned multiplication:

0 × j = 0
1 × j = j
i × j = j/2 × i + (jj/2) × i

The first two cases are basis cases for the computation. The final recursive case involves splitting one of the multiplicands, j in half. Since j could be odd, the two halves are not necessarily equal. One half is j/2, while the other half is j – j/2.

Useful background

The instruction SRU R3,1 divides an unsigned integer, in R3, by 2, and the instruction SL R3,2 multiplies by 4. If you want to try to do a little optimization, MOVESL can be used to multiply by a power of two while moving a value from one register to another.

The Assignment

  1. Write a recursive function MULT, that uses the recursive algorithm discussed above. Specifically, except for the basis case, it must make two recursive calls, one for j/2 × i, and one for (j – j/2) × i.
  2. Write a main program that uses your multiply function to compute all products of integers in the range from 1 to 10, displaying the result as a 10 by 10 matrix of decimal values on the screen, where each integer value is 4 characters wide and there is a 4 character margin on the left. Test your program to make sure it works!
  3. Make sure your program is appropriately commented. This applies to an overall file header, the main program and the recursive subroutine. We strongly recommend that your comments be written as you write the code, not added as an afterthought, and we strongly recommend that you take the time to read your code through one last time before you make your final submission to make sure the commentary is appropriate.

All code you add must be at least as readable and at about as well commented as the code distributed above and in the notes.

An absolute rule: We do not do detective work to connect printed paper copies of assignments with the person who did the work. We assemble and print all assignments as part of the grading process. If your name is not included in the title line, you will not receive any credit.

A general remark: In addition to the recursion and if-then-else constructs you are likely to incorporate into your recursive subroutine, your program will have two nested for loops in the main program, and the main program will call several monitor routines within these loops as well as making calls to your subroutine. Note that the main program is itself merely a subroutine called by the Hawk monitor, and you should write it and comment it knowing this.

Finally, note that the first midterm is July 2. Several questions on this exam will assume that you have solved this machine problem.


Programming assignments will be submitted on-line using the on-line Online Coursework Submission tool provided by the Liberal Arts Linux server cluster. The user interface for this is awful, but but it works. Your source file must be named mp2.a (the name is case-sensitive). This is the name you will type in response to the File/directory name prompt. When the submission tool prompts for Course type CS2630. Select the assignment directory mp2. Remember, this is a Linux system, file names are case sensitive.

You must submit your work using the submit command from the a CLAS Linux machine. If you make repeated submissions, only the last one will count. Submissions must be in place before midnight on the indicated day.