I strongly recommend against looking at the solutions for the problems below until you have attempted the problems. (That's why I put the solutions on separate web pages.) There is no need to print the solutions out now; they'll be here when you come back, at least through the date of the final exam.
Note: In the ASCII character set, the code for a space is 40 (base 8). Now, we would normally put about three ASCII characters in a 24-bit word, but for the purposes of this problem for now let's just say that each character is in its own word. (We could more appropriately do the more realistic version of this as a PDP-11 problem, which has separate bytes and words and other complications.)
Note: The bitwise AND of an integer with 1 discards all but its least significant bit. If this bit is zero, the number is even; else it is odd.
Note: For ease of reading, the constants 1, 2, and 3 are stored in register 1, 2, and 3, respectively.
MOV# 1, R1
MOV# 2, R2
MOV# 3, R3
MOV 2000, R4
LOOP: BIT R4, R1
BEQ L2
MUL R3, R4
ADD R1, R4
BR L3
L2: DIV R2, R4
L3: CMP R1, R4
BGT LOOP
HALT
Suppose that you were sceptical of this formula and no one showed you a proof. You try it for a few cases and it works, but you are having difficulty finding a proof yourself. Before looking harder for a proof you'd like to verify it for a few hundred cases or more, by computer.
Write a program in the VELMA assembly language which verifies this equation (i.e. that the two sides are indeed equal), for 0 <= n < N. N is stored in memory location 500.
The answer should be in R0 when your program HALTs. If overflow occurs at any point in your calculation, your program should HALT with -2 in R0. Otherwise, if it finds a counterexample to this formula, it should HALT with the n counterexample in R0 and with carry set (and overflow clear). If it verifies the formula for all n, 0 <= n < N, it will HALT with -1 in R0.
Your program needn't be especially well-commented but you should explain your use of registers and anything else particularly unclear. Do not assemble your code; leave it in symbolic form.
| .ORG 100 | |
| MOV X, R2 | |
| MUL R2, R2 | |
| BVS OVERFLOW | |
| MOV Y, R4 | |
| MUL R4, R4 | |
| BVS OVERFLOW | |
| SUB R4, R2 | |
| MOV R2, W | |
| HALT | |
| OVERFLOW: | CLR R0 |
| MOV R0, W | |
| HALT | |
| X: | .WORD 22 |
| Y: | .WORD 33 |
| W: | .WORD 0 |
(a) Describe simply (in English) what it does (in general, for any values of X and Y).
(b) Assemble the program into unsigned 24-bit octal numbers.
MOV N, -(R6) MOV #A, -(R6) ; (actually this requires two instructions) JSR ROUTINE INC R6 INC R6You return the computed sum in R0. Your subroutine may thus use R0 as a scratch register, but any other registers used must be pushed and restored.
Your subroutine is required to check for overflow. If none of the addition operations overflows, your subroutine must return the sum in R0, and with the V condition code clear. If any of the addition operations overflow, your subroutine must return with the V condition code set, and in that case it doesn't matter what the final contents of R0 is. In the case of overflow, the caller will ignore the returned contents of R0; thus your subroutine may return immediately. (So there would actually be a BVS instruction between the JSR and the ADD in the calling sequence above.)
You need not handle the case of zero-sized arrays; the count (second argument) must be positive. You are not required to handle any kind of incorrect use of your subroutine.
Your program needn't be especially well-commented but you should explain your use of registers and anything else particularly unclear.
Do not assemble your code; leave it in symbolic form.
'B' is an array of another 308 items starting at memory location 560 (right after 'A') and organized similarly.
The distance between points A[i] and B[i], for a particular i, is
Write a program in the VELMA machine language to find the value of i (from 0 to 30) such that A[i] and B[i] are the closest to each other. The result should be in R0 when you HALT.
Note that you do not have to take square roots to write this program. sqrt(p) < sqrt(q) if and only if p<q. So although finding the actual distance requires taking a square root, comparing distances does not; your register corresponding to a variable min will actually store the square of the minimum distance so far, rather than the actual minimum distance so far.