(11C) GCD and LCM

01062018, 12:59 PM
(This post was last modified: 07162018 03:50 AM by Gamo.)
Post: #1




(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:
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 

01062018, 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 

01072018, 01:09 AM
(This post was last modified: 01072018 01:10 AM by Gamo.)
Post: #3




RE: (11C) Least Common Multiple <> GCD
Thank You wawa
Your program is much faster. Gamo 

01072018, 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,ab).
Unfortunatly, there is no modulo function on the hp11, so extra steps are needed. 

01072018, 06:00 PM
(This post was last modified: 01072018 06:05 PM by Dieter.)
Post: #5




RE: (11C) Least Common Multiple <> GCD
(01072018 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,ab). @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↓ 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 :) Dieter 

01072018, 09:09 PM
Post: #6




RE: (11C) Least Common Multiple <> GCD
(01072018 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 

01082018, 12:29 PM
Post: #7




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)