GCD using Assembly Language Homework 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.

• 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