Greatest Common Divisor in Assembly Language Assignment Solution

Find GCD for Two Integer

Write an assembly language assignment program that requests input from the keyboard for two positive integers greater than 0 then it calculates and displays the greatest common divisor (GCD). The greatest common divisor (GCD) of two integers (numbers), is the largest number that divides them both without a reminder. For example, 21 is the GCD of 252 and 105 (because 252 = 21 × 12 and 105 = 21 × 5). Since 21 is the greatest common number that divides both integers it is the GCD.

Your program must define and use the following procedures:

Procedure Main: This is the main procedure of the program which makes the correct sequence of calls to other procedures and displays the program title as shown in the sample run.
Procedure Read_Numbers: This procedure prompts for input and reads the value of two positive integers. This procedure makes use of the procedure Check_Value (defined below) which checks if a value is out of range and displays the error message. If the returned value in BL is 0 (error) then it must prompt for the input again.
Procedure Check_Value: This procedure takes as input parameters an integer value in EAX, a minimum value in EBX. If the value of EAX is greater than the value of EBX, this procedure returns in BL the value 1. Otherwise, it displays the error message “Error, incorrect input. Try again!” and returns in BL the value 0.
Procedure GCD: This procedure takes as input parameters in EAX and EBX representing the two input integers and finds the greatest common divisor (GCD) using the following algorithm (subtraction method). In addition, this procedure provides a trace of execution as shown in the sample run.

GCD 01

Procedure Display_Result: Displays the result of GCD as shown in the sample run.

Sample Run

>>>>>> Greatest Common Divisor (GCD) <<<<<<<

Enter the 1st integer (>0): -1 Error,

incorrect input. Try again!

Enter the 1st integer (>0): 30

Enter the 2nd integer (>0): 0 Error,

incorrect input. Try again!

Enter the 2nd integer (>0): 55

GCD(30,55): START;

a=30,b=55 -> a < b -> b := b – a -> b := 25

a=30,b=25 -> a > b -> a := a – b -> a := 5 a=5,b=25

-> a < b -> b := b – a -> b := 20 a=5,b=20 -> a <

b -> b := b – a -> b := 15 a=5,b=15 -> a < b -> b

:= b – a -> b := 10 a=5,b=10 -> a < b -> b := b – a -> b := 5

a=5,b=5 -> a = b -> return a END;

The greatest common divisor of 30 and 55 is 5

Solution:

INCLUDE c:\Irvine\Irvine32.inc
.386; 32 bit registers
.stack 4096; don't need more
.data
a DWORD 0
b DWORD 0
header BYTE ">>>>>> Greatest Common Divisor (GCD) <<<<<<<", 10, 13, 10, 13, 0
enter_1st BYTE "Enter the 1st integer (>0): ", 0
enter_2nd BYTE "Enter the 2nd integer (>0): ", 0
error BYTE "Error, incorrect input. Try again!", 10, 13, 0
gcd_pre BYTE "GCD(", 0
gcd_comma BYTE ",", 0
gcd_post BYTE "): START;", 10, 13, 0
a_equals BYTE "a=", 0
b_equals BYTE ",b=", 0
a_equals_b BYTE " -> a = b -> return a", 10, 13, "END;", 10, 13, 10, 13, 0
a_lt_b BYTE " -> a < b -> b:= b - a -> b:=", 0
a_gt_b BYTE " -> a > b -> a:= a - b -> a:=", 0
gcd_msg BYTE "The greatest common divisor of ", 0
gcd_msg2 BYTE " and ", 0
gcd_msg3 BYTE " is ", 0
.code
gcd proc
lea edx, gcd_pre
call WriteString ; cout << "GCD("
call WriteInt ; cout << a
lea edx, gcd_comma
call WriteString ; cout << ","
push eax
mov eax, ebx
call WriteInt ; cout << b
pop eax
lea edx, gcd_post
call WriteString ; cout << "): START;"
gcd_loop:
lea edx, a_equals
call WriteString ; cout << "a="
call WriteInt ; cout << a
push eax
lea edx, b_equals
call WriteString ; cout << ",b="
mov eax, ebx
call WriteInt ; cout << b
pop eax ; (restore a)
cmp eax, ebx ; if (a == b) return a;
je gcd_equals
jg gcd_greater ; if (a > b) a -= b
gcd_lesser:
lea edx, a_lt_b
call WriteString ; cout << " a < b..."
sub ebx, eax ; b-=a
push eax
mov eax, ebx
call WriteInt ; cout<< b
call CrLf
pop eax ; (restore a)
jmp gcd_loop
gcd_greater:
lea edx, a_gt_b
call WriteString ; cout << " a > b..."
sub eax, ebx ; a-=b
call WriteInt ; cout << a
call CrLf
jmp gcd_loop
gcd_equals:
lea edx, a_equals_b
call WriteString
ret
gcd endp
; Read 2 integers (both > 0)
read_numbers proc
enter_1:
lea edx, enter_1st ; Display message
call WriteString ; cout << "Enter the 1st..."
call ReadInt ; cin >> input
mov a, eax
mov ebx, 1
call check_value ; check 1st value
and bl, bl
je enter_1 ; retry
enter_2:
lea edx, enter_2nd ; Display message
call WriteString ; cout << "Enter the 2nd..."
call ReadInt ; cin >> input
mov b, eax
mov ebx, 1
call check_value ; check 2nd value
and bl, bl
je enter_2 ; retry
read_numbers_finish:
ret
read_numbers endp
; check if eax >= ebx
; if it is bl = 1 otherwise it displays error message and bl = 0
check_value proc
cmp eax, ebx
jge bigger
lea edx, error
call WriteString ; cout << "Error.."
xor ebx, ebx ; return bl = 0
ret
bigger:
mov bl, 1 ; valid value
ret
check_value endp
main proc
lea edx, enter_1st ; Display message
call WriteString ; cout << ">>>>> Greatest..."
call read_numbers ; a= input(), b=input()
mov eax, a
mov ebx, b
call gcd ; GCD(a, b)
push eax ; save return value
lea edx, gcd_msg
call WriteString ; cout << "The greatest..."
mov eax, a
call WriteInt ; cout << a
lea edx, gcd_msg2
call WriteString ; cout << " and "
mov eax, b
call WriteInt ; cout << b
lea edx, gcd_msg3
call WriteString ; cout << " is "
pop eax
call WriteInt ; cout << GCD(a, b)
call CrLf ; cout << endl
finish:
call WaitMsg ; system("PAUSE");
ret ; return to command line
main endp
end main ; end of file

GCD using Assembly Language Homework Solution

Find GCD for Two Integer