(11C) GCD and LCM
01-06-2018, 12:59 PM (This post was last modified: 07-16-2018 03:50 AM by Gamo.)
Post: #1
 Gamo Senior Member Posts: 378 Joined: Dec 2016
(11C) GCD and LCM
Program to find GCD and LCM of two integers.

After running this program the stack registers contain:

T = a
Z = b
Y = LCM (a, b)
X = GCD (a,b)

Code:
 LBL A ENTER ENTER R^ ENTER Rv LBL 1 - LSTx X<>Y ABS X≠Y GTO 1 Rv Rv ENTER Rv X<>Y x LSTx Rv X<>Y ÷ LSTx RTN

Example:

(1133, 35)

1133 ENTER 35 f [A]

GCD 1 [X<>Y] LCM 39655

T = 1133
Z = 35
Y = 39655
X = 1

--------------------------------------------

(159951, 258852)

159951 ENTER 258852 f [A]

GCD 1221 [X<>Y] LCM 33909612

T = 159951
Z = 258852
Z = 33909612
X = 1221

---------------------------------------------
Gamo
01-06-2018, 04:34 PM
Post: #2
 wawa Junior Member Posts: 28 Joined: Dec 2013
RE: (11C) Least Common Multiple <> GCD
Here is another version which is generally much faster and operates only in the stack - no registers needed.

On HP11C, 159951 ENTER 2585 returns in approximatively 10 seconds
Y : 11 <- GCD
X : 37588485 <- LCM

Code:
01▸LBL A 02 FIX 2 03 ENTER 04 ENTER 05 R↑ 06 ENTER 07 R↓ 08 X>Y? 09 X<>Y 10▸LBL 1 11 ÷ 12 LASTX 13 X<>Y 14 FRAC 15 X<>Y 16 × 17 LASTX 18 X<>Y 19 RND 20 X≠0? 21 GTO 1 22 R↓ 23 R↓ 24 × 25 R↑ 26 ÷ 27 R↑
01-07-2018, 01:09 AM (This post was last modified: 01-07-2018 01:10 AM by Gamo.)
Post: #3
 Gamo Senior Member Posts: 378 Joined: Dec 2016
RE: (11C) Least Common Multiple <> GCD
Thank You wawa

Your program is much faster.

Gamo
01-07-2018, 08:26 AM
Post: #4
 wawa Junior Member Posts: 28 Joined: Dec 2013
RE: (11C) Least Common Multiple <> GCD
it is because I use the rule gcd(a,b)=gcd(b,a mod b) which decreases faster than gcd(a,b)=gcd(b,a-b).
Unfortunatly, there is no modulo function on the hp11, so extra steps are needed.
01-07-2018, 06:00 PM (This post was last modified: 01-07-2018 06:05 PM by Dieter.)
Post: #5
 Dieter Senior Member Posts: 2,258 Joined: Dec 2013
RE: (11C) Least Common Multiple <> GCD
(01-07-2018 08:26 AM)wawa Wrote:  it is because I use the rule gcd(a,b)=gcd(b,a mod b) which decreases faster than gcd(a,b)=gcd(b,a-b).
Unfortunatly, there is no modulo function on the hp11, so extra steps are needed.

@Gamo: That's the same algorithm as proposed in my reply to your 12C program.

@wawa: I would recommend changing the last steps to avoid results ≥ 1 E+10 when a*b is calculated:

Code:
22 R↓ 23 ENTER 24 R↓ 25 / 26 * 27 R↑

Yes, it's really sad that a MOD function was not implemented on the Voyagers, not even on the 15C. A better way than coding a mod b as  b*frac(a/b) is a–b*int(a/b). This avoids roundoff errors that have to be corrected by the RND command in your program. But it is a bit more tricky to implement, especially if only the stack is used.

However, with direct stack access and a MOD function a GCD routine can be done in merely six steps, e.g. on the HP41:

Code:
01 LBL 01 02 STO Z 03 MOD 04 X≠0? 05 GTO 01 06 +

:-)

Dieter
01-07-2018, 09:09 PM
Post: #6
 Csaba Tizedes Member Posts: 292 Joined: May 2014
RE: (11C) Least Common Multiple <> GCD
(01-07-2018 06:00 PM)Dieter Wrote:  However, with direct stack access and a MOD function a GCD routine can be done in merely six steps, e.g. on the HP41:

And WITHOUT MOD function on any Voyager only 8 steps:

(unfortunately very slooooow)

Csaba
01-08-2018, 12:29 PM
Post: #7
 wawa Junior Member Posts: 28 Joined: Dec 2013
RE: (11C) Least Common Multiple <> GCD
Thank you @Dieter for these improvements. Your mod version is much better !
 « Next Oldest | Next Newest »

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