[hp15c]

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


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         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 5        011-   22  5
   x><y         012-      34   // cal b=b-a
   -            013-      30
g LST x        014-   43 36
   x><y         015-      34
   GTO 6        016-   22  6
f LBL 5        017-42,21, 5   // 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         022-      34
g ABS          023-   43 16
g RTN          024-   43 32

This program uses the following labels: LBL B and LBL 5,6,7

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).

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

An algorithm that produces the same results with fewer iteration

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         004-      34
g ABS          005-   43 16
   STO 8        006-   44  8
   *            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
   +            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
   x<=y         019-   43 10
   GTO B        020-   22 12   // redo with a and b swapped
   x><y         021-      34  // the following lines calculate a modulo b
   /            022-      10
g LST X        023-   43 36
   x><y         021-      34
g INT          025-   43 44
   *            026-      20
   CHS          027-      16
   RCL 8        028-   45  8
   +            029-      40
   GTO B        030-   45  9

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

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.

References



© Guido Socher