The greatest common divisor (GCD) of two integers is the largest positive intege
ID: 3766617 • Letter: T
Question
The greatest common divisor (GCD) of two integers is the largest positive integer that divides both evenly. Thus GCD(100, 240) is 20, GCD(34, 27) is 1 and GCD(0, 14) is 14. A standard elementary programming exercise computes the GCD of M and N (both > 0) without using division (which is slow) by the following method: while (MN) do if (N > M) then N = N _m else M = M - N ; GCD = N; Write a separately assembled function GCD to compute the GCD of the integers in AX and BX using the algorithm and return the value in AX. Treat the cases M or N = 0 or negative as special cases. (.GCD (-M, N) = GCD(M,N); GCD(-32768,-32768)= -32768, GCD(-32768,N) = GCD(16384,N) if N -32768. GCD(0,0) should be infinity, but return 0.) Be sure to test your procedure as completely as possible.Explanation / Answer
GCD Procedure:
----------------------------------------
GSD PROC
PUSH AX ;push M on stack. M in AX
PUSH BX ;push N on stack. N in BX
CHECKNEGATIVE:
CMP AX,0 ;checks if M<0
JB MNEGATIVE ;if M is negative
CMP BX,0 ;checks if N<0
JB NNEGATIVE ;if N is negative
GCDCALCULATION: ;calculation of GCD
CMP AX,BX ;compare M and N
JMP EQUAL ;if M=N, covers also M=N=0
JNE CALCULATION ;if M<>N, execute CALCULATION
CALCULATION:
CMP BX,AX ;check if N>M
JG SUBM
SUB AX,BX ;M=M-N, if N<M
JMP GCDCALCULATION
MNEGATIVE:
;code to convert to positive
JMP CHECKNEGATIVE
NNEGATIVE:
;code to convert to positive
JMP GCDCALCULATION
SUBM:
SUB BX,AX ;N=N-M, if N>M
JMP GCDCALCULATION
EQUAL: ;if M=N, then GCD=N
MOV AX,BX ;sets AX to N
POP AX ;AX=GCD
STOP:
RET
GCD ENDP
--------------------------------
Note: This is a generalised procedure. You will need to add checks for special values like -32768.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.