HP15c program: Euclidean algorithm, Greatest Common Divisor (GCD), Highest Common Factor (HCF)

Note that all those GCD algorithms on this page work only for positive integers. The programs don't enforce that you have to make sure it's the case.

command         display

f LBL B        001-42,21,12   // LBL B: Calculate GCD(a,b), a->x, b->y
g ABS          002-   43 16
g X=0          003-   43 20
   GTO 7        004-   22  7
   x<>y (swap)  005-      34
g ABS          006-   43 16
f LBL 6        007-42,21, 6
g TEST 4       008-43,30, 4   // less or equal zero then end
   GTO 7        009-   22  7
g TEST 8       010-43,30, 8   // is a greater than b ? , a->y, b->x
   GTO 8        011-   22  8
   x<>y (swap)  012-      34   // cal b=b-a
   -            013-      30
g LST x        014-   43 36
   x<>y (swap)  015-      34
   GTO 6        016-   22  6
f LBL 8        017-42,21, 8   // cal a=a-b, a->y, b->x
   -            018-      30
g LST x        019-   43 36
   GTO 6        020-   22  6
f LBL 7        021-42,21, 7
   x<>y (swap)  022-      34
g ABS          023-   43 16
g RTN          024-   43 32

This program uses the following labels: LBL B and LBL 6,7,8
This program uses the following registers (STO/RCL): none

Using the program

I start every program with a label. This way you can have a number of programs in your 15c and you just select which one to run by pressing f LABELNAME (f B in this case) or GSB LABELNAME (GSB B in this case).

Let's say you would like to know what the GCD of 35 and 42 is:
You type: 35, ENTER, 42, GSB B
The display shows "running" and then you see 7 which is GCD(35,42)

Note: Enter only integer numbers (not floating point numbers / fractions).

The Euclidean algorithm

We use the Euclidean algorithm which works like this:

function eucledian(a,b){ // a and b must be postive integers, calculates GCD
    if (a ==0){
        return(b);
    }
    while(b > 0){
        if (a > b) {
            a = a - b;
        }else{
            b = b - a;
        }
    }
    return(a);
}

Example:

b=9 a=6
calculate b=9-6=3
b=3 a=6
calculate a=6-3=3
b=3 a=3
calculate b=3-3=0
Now b is zero. That means the result is a which is 3

LCM (Least Common Multiple)

The LCM is the smallest positive integer that is divisible by each of the two given integers. You can calculate the LCM wit the formula:
LCM(a,b) = ( a * b ) / GCD(a,b)
That's the product of a and b divided by the GCD of a and b.
The LCM is useful for finding a common denominator for adding fractions.

An algorithm that produces the same results with fewer iterations

The following algorithm is a modified version of the original Euclidean algorithm. It requires fewer iterations to come to the result. The program is however longer as the HP15c has no built-in modulo operator.

function eucledian_mod(a,b){ // a and b must be postive integers, calculates GCD
    while((a * b) > 0 ){ // condition can be 0 or any number between 0 an 0.9
        if (a >= b) {
            a = a % b; // a modulo b
        }else{
            b = b % a;
        }
    }
    return(a+b); // either a or b is zero
}

The HP15c does not have a modulo operator but it has [INT] and [FRAC] either of them could in theory be used to calculate the reminder of "a" divided by "b". [FRAC] may have issues with rounding errors. It is therefore better to use [INT].

command      display

f LBL B        001-42,21,12   // LBL B: Calculate GCD(a,b), a->x, b->y
g ABS          002-   43 16
   STO 9        003-   44  9
   x<>y (swap)  004-      34
g ABS          005-   43 16
   STO 8        006-   44  8
   * (multiply) 007-      20
   .            008-      48   // we do a*b <= 0.1
   1            009-       1
g x<=y         010-   43 10   
   GTO 5        011-   22  5
   RCL 9        012-   45  9   
   RCL 8        013-   45  8
   + (add)      014-      40
   R/S          015-      31
f LBL 5        016-42,21, 5
   RCL 9        017-   45  9   // a
   RCL 8        018-   45  8   // b
g x<=y         019-   43 10
   GTO B        020-   22 12   // redo with a and b swapped
   x<>y (swap)  021-      34   // the following lines calculate a modulo b
   / (divide)   022-      10
g LST X        023-   43 36
   x<>y (swap)  024-      34
g INT          025-   43 44
   * (multiply) 026-      20
   CHS          027-      16
   RCL 8        028-   45  8
   + (add)      029-      40
   RCL 9        030-   45  9   
   GTO B        031-   22 12

This program uses the following labels: LBL B and LBL 5
This program uses the following registers (STO/RCL): 8, 9

Test the program: 1071, Enter, 1029, GSB B, expected result: 21

The second algorithm is faster with bigger numbers and slower with smaller ones. To calculate GCD(35,42)=7 the first algorithm is better. To calculate GCD(1071,1029)=21 the second one is faster.

An even shorter algorithm

This is probably the best algorithm in terms of code length.

command      display

f LBL B        001-42,21,12   // LBL B: Calculate GCD(a,b), a->x, b->y
g TEST 7       002-43,30, 7  // x > y ?
   x<>y (swap)  003-      34
   - (subtract) 004-      30
g LSTx         005-   43 16
   x<>y (swap)  006-      34
g TEST 1       007-43,30, 1  // x > 0 ?
   GTO B        008-   22 12
   R↓           009-      33
g RTN          010-   43 32

Test the program: 88, Enter, 56, GSB B, expected result: 8

The algorithm

function gcd(int y, int x){
    int tmp;
    if (x>y){ // swap x and y
        tmp=x;y=x;x=tmp;
    }
    tmp=x;
    y=y-x;
    if (y==0){
	return(y);
    }
    gcd(tmp,y);
}

References

http://en.wikipedia.org/wiki/Euclidean_algorithm