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