The Museum of HP Calculators

HP Forum Archive 15

[ Return to Index | Top of Index ]

lcm program on hp 33s
Message #1 Posted by kevin on 11 Dec 2005, 7:03 p.m.

does anybody know a program for finding the lcm of two numbers on the hp33s (or hp 32s or 32sii)?

      
Re: lcm program on hp 33s
Message #2 Posted by Hal on 11 Dec 2005, 11:57 p.m.,
in response to message #1 by kevin

Hi Kevin,
I just banged out this very simple, brute force program for a 33s that seems to work. Enter yor two arguments into the X and Y stack registers and XEQ L. The LCM will show in the display when finished. The bigger the arguments and the higher the LCM, the longer it takes. I put in 5000 and 5002 and it took about a munute to return an lcm of 12505000. 50 and 57 took 3 seconds to return 2850. Best regards, Hal

The program:

lblL
x>y?
x<>y
stoA
x<>y
stoB
2
stoC
lblO
rclC
rclB
*
rclA
/
FP (fractional part)
x=0?
gtoQ
1
sto+C
gtoO
lblQ
rclC
rclB
*
rtn

            
Re: lcm program on hp 33s
Message #3 Posted by Hal on 12 Dec 2005, 1:51 a.m.,
in response to message #2 by Hal

Actually the program I submitted in the posting above was predicated on the assumption that the LCM has to be at least twice the larger argument, which is actaully not true (my bad)...the LCM could be the larger argument itself. Easy fix...just change line seven to 1.


Hal :)

      
Re: lcm program on hp 33s
Message #4 Posted by Katie Wasserman on 12 Dec 2005, 10:21 a.m.,
in response to message #1 by kevin

Here are LCM and GCD routines for the 32SII/33S that I came up with. Note that LCM(m,n)= m x n / GCD(m,n) and LCM is computed here using Euclid's method. It's really fast, worst case is on the order of log base 2 of the smaller of m, n.


LCM: call with m,n in x,y return with LCM in x
uses: A, B, x,y,z,t

L01 LBL L
L02 STO A
L03 x<>y
L04 STOx A
L05 XEQ G
L06 RCL A
L07 x<>y
L08 /
L09 RTN

GCD: call with m,n in x,y return with GCD in x
uses: B, x,y,z,t

G01 LBL G
G02 x>y?
G03 x<>y
G04 STO B
G05 0                | these 7 instructions are just 
G06 ENTER            | to compute y mod x.  On a 33S
G07 CMPLX+           | You can replace these with
G08 /                | the single instruction:
G09 IP               | RMDR
G10 x                |
G11 -                |
G12 RCL B
G13 x<>y
G14 x>0?
G15 GTO G
G16 RCL B
G17 RTN
            
Re: lcm program on hp 33s
Message #5 Posted by Valentin Albillo on 12 Dec 2005, 11:12 a.m.,
in response to message #4 by Katie Wasserman

Hi, Katie:

In your 1st routine, namely: 

      L01 LBL L
      L02 STO A
      L03 x<>y
      L04 STOx A
      L05 XEQ G
      L06 RCL A
      L07 x<>y
      L08 /
      L09 RTN
you can save an additional step by replacing the final 
      RCL A, X<>Y, /
by the simpler: 
      L06 STO/ A
      L07 X<> A
which is one step shorter, slightly faster, and leaves the GCD in A and the LCM in X. Or you can simply use 
      L07 RCL A
instead of 
      L07 X<> A
to get the GCD in Y and the LCM in X, also one step shorter.

Best regards from V.

[ Return to Index | Top of Index ]

Go back to the main exhibit hall