# Greatest Common Denominator using Assembly Language Homework Solution

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 ```