8086 Assembly Program to Compute the Greatest Common Divisor (GCD) of Two 16-bit Numbers Using Euclidean Algorithm

In this blog post, we’ll explore an 8086 assembly program that computes the Greatest Common Divisor (GCD) of two numbers using the classic Euclidean Algorithm.

The Euclidean method is an efficient and elegant way to find the largest number that divides both inputs without leaving a remainder.

The principle is simple:
GCD(A, B) = GCD(B, A mod B)

This process repeats until the remainder becomes zero. At that point, the divisor is the GCD.

Let’s dive into the code and understand how it works!

Program Code

data segment
    a dw 0012h          ; First number (18 decimal)
    b dw 000Ah          ; Second number (10 decimal)
    gcd_result dw ?     ; Variable to store the GCD
data ends

code segment
    assume cs:code, ds:data
start:
    mov ax, data
    mov ds, ax           ; Initialize data segment

    mov ax, a            ; Load A into AX
    mov bx, b            ; Load B into BX

    cmp bx, 0000h        ; Check if B is zero
    jz store_result

gcd_loop:
    mov dx, 0000h        ; Clear DX before division
    div bx               ; AX = AX / BX, remainder in DX

    cmp dx, 0000h        ; If remainder = 0, GCD found
    je store_result_bx

    mov ax, bx           ; A = B
    mov bx, dx           ; B = remainder
    jmp gcd_loop         ; Repeat loop

store_result_bx:
    mov ax, bx           ; Move GCD into AX

store_result:
    mov gcd_result, ax   ; Store final result
    int 3                ; Stop execution
code ends
end start

Understanding the Code

Data Segment

The data segment defines all variables used in the program.

data segment: Marks the start of variable declarations.
a dw 0012h: Defines a 16-bit variable a initialized to 0012h (18 decimal).
b dw 000Ah: Defines a 16-bit variable b initialized to 000Ah (10 decimal).
gcd_result dw ?: Declares a 16-bit variable to store the computed GCD.

Code Segment

The code segment holds all instructions executed by the processor.

assume cs:code, ds:data: Tells the assembler that CS points to the code segment and DS points to the data segment.
mov ax, data / mov ds, ax: Loads the address of the data segment into DS so that variables can be accessed.
mov ax, a / mov bx, b: Loads the two input numbers into registers AX and BX.

The Euclidean Algorithm Loop

The program uses division and conditional jumps to implement the Euclidean Algorithm.

Clear DX:
mov dx, 0000h ensures DX is zero before division. For 16-bit division, DX:AX forms the dividend.
Perform Division:
div bx divides AX by BX.
- Quotient → AX
- Remainder → DX
Check Termination:
cmp dx, 0000h checks if the remainder is zero.
- If yes, jump to store_result_bx (GCD found).
Iterate:
- mov ax, bx → new A becomes old B.
- mov bx, dx → new B becomes remainder.
- jmp gcd_loop → repeat until remainder is zero.
Store Result:
Once the remainder is zero, BX holds the GCD.
- mov gcd_result, ax stores the final result.
- int 3 halts execution.

Flowchart

On a High Level

The data and code segments are initialized.
The two input values (A and B) are loaded.
The Euclidean Algorithm runs iteratively using division and remainders.
The result (GCD) is stored in memory and the program stops.

For inputs 18 (0012h) and 10 (000Ah), the program produces a GCD of 2 (0002h).

Output

C:\TASM>masm gcd.asm
Microsoft (R) Macro Assembler Version 5.00
Copyright (C) Microsoft Corp 1981-1985, 1987.  All rights reserved.
 
Object filename [gcd.OBJ]:
Source listing  [NUL.LST]:
Cross-reference [NUL.CRF]:
 
  50350 + 450306 Bytes symbol space free
 
      0 Warning Errors
      0 Severe  Errors
 
C:\TASM>link gcd.obj
 
Microsoft (R) Overlay Linker  Version 3.60
Copyright (C) Microsoft Corp 1983-1987.  All rights reserved.
 
Run File [GCD.EXE]:
List File [NUL.MAP]:
Libraries [.LIB]:
LINK : warning L4021: no stack segment
 
C:\TASM>debug gcd.exe
-g
 
AX=0002  BX=000A  CX=0000  DX=0000  SP=0000  BP=0000  SI=0000  DI=0000
DS=0B97  ES=0B87  SS=0B97  CS=0B98  IP=0015   NV UP EI PL NZ NA PO NC
0B98:0015 CC            INT     3
-d 0B97:0000
0B97:0000  12 00 0A 00 02 00 00 00-00 00 00 00 00 00 00 00   ................
0B97:0010  B8 97 0B 8E D8 A1 00 00-8B 1E 02 00 F7 E3 A3 04   ................
0B97:0020  00 89 16 06 00 CC 15 8A-86 70 FF 2A E4 50 B8 FD   ...r.w...p.*.P..
0B97:0030  05 50 FF 36 24 21 E8 77-63 83 C4 06 FF 36 24 21   .P.6$!.wc....6$!
0B97:0040  B8 0A 00 50 E8 47 5E 83-C4 04 5E 8B E5 5D C3 90   ...P.G^...^..]..
0B97:0050  55 8B EC 81 EC 84 00 C4-5E 04 26 80 7F 0A 00 74   U.......^.&amp;....t
0B97:0060  3E 8B 46 08 8B 56 0A 89-46 FC 89 56 FE C4 5E FC   >.F..V..F..V..^.
0B97:0070  26 8A 47 0C 2A E4 40 50-8B C3 05 0C 00 52 50 E8   &amp;.G.*[email protected].
-q

Understanding the Memory Dump

This memory dump shows the contents starting from address 0B97:0000 after program execution.

0B97:0000  12 00 0A 00 02 00 00 00-00 00 00 00 00 00 00 00  ................

Breakdown:

12 00 → Value of a = 18 (0012h)
0A 00 → Value of b = 10 (000Ah)
02 00 → Computed GCD = 2 (0002h), stored in gcd_result

Writing an 8086 assembly program to find the GCD is like watching two numbers argue over who’s bigger—until one finally gives up, and their only common ground left is the GCD!

Calculating the GCD using the Euclidean Algorithm in 8086 assembly requires careful management of the DIV instruction’s registers (AX, DX) within a repetitive loop structure. It’s a classic example of how a complex mathematical routine is broken down into simple, register-level arithmetic steps, much like calculating modulo in assembly is fundamentally a division operation where the output is determined by checking the remainder. This iterative process acts like a self-adjusting sieve, continuously refining the dividend and divisor until only the largest common factor remains, a true low-level powerhouse calculation!

@ankurm