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!

### Like this:

Like Loading...

*Related*

Pingback: Euclid's gcd algorithm | Raspberry Pi | Scoop.it

Pingback: ห.ร.ม. ด้วยภาษา Assembly บน Raspberry Pi | Raspberry Pi Thailand

antiloquaxPost authorThanks for your comment. Sadly, I don’t understand Thai!