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