Find LCM of 2 numbers without using GCD

[Gamo]

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

[Albert Chan]

Hi Gamo,

Why calculate LCM by brute force ? (that is basically what the code does)

Is it because the calculator cannot do modulus ?

[Thomas Klemm]

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.

[Thomas Klemm]

But then why not using Jean-Marc Baillard's solution: GCD?

[Gamo]

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

[Dieter]

(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

[Albert Chan]

(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

[Thomas Klemm]

(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

[Dieter]

(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

[Dieter]

(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

[Thomas Klemm]

(07-30-2018 06:22 PM)Dieter Wrote:  I think that's a different algorithm. ;-)

Maybe. But it avoids division.

[Thomas Klemm]

(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

[Albert Chan]

(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

[Gamo]

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

[Dieter]

(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

[Paul Dale]

I am wondering why?

We have an algorithm that takes little time. Let's use one that takes lots of time.......



Pauli

[Albert Chan]

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

[Gamo]

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

[Dieter]

(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

[Albert Chan]

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