Tuesday, June 12, 2012

Program to find GCD of two numbers


MY_DATA SEGMENT
                NUM1 DW 000AH
                NUM2 DW 0004H
                GCD DW ?
MY_DATA ENDS

CODE SEGMENT
                ASSUME CS:CODE, DS:DATA
                START:
                MOV AX, DATA
                MOV DS, AX
                ; INITIALISATION OF DATA SEGMENT
               
                MOV AX, NUM1
                ; MOVE FIRST NUMBER TO AX
                MOV BX, NUM2
                ; MOVE SECOND NUMBER TO BX
               
                UP:
                CMP AX, BX
                JE EXIT
                ; IF EQUAL THEN NO POINT IN FINDING GCD
                JB EXCG
                ; IF FIRST NUMBER IS SMALLER PUT IT BX
                ; MEANING SMALL NUMBER MUST STAY IN BX
               
                UP1:
                MOV DX, 0000H
                ; INITIALISE DX
                DIV BX
                ; DIVIDE (BIGGER NUMBER)/(SMALLER NUMBER)
                CMP DX, 0
                ; SEE IF REMAINDER IS ZERO OR NOT
                JE EXIT
                ; IF ZERO VOILA YOU HAVE FOUND THE GCD IN THE SMALLER NUMBER
                MOV AX, DX
                ; IF NON ZERO MOVE REMAINDER TO AX
                JMP UP

                EXCG:
                XCHG AX, BX
                ; EXCHANGE CONTENTS OF AX AND BX
                JMP UP1
               
                EXIT:
                MOV GCD, BX
                ; STORE RESULT IN GCD
               
                ; WRITE THESE TWO LINES IF YOU ARE TESTING IN TASM
                MOV AH, 4CH
                INT 21H
                ; THE ABOVE TWO LINES ARE OBVIOUSLY THE EXIT INTERRUPT
                ; USED IN TASM

CODE ENDS
END START
Understanding the program
What I did was basically divide the larger number with the smaller number.
If we get remainder 0 then the smaller number is our GCD for the two given number.
If we don’t get a zero remainder we transfer the remainder to AX and then again repeat the process till we get that zero remainder. In short I perform the same procedure we use mathematically to find the Greatest Common Denominator.

No comments:

Post a Comment