I need help implementing a simple recursive function that finds the G reatest C
ID: 3600230 • Letter: I
Question
I need help implementing a simple recursive function that finds the
G reatest C ommon D ivisor of two values.
Here’s the pseudocode:
// GCD(50, 15) => 5
// GCD(13, 12) => 1
// No local variables needed
// Assume a and b are always positive and b is nonzero
GCD(a, b) {
R0 = a; // a must be put in R0
R1 = b; // b must be put in R1
UDIV(); // UDIV is a trap that divides and mods
// R0 = a / b
// R1 = a % b
if (R1 == 0) { // if((a % b) == 0)
return b;
} else {
return GCD(b, R1);
}
}
This function uses the trap called UDIV included in Complx. Unlike other traps you’ve
used (such as GETC, OUT, PUTS, and HALT), this trap is not built into LC3 but is an
external plugin you must include (the file is not provided so write the code assumming it is included in the top of the file as an @plugin comment.). The way UDIV works is that it accepts two arguments through registers R0 and R1 and returns the
division and modulo of those two in the same registers, as shown in the comment in the
pseudocode. R2-R6 are not modified, R7 is of course overwritten for the return address.
Thanks.
Current code I have written is as follows and is only 80% correct:
; DO NOT REMOVE THIS LINE
;@plugin filename=lc3_udiv vector=x80
.orig x3000
LD R6, STACK
; TODO: Setup GCD call with arguments A and B
LD R0, A ;R0 = A
LD R1, B ;R1 = B
STR R0, R6, -1
STR R1, R6, 0
LDR R6, R6, -1
JSR GCD
; TODO: Store the return value in ANSWER
LDR R0, R6, 0
ADD R6, R6, 2
ST R0, ANSWER
HALT
A .fill 20
B .fill 16
ANSWER .blkw 1
STACK .fill xF000
GCD
; TODO: Implement GCD here
ADD R6, R6, -4
STR R7, R6, 2
STR R5, R6, 1
ADD R5, R6, 0
LDR R0, R5, 4
LDR R1, R5, 5
UDIV
AND R1, R1, 0
BRNP N
LDR R0, R5, 5
BR END
N
LDR R6, R6, -1
LDR R2, R5, 5
STR R6, R2, 0
STR R6, R1, 1
JSR GCD
LDR R0, R6, 0
BR END
END
STR R0, R5, 3
LDR R7, R5, 2
ADD R6, R5, 3
LDR R5, R5, 1
RET
.end
Explanation / Answer
the code is correct and fxed
;@plugin filename=lc3_udiv vector=x80
.orig x3000
LD R6, STACK
; TODO: Setup GCD call with arguments A and B
LD R0, A ;R0 = A
LD R1, B ;R1 = B
STR R0, R6, -1
STR R1, R6, 0
LDR R6, R6, -1
JSR GCD
; TODO: Store the return value in ANSWER
LDR R0, R6, 0
ADD R6, R6, 2
ST R0, ANSWER
HALT
A .fill 20
B .fill 16
ANSWER .blkw 1
STACK .fill xF000
GCD
; TODO: Implement GCD here
ADD R6, R6, -4
STR R7, R6, 2
STR R5, R6, 1
ADD R5, R6, 0
LDR R0, R5, 4
LDR R1, R5, 5
UDIV
AND R1, R1, 0
BRNP N
LDR R0, R5, 5
BR END
N
LDR R6, R6, -1
LDR R2, R5, 5
STR R6, R2, 0
STR R6, R1, 1
JSR GCD
LDR R0, R6, 0
BR END
END
STR R0, R5, 3
LDR R7, R5, 2
ADD R6, R5, 3
LDR R5, R5, 1
RET
.end
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.