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:
... 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