(12C) LCM <> GCD

[Gamo]

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

[Dieter]

(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

[Gamo]

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