The basic GCD algorithm is:
Enter larger_number
Enter smaller_number
While the larger_number is not equal to the smaller_number
If larger_number < smaller_number
Exchange values of larger_number and smaller_number
EndIf
Subtract smaller_number from larger_number (replacing larger_number)
Loop back to while
Output larger_number
Stop
Our code will perform these generic activities:
In addition to these activities explicit in the algorithm, we will need to be able to:
A major difficulty here is caused by the fact that the user will be entering a value in decimal (base 10) which will need to be converted into unsigned binary for internal processing. A rough algorithm to manage this process could be:
Because this is a fairly common processing requirement, it may be convenient to code it as a subroutine (called a PROC, in MASM assembler) which could easily be copied into other programs with similar needs. Limitations on the size of numeric value that is acceptable should also be considered at this point; assuming a single word is being used, the maximum value that could be encoded (in a 16-bit word) is 65535; we can not guarantee the validity of any user input which allowed 5 or more digits. Non-decimal digit characters should also cause some kind of error recognition.
; GetNum - input a maximum of 4 decimal digits and return the
; unsigned binary form of this number in AX;
; Return with the Carry flag "on" if the input is invalid
;
; note that this particular version of the GetNum "proc" is flagged as "near"
; indicating that it will be contained in the same segment as the
; statement that calls it.
getnum proc near
mov num,0
mov bh,'9' ;setup for valid range testing
mov bl,'0'
mov cl,4 ;maximum number of digits acceptable
get_loop:
mov ah,01 ;get key (with echo)
int 21h
cmp al,0Dh ;exit loop on carriage return
je get_exit
cmp bh,al ;check that it's < '9'
jc bad_digit ;error if its not
sub al,bl
jc bad_digit ;error if its < '0'
mov ah,0
push ax ;save digit value for later addition
mov ax,num
mov dx,10 ;decimal based system
imul dx ;multiply ax by dx results in dx|ax
mov num,ax ;value of prior digits times 10
pop ax ;add this digit's value
add num,ax
sub cl,1
jnc get_loop
bad_digit: ;-- if we get here something is wrong
;-- by careful coding we have ensured that
;-- the carry flag will be set
;-- this is the "error" return indicator
get_exit:
mov ax,num
ret
;--- local data ---
num dw ?
getnum endp
A WHILE loop has two key parts: the test at the top of the while loop and the return to the top of the loop:
while: mov ax,large ; while ( large != small )
cmp ax,small
je endwhile ; exit loop when large == small
;
; instructions to be repeated by WHILE go here
;
jmp while ; loop back to WHILE test
endwhile:
This is a standard logic flow structure:
if: mov ax,large ; if ( large < small )
cmp ax,small
jae endif ; exit IF when large >= small
;
; instructions to be executed by IF (true) go here
;
endif:
Use a temporary work data location or a register to help switch values. There are actually may ways to achieve this; one method will be given here and a different method will be included in the final combined program sample.
push large
push small
pop large
pop small
Note that for arithmetic at least one of the values must be in a register.
mov ax,small ; must put one value in register
sub large,ax ; subtract small from large (replacing large)
Together with the "Enter a number" requirement, this is one of the more difficult processes since it involves a conversion between unsigned binary and decimal digits. Again, we will consider a rough algorithm:
Repeat:
... until the number has been reduced to zero.
Repeat for each of the saved digits:
... until all digits have been output.
As with the "Get a number" routine, this is a common enough requirement that creation as a separate subroutine would likely be a good design decision. Converted to mnemonic code, this would become something like:
; ShowNum - Display the unsigned binary value in AL as a
; decimal value
showNum proc near
mov bx,10 ;divide by 10 to convert to decimal
mov cl,0 ;count of number of digits produced
div_loop:
mov dx,0 ;setup to divide dx|ax by bx
idiv bx ;unsigned division:
;quotient in ax, remainder in dx
push dx ;save the digit (remainder) on the LIFO stack
inc cl ;keep track of number of digits
cmp ax,0 ;until nothing left to divide
jnz div_loop; loop back
mov dx,offset newline ;ensure display is on a newline
mov ah,09
int 21h
show_digit:
pop dx ;retrieve digit value from LIFO stack
add dl,30h ;convert digit to ASCII code
mov ah,02 ;display character
int 21h
dec cl ;loop until all digits shown
jnz show_digit
ret
;-- local data --
newline db 0Dh,0Ah,"$"
showNum endp
Assuming AL has been pre-loaded with the desired return code:
mov ah,4Ch ; 4C means "terminate with code"
int 21h
Download the complete source: gcd.asm