(12C) LCM <> GCD
01-06-2018, 10:14 AM (This post was last modified: 07-30-2018 01:50 AM by Gamo.)
Post: #1
 Gamo Senior Member Posts: 625 Joined: Dec 2016
(12C) LCM <> GCD
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, 12:27 PM (This post was last modified: 01-06-2018 12:31 PM by Dieter.)
Post: #2
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
RE: (12C) Least Common Multiple <> GCD
(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
01-07-2018, 12:49 AM (This post was last modified: 01-07-2018 02:21 AM by Gamo.)
Post: #3
 Gamo Senior Member Posts: 625 Joined: Dec 2016
RE: (12C) Least Common Multiple <> GCD
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
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)