GCD Algorithm

Greatest Common Divisor

The GCD (Greatest Common Divisor) of two numbers is the largest number that divides both evenly. Euclid's algorithm computes it efficiently using repeated division.

Euclid's Algorithm

The key insight: GCD(a, b) = GCD(b, a % b). Keep replacing a with b and b with a % b until b becomes 0. Then a is the GCD.

GCD(48, 18):
  48 % 18 = 12  →  GCD(18, 12)
  18 % 12 = 6   →  GCD(12, 6)
  12 % 6  = 0   →  GCD(6, 0)
  b = 0, so GCD = 6

Computing Remainder in ARM64

ARM64 has no modulo instruction, but you can compute a % b using:

UDIV X2, X0, X1      // quotient = a / b
MUL X3, X2, X1       // quotient * b
SUB X0, X0, X3       // remainder = a - quotient * b

The GCD Loop

// X0 = a, X1 = b
gcd_loop:
    CBZ X1, gcd_done      // if b == 0, GCD is in X0
    UDIV X2, X0, X1       // a / b
    MUL X3, X2, X1        // (a / b) * b
    SUB X2, X0, X3        // remainder = a % b
    MOV X0, X1            // a = old b
    MOV X1, X2            // b = remainder
    B gcd_loop
gcd_done:
// X0 = GCD

Your Task

Compute GCD(48, 18) using Euclid's algorithm and print the result (6) followed by a newline.