# Euclid’s gcd algorithm

Euclid’s algorithm for finding the greatest common divisor of two numbers is probably the oldest known algorithm.

The code that follows is based on Donald Knuth’s explanation of the algorithm in The Art of Computer Programming (Vol. i, pg. 9).

```@ euclid.s
@ GCD algorithm (example taken from Knuth TAOCP, p.9)

@ r1 holds the first value
@ r0 holds the second

.section	.data
vals:
.long 6099, 2166
.section	.text
.globl  _start

_start:
ldr r2, =vals	@ make r1 point to start of vals
ldr r1, [r2]	@ load first number into r2.
ldr r0, [r2, #4]	@ load second number into r0.

gcd:
cmp r0, r1		@ compare r0 and r1
subgt r0, r0, r1	@ if r0 > r1, r0 = r0 - r1
sublt r1, r1, r0	@ if r0 < r1, r1 = r1 - r0
bne gcd 		@ if r0 != r1, repeat

mov     r7, \$1	@ prepare to exit
swi     0		@ wake kernel

.end
```

In this example, I have omitted the ‘%’ signs from the register labels. The assembler is able to cope just fine with this.

```as -o euclid.o euclid.s ld -o euclid euclid.o ./euclid echo \$? ```

I’ll leave you to find out what result your program returns. Make sure it gives the correct result and if something is wrong, you’ll have to debug!