Find LCM of 2 numbers without using GCD - Printable Version +- HP Forums (https://www.hpmuseum.org/forum) +-- Forum: HP Calculators (and very old HP Computers) (/forum-3.html) +--- Forum: General Forum (/forum-4.html) +--- Thread: Find LCM of 2 numbers without using GCD (/thread-11144.html) Pages: 1 2 Find LCM of 2 numbers without using GCD - Gamo - 07-30-2018 01:06 PM Found this topic interesting and would like to share the concept on how to find the LCM without first calculating the GCD. The approach is to start with the largest of the 2 numbers and keep incrementing the larger number by itself till smaller number perfectly divides the resultant. Example: (7, 5) 7 + 7 + 7 +7 + 7 = 35 35 divide 5 perfectly so LCM is 35 The problem is I'm still figuring out on how to program this algorithm by using RPN programmable calculator. Anyone with a solution is welcome to share here. Thank You Gamo RE: Find LCM of 2 numbers without using GCD - Albert Chan - 07-30-2018 02:42 PM Hi Gamo, Why calculate LCM by brute force ? (that is basically what the code does) Is it because the calculator cannot do modulus ? RE: Find LCM of 2 numbers without using GCD - Thomas Klemm - 07-30-2018 04:07 PM This is the Python program that I came up with: Code: def lcm(a, b):     p, q = a, b     while p != q:         if p < q:             p += a         else:             q += b     return p And this is for the HP-42S: Code: 00 { 30 Byte-Prgm } 01 LBL "LCM" 02 RCL ST Y 03 RCL ST Y 04 LBL 00 05 X=Y? 06 RTN 07 XY 10 RCL+ ST T 11 X<>Y 12 GTO 00 13 LBL 01 14 RCL+ ST Z 15 GTO 00 16 END I hope that's what you had in mind. Cheers Thomas PS: Look ma, no modulus. RE: Find LCM of 2 numbers without using GCD - Thomas Klemm - 07-30-2018 04:41 PM But then why not using Jean-Marc Baillard's solution: GCD? RE: Find LCM of 2 numbers without using GCD - Gamo - 07-30-2018 05:46 PM Thank You Thomas Klemm With this particular algorithm I like to see on how to program this on RPN programmable calculator. There must be many different techniques to do this. Can you convert this 42S program to 11C 12C or 15C? Sorry I don't have the 42S at hand. Thank You Gamo RE: Find LCM of 2 numbers without using GCD - Dieter - 07-30-2018 06:02 PM (07-30-2018 01:06 PM)Gamo Wrote:  Found this topic interesting and would like to share the concept on how to find the LCM without first calculating the GCD. The approach is to start with the largest of the 2 numbers and keep incrementing the larger number by itself till smaller number perfectly divides the resultant. ... The problem is I'm still figuring out on how to program this algorithm by using RPN programmable calculator. I assume you're especially interested in a version for the 12C, so here it is: Code: 01 X<=Y? 02 X<>Y 03 X<>Y 04 STO 0 05 X<>Y 06 ENTER 07 ENTER 08 ENTER 09 RCL 0 10 / 11 FRAC 12 X=0? 13 GTO 17 14 Rv 15 + 16 GTO 07 17 + 18 GTO 00 The larger number is kept on the stack, the smaller one is in R0. 15 [ENTER] 20 [R/S] => 60 Additional feature: replace the last line with these ones.... Code: 18 X<>Y 19 RCL 0 20 x 21 X<>Y 22 / 23 LstX 24 GTO 00 ... and you get both the LCM (in X) and the GCD (in Y). Dieter RE: Find LCM of 2 numbers without using GCD - Albert Chan - 07-30-2018 06:13 PM (07-30-2018 04:41 PM)Thomas Klemm Wrote:  But then why not using Jean-Marc Baillard's solution: GCD? Exactly ! Why brute force LCM ? For lcm(54321, 12345), a simple gcd derived lcm is 2600X faster ! (Speed relative to the no modulus brute forced lcm, post #3) Code: def gcd(a, b):     while b:         a = a % b         if not a: return b         b = b % a     return a def lcm(a,b):     g = gcd(a, b)     return g and a // g * b RE: Find LCM of 2 numbers without using GCD - Thomas Klemm - 07-30-2018 06:21 PM (07-30-2018 05:46 PM)Gamo Wrote:  Sorry I don't have the 42S at hand. You really should check Thomas Okken's Free42. Here's a program for the HP-11C: Code: LBL A STO 0 x<>y STO 1 LBL 0 x=y RTN x>y GTO 1 RCL 1 + GTO 0 LBL 1 x<>y RCL 0 + x<>y GTO 0 Kind regads Thomas RE: Find LCM of 2 numbers without using GCD - Dieter - 07-30-2018 06:22 PM (07-30-2018 04:07 PM)Thomas Klemm Wrote:  This is the Python program that I came up with: Code: def lcm(a, b):     p, q = a, b     while p != q:         if p < q:             p += a         else:             q += b     return p ... I hope that's what you had in mind. I think that's a different algorithm. ;-) On the 12C it would translate into something like this: Code: 01 STO 2 02 X<>Y 03 STO 1 04 - 05 X=0? 06 GTO 20 07 LstX 08 + 09 LstX 10 X<=Y? 11 GTO 17 12 X<>Y 13 RCL 2 14 + 15 X<>Y 16 GTO 04 17 RCL 1 18 + 19 GTO 04 20 LstX   21 GTO 00 35 [ENTER] 50 [R/S] => 350 Dieter RE: Find LCM of 2 numbers without using GCD - Dieter - 07-30-2018 06:42 PM (07-30-2018 06:13 PM)Albert Chan Wrote:   (07-30-2018 04:41 PM)Thomas Klemm Wrote:  But then why not using Jean-Marc Baillard's solution: GCD? Exactly ! Why brute force LCM ? The point here is not coding the best possible LCM algorithm. The program you linked is an example for the appropriate method on a suitable calculator (with MOD). But the idea of this thread is how to code a much less powerful method on a less powerful calculator like the 12C. Of course that's nothing what you'd seriously consider for writing an LCM program. ;-) Dieter RE: Find LCM of 2 numbers without using GCD - Thomas Klemm - 07-30-2018 06:47 PM (07-30-2018 06:22 PM)Dieter Wrote:  I think that's a different algorithm. ;-) Maybe. But it avoids division. RE: Find LCM of 2 numbers without using GCD - Thomas Klemm - 07-30-2018 07:43 PM (07-30-2018 06:13 PM)Albert Chan Wrote:  Why brute force LCM ? I wouldn't call that "brute force". It uses $$\frac{a+b}{\gcd(a,b)}-2$$ additions. This can be huge as in your example or then rather small if $$\gcd(a, b)$$ is in the same order as $$a$$ and $$b$$. On the other hand only addition is used which can be a benefit depending on the instruction set. Just for the record here's an implementation of lcm that doesn't calculate the gcd: Code: def lcm(a, b):     r = a % b     return a if r == 0 else a * lcm(b, r) / r Cheers Thomas RE: Find LCM of 2 numbers without using GCD - Albert Chan - 07-30-2018 11:31 PM (07-30-2018 07:43 PM)Thomas Klemm Wrote:  I wouldn't call that "brute force". It uses $$\frac{a+b}{\gcd(a,b)}-2$$ additions. This can be huge as in your example or then rather small if $$\gcd(a, b)$$ is in the same order as $$a$$ and $$b$$. On the other hand only addition is used which can be a benefit depending on the instruction set. Your formula is correct, post #3 lcm(54321, 12345) required 22,220 additions. The code search lcm by finding positive integers k1, k2, such that min(k1) * a = min(k2) * b It does not allow k1 or k2 to jump ahead, but to walk the number line. I think it is safe to say this is a brute force method. It might still be fast for certain inputs. Sometimes, brute force is all we need ... For calculator without modulus, we can also use binary-gcd Code: def binary_gcd(a, b):     while 1:         if a < b: a, b = b, a   # b smaller         if a == b or not b: return a         c = b+b         while c < a: c = c+c    # reduce a by two-thirds or more         a = c - a if a >= 0.75*c else a - c//2 For comparison, for binary_gcd(54321, 12345), additions + subtractions = 27 + 7 = 34 RE: Find LCM of 2 numbers without using GCD - Gamo - 07-31-2018 02:07 AM Thanks Dieter Very nice routine that used this starting code by making sure that Y is always larger than X I remember that you show me this code before on the (12C) LCM <> GCD topic. x<=y? x<>y x<>y One question though how to set up the routine so that it know when the integers is divide perfectly. Thank You Gamo RE: Find LCM of 2 numbers without using GCD - Dieter - 07-31-2018 07:05 AM (07-31-2018 02:07 AM)Gamo Wrote:  One question though how to set up the routine so that it know when the integers is divide perfectly. If x is divisible by y the fractional part of x:y is zero, cf. line 09...12. Dieter RE: Find LCM of 2 numbers without using GCD - Paul Dale - 07-31-2018 07:48 AM I am wondering why? We have an algorithm that takes little time. Let's use one that takes lots of time....... Pauli RE: Find LCM of 2 numbers without using GCD - Albert Chan - 07-31-2018 12:41 PM (07-31-2018 07:48 AM)Paul Dale Wrote:  I am wondering why? We have an algorithm that takes little time. Let's use one that takes lots of time....... Good enough for domain ? Shorter program codes ? Benchmark program ? School assignment ? Just joking :-) RE: Find LCM of 2 numbers without using GCD - Gamo - 07-31-2018 01:28 PM Hello Paul Dale This particular algorithm is one of the several others ways to solve for LCM. Like Dieter said this algorithm is not meant for speed but is for ways to program this specific algorithm just for fun or this routine might be helpful to use into some program if any. I just figure this out to write program for this LCM algorithm. Even though this routine run slow with large integers but give very accurate result. [Slowly but Surely] I have to break Dieter hearth by using 3 registers on this program. Sorry. Program: HP-12C : Find LCM of 2 numbers without using GCD Code:  01 X≤Y ? 02 X<>Y 03 X<>Y 04 STO 1 05 X<>Y 06 STO 2 07 STO 3 08 RCL 3 09 RCL 1 10   ÷ 11 FRAC 12 X=0 ? 13 GTO 19 14 RCL 2 15 RCL 3 16   + 17 STO 3 18 GTO 08 19 RCL 3 20 GTO 00 Example: LCM (105, 321) 105 ENTER 321 [R/S] ---> 11235 LCM (10553, 7133) 10553 ENTER 7133 [R/S] ---> 75274549 Gamo RE: Find LCM of 2 numbers without using GCD - Dieter - 07-31-2018 03:51 PM (07-31-2018 01:28 PM)Gamo Wrote:  I have to break Dieter hearth by using 3 registers on this program. Yes, especially since my version above implements the same algorithm with merely one single data register. And two steps less. #-) But your three-register version may run slightly faster. And you can save several steps: Code: 01 X≤Y? 02 X<>Y 03 STO 2 04 STO 0 05 X<>Y 06 STO 1 07 RCL 0 08 RCL 1 09 ÷ 10 FRAC 11 X=0? 12 GTO 16 13 RCL 2 14 STO+0 15 GTO 07 16 RCL 0 17 GTO 00 Dieter RE: Find LCM of 2 numbers without using GCD - Albert Chan - 07-31-2018 06:10 PM HP-12C Mod program that setup for finding Gcd, thus Lcm too Sorry if it look stupid ... This is my first HP-12C program (only HP calc I own) Register Y X --> X Mod(Y, X) Keep pressing R/S, eventually it display 0, previous Mod was Gcd (Rotate key to get it back) Code:                 ; HP-12C Mod Program: Y X --> X Mod(Y, X) Enter Enter     ; Y X X X - LastX +       ; Y Y X X Rotate          ; X Y Y X / LastX Swap    ; X Y X Y/X Int * -         ; X X X Mod(Y,X) Example: gcd(54321, 12345) = 3 54321 Enter 12345 R/S --> 4941 R/S --> 2463 R/S --> 15 R/S --> 3 R/S --> 0 Rotate --> 3