Blog‎ > ‎

GCD in ARM Assembly

posted Apr 23, 2018, 3:56 AM by MUHAMMAD MUN`IM AHMAD ZABIDI   [ updated Apr 23, 2018, 8:02 AM ]
The greatest common divisor (GCD) of two positive integers is the largest integer that divides both numbers without a remainder. It is also know as Greatest Common Factors (GCF), Greatest Common Measure (GCM), Highest Common Divisor (HCD), or Highest Common Factor (HCF).

The 'official' algorithm in full 32-bit ARM instruction set. Cortex-M4 is different.

gcd     cmp    r0, r1     ;if r0 > r1
        subgt  r0, r0, r1 ;subtract r1 from r0
        sublt  r1, r1, r0 ;else subtract r0 from r1
        bne    gcd        ;reached the end?

Only 4 lines! Let us see if a compiler can do that.

Enter the following code:

int gcd(int A, int B)
    while( A != B )
        if( A > B )
            A -= B;
            B -= A;
    return B;

Then compile it to ARM7TDMI assembly using the -Os switch (optimize for size):

$ arm-none-eabi-gcc -mcpu=arm7tdmi --specs=nosys.specs -Os -S gcd.c

Finally, inspect the code, irrelevant junk filtered out.

    .cpu arm7tdmi
    cmp    r0, r1
    bne    .L5
    bx     lr
    subgt  r0, r0, r1
    suble  r1, r1, r0
    b      .L2

We can see that even when optimized for size, some redundant instructions still exist. All the more reason to know assembly language programming.