Post Reply 
(11C) Least Common Multiple <> GCD
01-06-2018, 12:59 PM
Post: #1
(11C) Least Common Multiple <> GCD
Program to find LCM and GCD of two integers.

Code:

LBL A
STO 0
X<>Y
STO 1
LBL 1
 -
LSTx
X<>Y
ABS
X=0
GTO 2
GTO 1
LBL 2
X<>Y
STO 2
RCL 0
RCL 1
 x
RCL 2
 ÷
RTN

Example:

LCM(1133, 35) is 39655 ---> 1133 ENTER 35 A
GCD(1133, 35) is 1 --------> X<>Y

LCM(159951, 258852) is 33909612 --> 159951 ENTER 258852 A
GCD(159951, 258852) is 1221 -------> X<>Y

Gamo
Find all posts by this user
Quote this message in a reply
01-06-2018, 04:34 PM
Post: #2
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↑
Find all posts by this user
Quote this message in a reply
01-07-2018, 01:09 AM (This post was last modified: 01-07-2018 01:10 AM by Gamo.)
Post: #3
RE: (11C) Least Common Multiple <> GCD
Thank You wawa

Your program is much faster.

Gamo
Find all posts by this user
Quote this message in a reply
01-07-2018, 08:26 AM
Post: #4
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.
Find all posts by this user
Quote this message in a reply
01-07-2018, 06:00 PM (This post was last modified: 01-07-2018 06:05 PM by Dieter.)
Post: #5
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
Find all posts by this user
Quote this message in a reply
01-07-2018, 09:09 PM
Post: #6
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:
LINK

(unfortunately very slooooow)

Csaba
Find all posts by this user
Quote this message in a reply
01-08-2018, 12:29 PM
Post: #7
RE: (11C) Least Common Multiple <> GCD
Thank you @Dieter for these improvements. Your mod version is much better !
Find all posts by this user
Quote this message in a reply
Post Reply 




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