+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (11C) GCD and LCM (/thread-9866.html)
(11C) GCD and LCM - Gamo - 01-06-2018 12:59 PM
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
RTNExample:
(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
RE: (11C) Least Common Multiple <> GCD - wawa - 01-06-2018 04:34 PM
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↑RE: (11C) Least Common Multiple <> GCD - Gamo - 01-07-2018 01:09 AM
Thank You wawa
Your program is much faster.
Gamo
RE: (11C) Least Common Multiple <> GCD - wawa - 01-07-2018 08:26 AM
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.
RE: (11C) Least Common Multiple <> GCD - Dieter - 01-07-2018 06:00 PM
(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
RE: (11C) Least Common Multiple <> GCD - Csaba Tizedes - 01-07-2018 09:09 PM
(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
RE: (11C) Least Common Multiple <> GCD - wawa - 01-08-2018 12:29 PM
Thank you @Dieter for these improvements. Your mod version is much better !