Program to find LCM and GCD with two integers.
Code:
STO 0
X<>Y
STO 1
X≤Y
X<>Y
X<>Y
-
LSTx
X<>Y
X=0
GTO 13
GTO 04
X<>Y
STO 2
RCL 0
RCL 1
x
RCL 2
÷
GTO 00
Example:
LCM(256, 562) is 71936 --> 256 ENTER 562 R/S
GCD(256, 562) is 2 -------> X<>Y
LCM(12345, 67890) is 55873470 ---> 12345 ENTER 67890 R/S
GCD(12345, 67890) is 15 -----------> X<>Y
Gamo
(01-06-2018 10:14 AM)Gamo Wrote: [ -> ]Program to find LCM and GCD with two integers.
You chose the algorithm with successive subtraction. I don't know how fast this runs on a real original 12C. But anyway, you can improve your code:
First you should
never ever use "2 y^x" for squaring. "ENTER x" is much faster and also more precise. It even sets LastX correctly.
Your program uses a square and squareroot sequence to emulate an ABS command. There are other ways to do so, but the ABS is not required if you make sure that y is greater than x:
x<=y?
x<>y
x<>y
At the end you should also first divide R0 by the GCD and then multiply with R1. This avoid inaccuracies for large arguments.
These suggestions lead to the following version:
Code:
01 STO 0
02 x<>y
03 STO 1
04 x<=y?
05 x<>y
06 x<>y
07 -
08 LastX
09 x<>y
10 x=0?
11 GTO 13
12 GTO 04
13 R↓
14 RCL 0
15 x<>y
16 STO 0
17 /
18 STOx1
19 RCL 0
20 RCL 1
21 GTO 00
This returns the LCM in X (and R1) and the GCD in Y (and R0).
However, I prefer a different algorithm:
repeat
c = a mod b
a = b
b = c
until c = 0
GCD = a
It runs quite fast and can be very elegantly implemented on calculators with mod function and direct stack access. For instance on the HP41:
Code:
01 LBL"GCDLCM"
02 RCL Y
03 RCL Y
04 LBL 00
05 MOD
06 LASTX
07 X<>Y
08 X≠Y?
09 GTO 00
10 +
11 /
12 ST* Y
13 X<> L
14 END
No registers, just the stack, returns GCD in X and LCM in Y.
This method can also be coded on the 12C:
Code:
01 x<=y?
02 x<>y
03 STO 0
04 STO 2
05 x<>y
06 STO 1
07 RCL 2
08 RCL 2
09 RCL 1
10 STO 2
11 /
12 INTG
13 RCL 1
14 x
15 -
16 STO 1
17 x=0?
18 GTO 21
19 R↓
20 GTO 07
21 R↓
22 RCL 2
23 /
24 RCL 0
25 x
26 STO 1
27 RCL 2
28 GTO 00
This returns the GCD in X (and R2) and the LCM in Y (and R1).
Dieter
Thank You Dieter
Very helpful to know that [ENTER] [x] is better than [2] [Y^X] and [X<=Y] [X<>Y] [X<>Y] to make Y greater than X
Your program version is much better.
Gamo