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
 Gamo Senior Member Posts: 605 Joined: Dec 2016
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
 Albert Chan Senior Member Posts: 1,103 Joined: Jul 2018
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
 Thomas Klemm Senior Member Posts: 1,447 Joined: Dec 2013
RE: Find LCM of 2 numbers without using GCD
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 X<Y? 08 GTO 01 09 X<>Y 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.
07-30-2018, 04:41 PM
Post: #4
 Thomas Klemm Senior Member Posts: 1,447 Joined: Dec 2013
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
 Gamo Senior Member Posts: 605 Joined: Dec 2016
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
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
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.

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
07-30-2018, 06:13 PM
Post: #7
 Albert Chan Senior Member Posts: 1,103 Joined: Jul 2018
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):     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
07-30-2018, 06:21 PM
Post: #8
 Thomas Klemm Senior Member Posts: 1,447 Joined: Dec 2013
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 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

Thomas
07-30-2018, 06:22 PM (This post was last modified: 07-30-2018 06:24 PM by Dieter.)
Post: #9
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
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:
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
07-30-2018, 06:42 PM
Post: #10
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
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?

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
07-30-2018, 06:47 PM
Post: #11
 Thomas Klemm Senior Member Posts: 1,447 Joined: Dec 2013
RE: Find LCM of 2 numbers without using GCD
(07-30-2018 06:22 PM)Dieter Wrote:  I think that's a different algorithm. ;-)

Maybe. But it avoids division.
07-30-2018, 07:43 PM
Post: #12
 Thomas Klemm Senior Member Posts: 1,447 Joined: Dec 2013
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):     r = a % b     return a if r == 0 else a * lcm(b, r) / r

Cheers
Thomas
07-30-2018, 11:31 PM
Post: #13
 Albert Chan Senior Member Posts: 1,103 Joined: Jul 2018
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.
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.

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
07-31-2018, 02:07 AM
Post: #14
 Gamo Senior Member Posts: 605 Joined: Dec 2016
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
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
RE: Find LCM of 2 numbers without using GCD
(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
07-31-2018, 07:48 AM
Post: #16
 Paul Dale Senior Member Posts: 1,645 Joined: Dec 2013
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
 Albert Chan Senior Member Posts: 1,103 Joined: Jul 2018
RE: Find LCM of 2 numbers without using GCD
(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 :-)
07-31-2018, 01:28 PM (This post was last modified: 07-31-2018 01:42 PM by Gamo.)
Post: #18
 Gamo Senior Member Posts: 605 Joined: Dec 2016
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:
 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
07-31-2018, 03:51 PM (This post was last modified: 07-31-2018 03:52 PM by Dieter.)
Post: #19
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
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? 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
07-31-2018, 06:10 PM
Post: #20
 Albert Chan Senior Member Posts: 1,103 Joined: Jul 2018
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) 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
 « Next Oldest | Next Newest »

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