Recursion program to find Greatest Common Denominator (GCD)
Description:
Write an x86 assembler assignment program that uses recursion to find the Greatest Common Denominator (GCD) between two non-zero unsigned numbers. Recommend you use the Euclid GCD algorithm for this purpose. If zero or negative value is input, the program must print out an error message and exit.
Example Sessions:
Solution:
INCLUDE Irvine32.inc
.data
header DB "Greatest Common Divisor Program", 0
help DB "Input two unsigned integers > 0", 0
prompt1 DB "Input unsigned integer #1: ", 0
prompt2 DB "Input unsigned integer #2: ", 0
result DB "Greatest common divisor is: ", 0
error DB "Error - Input is not greater than zero", 0
.code
main PROC
; Print program header
mov edx, OFFSET header ; load string address
call WriteString ; print the string
call CrLF ; print a newline
; Print program help
mov edx, OFFSET help ; load string address
call WriteString ; print the string
call CrLF ; print a newline
; Prompt for first number
mov edx, OFFSET prompt1 ; load string address
call WriteString ; print the string
call ReadInt ; read the first integer
mov ebx, eax ; save in ebx
; Prompt for second number
mov edx, OFFSET prompt1 ; load string address
call WriteString ; print the string
call ReadInt ; read the second integer
cmp ebx, 0 ; check if first value is positive
jle badInput ; if negative or zero, print error
cmp eax, 0 ; check if second value is positive
jg calculate ; if > 0, start calculation
badInput:
; Print error message
mov edx, OFFSET error ; load string address
call WriteString ; print the string
jmp endProg ; terminate program
calculate:
cmp ebx, eax ; compare numbers
jge start ; if a >= b, start calculation
xchg eax, ebx ; else, exchange numbers so a >= b
start:
push eax ; pass second number to function
push ebx ; pass first number to function
call gcd ; calculate gcd
add esp, 8 ; remove arguments from stack
mov ecx, eax ; save result in ecx
; Print result message
mov edx, OFFSET result ; load string address
call WriteString ; print the string
mov eax, ecx ; load the result in eax
call WriteDec ; print the gcd result
endProg:
call CrLF ; print newline
exit ; terminate the program
main ENDP
;-------------------------------------------------------------------
gcd PROC
;
; int gcd(a,b)
; Function to calculate the GCD
;-------------------------------------------------------------------
push ebp ; save frame pointer
mov ebp, esp ; point to new stack frame
push ebx ; save ebx
mov eax, [ebp + 8] ; load first argument (a)
mov ebx, [ebp + 12] ; load second argument (b)
cmp ebx, 0 ; if b == 0
je return ; return a
mov edx, 0 ; clear edx before division
div ebx ; divide a/b to get remainder
push edx ; pass a%b to next call
push ebx ; pass b to next call
call gcd ; call gcd(b, a%b)
add esp, 8 ; remove arguments from stack
return:
pop ebx ; restore ebx
pop ebp ; restore ebp
ret ; return to caller
gcd ENDP
END main