Assignment 8, Solutions
Part of
the homework for 22C:60 (CS:2630), Spring 2013
|
unsigned int sqrt(unsigned int num) {
short result = 0;
short bit = 0x40000000; /* 1 << 30, the largest power of 4 */
/* make "bit" the highest power of four <= the argument */
while (bit > num) bit >>= 2;
/* now compute the square root from this initial value */
while (bit != 0) {
if (num >= result + bit) {
num = num - (result + bit);
result = (result >> 1) + bit;
} else {
result = result >> 1;
}
bit = bit >> 2;
}
return result;
}
This looks a lot like the traditional pencil and paper square root algorithm that my grandfather used to teach his high-school math students but that was no-longer taught by the time I took high-school math in the late 1960s. For an explanation (if you are curious), see the Wikipedia page, but note that you don't need to understand the code in order to do this assignment.
A problem: Give a translation of this code to Hawk assembly language, as a function that takes one parameter in R3 and returns the result in R3. Paper and pencil will suffice, if your code is correct, but we will be hard-nosed about syntax errors and legibility. Your code must include the original code in the comments, so that we can see what is going on! (1.5 points)
SQRT: ; expects R3 = num, an unsigned integer
; returns R3 = sqrt(num)
; uses R4 as result
; uses R5 as bit
; uses R5 as a temporary
LIS R4,0 ; result = 0
LIW R5,1<<30 ; bit = the largest 32-bit power of 4
; make "bit" the highest power of four <= the argument
SQRLP1:
CMP R5,R3
BLE SQREX1 ; while (bit > num) {
SR R5,2 ; bit = bit >> 2
BR SQRLP1 ; }
SQREX1:
; now compute the square root from this initial value
SQRLP2:
TESTR R5
BZS SQREX2 ; while (bit != 0) {
ADD R6,R4,R5 ; temp = result + bit
SRU R4,1 ; result = result >> 1
CMP R3,R6
BLT SQREIF ; if (num >= temp) {
SUB R3,R3,R6 ; num = num - temp
ADD R4,R4,R5 ; result = result + bit
SQREIF:
SRU R5,2 ; bit = bit >> 2
BR SQRLP2
SQREX2: ; }
MOVE R3,R4
JUMPS R1 ; return result
a) 99 (it can be done in 4 instructions) (0.2 points)
ADDSL R3,R3,1 ; R3 times 3
ADDSL R3,R3,5 ; R3 times 33
b) 999 (it can be done in 4 instructions) (0.2 points)
Doing it by the book gives this:
ADDSL R3,R3,3 ; \ R3 times 27 = 9 x 3 ADDSL R3,R3,1 ; / MOV R1,R3 ; \ R3 times 37 = 5 + 32 ADDSL R1,R1,2 ; | ADDSL R3,R1,5 ; /But there are tricks, that are not obvious that give solutions like this one (but the previous solution is good enough):
ADDSL R3,R3,3 ; R3 times 9 MOVSL R1,R3,7 ; \ R3 times 111 = 128-17 ADDSL R3,R3,4 ; | SUB R3,R1,R3 ; /
c) 9999 (this one is harder) (0.4 points)
Doing it by the book suggests we ought to try finding the prime factors of the multiplier first:
9999 = 3 × 3 × 11 × 101
Not bad, but note that we have single instruction tricks for multiplying by 3, 9 and 33, so we can avoid multiplying by 11 if we write this:
9999 = 3 × 33 × 101
Now, how do we handle multiplying by 101? That is more fun. 101 is 1100101 in binary, so we can apply brute force binary multiplication by 101 and then follow up with the two final multiplies to get this:
MOV R1,R3 ADDSL R3,R1,1 ; times 11 ADDSL R3,R1,3 ; times 11001 ADDSL R3,R1,2 ; times 1100101 = times 101 ADDSL R3,R3,1 ; R3 times 3 ADDSL R3,R3,5 ; R3 times 33
Note that section 14.6 of the Hawk manual discusses reciprocal multiplication as a way to do efficient division by constants.
A problem: Give Hawk code to multiply R3 by 1/12. (0.7 points)
Here, we use brute force methods from section 14.6:
; R3 = R3 / 12 = R3 * 0.00010101010101010101010101010101011 MOVE R1,R3 ; R3 = R1 * 1.0 (make copy of original R3) SRU R3,1 ; R3 = R1 * 0.1 ADDSRU R3,R1,2 ; R3 = R1 * 0.011 ADDSRU R3,R1,2 ; R3 = R1 * 0.01011 ADDSRU R3,R1,2 ; R3 = R1 * 0.0101011 ADDSRU R3,R1,2 ; R3 = R1 * 0.010101011 ADDSRU R3,R1,2 ; R3 = R1 * 0.01010101011 ADDSRU R3,R1,2 ; R3 = R1 * 0.0101010101011 ADDSRU R3,R1,2 ; R3 = R1 * 0.010101010101011 ADDSRU R3,R1,2 ; R3 = R1 * 0.01010101010101011 ADDSRU R3,R1,2 ; R3 = R1 * 0.0101010101010101011 ADDSRU R3,R1,2 ; R3 = R1 * 0.010101010101010101011 ADDSRU R3,R1,2 ; R3 = R1 * 0.01010101010101010101011 ADDSRU R3,R1,2 ; R3 = R1 * 0.0101010101010101010101011 ADDSRU R3,R1,2 ; R3 = R1 * 0.010101010101010101010101011 ADDSRU R3,R1,2 ; R3 = R1 * 0.01010101010101010101010101011 ADDSRU R3,R1,2 ; R3 = R1 * 0.0101010101010101010101010101011 ADDSRU R3,R1,4 ; R3 = R1 * 0.00010101010101010101010101010101011