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!

About these ads

3 thoughts on “Euclid’s gcd algorithm

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

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s