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

Hi Gamo,

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

Is it because the calculator cannot do modulus ?

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.

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

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

(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: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:22 PM)Dieter Wrote: [ -> ]I think that's a different algorithm. ;-)

Maybe. But it avoids division.

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

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

I am wondering why?

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

Pauli

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

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