Find LCM of 2 numbers without using GCD
|
07-30-2018, 01:06 PM
(This post was last modified: 07-30-2018 01:18 PM by Gamo.)
Post: #1
|
|||
|
|||
Find LCM of 2 numbers without using GCD
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 |
|||
07-30-2018, 02:42 PM
Post: #2
|
|||
|
|||
RE: Find LCM of 2 numbers without using GCD
Hi Gamo,
Why calculate LCM by brute force ? (that is basically what the code does) Is it because the calculator cannot do modulus ? |
|||
07-30-2018, 04:07 PM
Post: #3
|
|||
|
|||
RE: Find LCM of 2 numbers without using GCD
This is the Python program that I came up with:
Code: def lcm(a, b): And this is for the HP-42S: Code: 00 { 30 Byte-Prgm } I hope that's what you had in mind. Cheers Thomas PS: Look ma, no modulus. |
|||
07-30-2018, 04:41 PM
Post: #4
|
|||
|
|||
RE: Find LCM of 2 numbers without using GCD
But then why not using Jean-Marc Baillard's solution: GCD?
|
|||
07-30-2018, 05:46 PM
Post: #5
|
|||
|
|||
RE: Find LCM of 2 numbers without using GCD
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 |
|||
07-30-2018, 06:02 PM
Post: #6
|
|||
|
|||
RE: Find LCM of 2 numbers without using GCD
(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. I assume you're especially interested in a version for the 12C, so here it is: Code: 01 X<=Y? 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 ... and you get both the LCM (in X) and the GCD (in Y). Dieter |
|||
07-30-2018, 06:13 PM
Post: #7
|
|||
|
|||
RE: Find LCM of 2 numbers without using GCD
(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): |
|||
07-30-2018, 06:21 PM
Post: #8
|
|||
|
|||
RE: Find LCM of 2 numbers without using GCD
(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 Kind regads Thomas |
|||
07-30-2018, 06:22 PM
(This post was last modified: 07-30-2018 06:24 PM by Dieter.)
Post: #9
|
|||
|
|||
RE: Find LCM of 2 numbers without using GCD
(07-30-2018 04:07 PM)Thomas Klemm Wrote: This is the Python program that I came up with: I think that's a different algorithm. ;-) On the 12C it would translate into something like this: Code: 01 STO 2 35 [ENTER] 50 [R/S] => 350 Dieter |
|||
07-30-2018, 06:42 PM
Post: #10
|
|||
|
|||
RE: Find LCM of 2 numbers without using GCD
(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? 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 |
|||
07-30-2018, 06:47 PM
Post: #11
|
|||
|
|||
RE: Find LCM of 2 numbers without using GCD | |||
07-30-2018, 07:43 PM
Post: #12
|
|||
|
|||
RE: Find LCM of 2 numbers without using GCD
(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): Cheers Thomas |
|||
07-30-2018, 11:31 PM
Post: #13
|
|||
|
|||
RE: Find LCM of 2 numbers without using GCD
(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. 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): For comparison, for binary_gcd(54321, 12345), additions + subtractions = 27 + 7 = 34 |
|||
07-31-2018, 02:07 AM
Post: #14
|
|||
|
|||
RE: Find LCM of 2 numbers without using GCD
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 |
|||
07-31-2018, 07:05 AM
Post: #15
|
|||
|
|||
RE: Find LCM of 2 numbers without using GCD | |||
07-31-2018, 07:48 AM
Post: #16
|
|||
|
|||
RE: Find LCM of 2 numbers without using GCD
I am wondering why?
We have an algorithm that takes little time. Let's use one that takes lots of time....... Pauli |
|||
07-31-2018, 12:41 PM
Post: #17
|
|||
|
|||
RE: Find LCM of 2 numbers without using GCD | |||
07-31-2018, 01:28 PM
(This post was last modified: 07-31-2018 01:42 PM by Gamo.)
Post: #18
|
|||
|
|||
RE: Find LCM of 2 numbers without using GCD
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:
Example: LCM (105, 321) 105 ENTER 321 [R/S] ---> 11235 LCM (10553, 7133) 10553 ENTER 7133 [R/S] ---> 75274549 Gamo |
|||
07-31-2018, 03:51 PM
(This post was last modified: 07-31-2018 03:52 PM by Dieter.)
Post: #19
|
|||
|
|||
RE: Find LCM of 2 numbers without using GCD
(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? Dieter |
|||
07-31-2018, 06:10 PM
Post: #20
|
|||
|
|||
RE: Find LCM of 2 numbers without using GCD
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) 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 |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: