GCD (Greatest Common Divisor)ΒΆ

Computes the GCD of two numbers using Euclidean algorithm.

 1; GCD - Compute greatest common divisor using Euclidean algorithm
 2; Example: gcd(48, 18) = 6
 3; Output: R16 = 6
 4
 5start:
 6    ldi r16, 48       ; a = 48
 7    ldi r17, 18       ; b = 18
 8    
 9    cpi r17, 0
10    breq done
11
12loop:
13    ; Compute remainder: a % b
14    mov r18, r16      ; Save a
15    div r16, r17      ; a / b
16    mul r16, r17      ; (a / b) * b
17    mov r19, r18
18    sub r19, r16      ; remainder = a - (a/b)*b
19    
20    ; Shift: a = b, b = remainder
21    mov r16, r17
22    mov r17, r19
23    
24    cpi r17, 0
25    brne loop
26
27done:
28    jmp done

Demonstrates division, modulo operation, and iterative algorithm.