The Museum of HP Calculators

HP Forum Archive 13

[ Return to Index | Top of Index ]

HP-15C (11C/34C/42S/etc) Arguably Useful Mini-Challenge
Message #1 Posted by Valentin Albillo on 24 Nov 2003, 11:16 a.m.

Hi all,

After some months of comforting absence, here's a new Arguably Useful Mini-Challenge for the HP-15C.You can also use other HP models such as the HP-11C, HP-34C, HP42S, etc, though my solutions and timing will be particularized explicitly for the HP-15C.

The challenge has practical applications, and goes like this:

The Challenge

Write a subroutine (LBL A ... RTN) that given an integer N (where N > 0) in the display, it will return to the display the value of f(N), where: 

    f(N) =  1 x 3 x 5 x ... x (2*N-3) x (2*N-1)

            <------------ N terms ------------>
thus, for instance, if N = 4 then 
     f(4) = 1 x 3 x 5 x 7 = 105

The main design goal for the routine is for it to be as fast as possible, (specially for large N, such as N > 30) and subject to that, to be as short as possible, to minimize resources (registers, flags, etc) used or have some other desirable properties.

Under the conditions given, there's a solution for the HP-15C in just 12 steps (counting LBL A and RTN) which takes 2.7 seconds for N = 52.

I'll give my solutions within 2 days or so, discussing the relative advantages of each. Meanwhile, let's see what you can do with your trusty HP and your ingenuity. :-)

Best regards from V.

Edited: 24 Nov 2003, 11:23 a.m.

      
Re: HP-15C (11C/34C/42S/etc) Arguably Useful Mini-Challenge
Message #2 Posted by Pascal on 24 Nov 2003, 12:19 p.m.,
in response to message #1 by Valentin Albillo

Well, taking your function f(n) = 1 * 3 * 5 * ... * (2*n-3) * (2*n-1)

one can see that it's related to the factorial.... somehow :-)

Lets put it differently:

        n
       ---
f(n) = | | (2x-1)
       x=1

         (2n)!
     = ----------
          n
         ---
         | |(2x) 
         x=1

              
     = (2n)! / g(x)


where g(x) = x! * 2^x


Putting this together gives

f(n) = (2n)! / (2^n * n!)



So:

LBL A
STO 0
2
*
x!
2
RCL 0 
y^x
LAST X
x!
*
/
RTN

OK, that's 13 steps.... but be it :-)

regards Pascal

            
Re: HP-15C (11C/34C/42S/etc) Arguably Useful Mini-Challenge
Message #3 Posted by Stephan (Germany) on 24 Nov 2003, 12:23 p.m.,
in response to message #2 by Pascal

I came to the same expression. But on a 15C evaluation for N=52 will fail due to 2*52 > 69 which is the maximum integer x! can handle. Still thinking, will post when I found another way.

Regards, Stephan

12345 to delete

      
Re: HP-15C Mini-Challenge - Valid solution, but too slow
Message #4 Posted by Stephan (Germany) on 24 Nov 2003, 12:47 p.m.,
in response to message #1 by Valentin Albillo

Considering that (2*52)! cant be evaluated by a 15C I found a solution in 11 steps.

f LBL A STO 0 2 * RCL 0 f Px,y 2 RCL 0 y^x / RTN

Unfortunately it is too slow (about 8 to 9 seconds for N=52). Still trying to improve.

Regards, Stephan

12345 to delete

      
Re: HP-15C:Fast(???), but limited (Nmax=34)
Message #5 Posted by Tizedes Csaba on 24 Nov 2003, 5:07 p.m.,
in response to message #1 by Valentin Albillo

I don't saw other solutions yet, this is my solution:

LBL B
ENTER
ENTER
+
x!
x<>y
x!
LSTx
2
x<>y
y^x
*
/
RTN

This is use the following equality:

1*3*5*...*(2*N-3)*(2*N-1)=(2*N)!/(2*4*6*...*(2*N-2)*(2*N))=(2*N)!/(2^N*(1*2*3*...*(N-1)*N))=(2*N)!/(2^N*N!)

Running times: (I measured 3 times, then calculated average times) 

N=4     2.36s
N=34    3.09s

Only three problems with this solution:

  1. Too long (14 steps with LBL and RTN)
  2. Too slow
  3. Limited by N=34 (because (2*N)!)

But I'm working... ;)

Csaba

            
Re: HP-15C:Slow, but not limited by N
Message #6 Posted by Tizedes Csaba on 24 Nov 2003, 5:26 p.m.,
in response to message #5 by Tizedes Csaba

LBL C
ENTER
+
LSTx
Py,x
LSTx
2
x<>y
y^x
/
RTN

11 steps, N=52 -> 9.39s

Csaba

                  
Re: HP-15C:Faster...
Message #7 Posted by Tizedes Csaba on 24 Nov 2003, 6:38 p.m.,
in response to message #6 by Tizedes Csaba

LBL A
2
x<>y
y^x
LSTx
.
5
-
x!
*
pi
sqrt(x)
/
RTN

14 steps, N=52 -> 4.02s

Csaba

This is use the following equality:

1*3*5*...*(2*N-3)*(2*N-1) = 2^N*GAMMA(N+1/2)/SQRT(PI)

                        
Re: HP-15C: An approximately solution...
Message #8 Posted by Tizedes Csaba on 24 Nov 2003, 9:13 p.m.,
in response to message #7 by Tizedes Csaba

I was played with Stirling-formula, and then Wallis-product, and I maked this approximately solution:

LBL D
2
x<>y
y^x
LSTx
x!
LSTx
pi
*
sqrt
/
*
RTN

13 steps, N=52 -> 2.69s

Error at N=4 +3.2%, at N=60 +0.2%

Csaba

                        
Re: HP-15C:Faster...
Message #9 Posted by Stefan Katletz on 25 Nov 2003, 8:33 a.m.,
in response to message #7 by Tizedes Csaba

By storing the two constants (0.5 and sqrt(PI)) in two registers (before running the program) one gains two lines and a little bit of time. But it still not the 2.7s ....

                              
Re: HP-15C:Faster...
Message #10 Posted by Tizedes Csaba on 25 Nov 2003, 12:32 p.m.,
in response to message #9 by Stefan Katletz

Thank you, Stefan, I wrote it, and I tryed:

LBL E
2
x<>y
y^x
LSTx
RCL-9
x!
*
RCL/8
RTN

.5 STO 9
sqrt(pi) STO 8

10 steps, N=52 -> 3.54s (Hmm...)

Csaba

      
Re: HP-15C (11C/34C/42S/etc) Arguably Useful Mini-Challenge
Message #11 Posted by Brent on 24 Nov 2003, 6:30 p.m.,
in response to message #1 by Valentin Albillo

I'm thinking of some way to put this in tha calc but I'm not a math person.

(N+1) x (N+2) x (N+3) x ... x (N+N) ----------------------------------- 2^N

It seems you can get rid of a bunch of internal stuff if you can do it.

            
Re: HP-15C (11C/34C/42S/etc) Arguably Useful Mini-Challenge
Message #12 Posted by Brent on 24 Nov 2003, 6:34 p.m.,
in response to message #11 by Brent

Sorry, I guess I don't know how to format the form properly.

2^N should be in the denominator.

      
14 step solution HP41
Message #13 Posted by Gene on 24 Nov 2003, 8:56 p.m.,
in response to message #1 by Valentin Albillo

Might be really bad (haven't read below). 14 steps includes LBL and RTN.

LBL 01 ENTER ST + X 1 + FACT X<>Y FACT 2 LASTX Y^X * / RTN

An odd double factorial, eh?

            
Re: What's with the " 1 + " ?
Message #14 Posted by Paul Brogger on 25 Nov 2003, 3:44 p.m.,
in response to message #13 by Gene

I figure the factorial formula is: 

   (2N)! / (N! * 2**N)
Am I missing something?

Also, removing "1 +" from yours, and using "ST + x" rather than the two-step "2 *" in mine (below) brings us both to 12 steps, with the same formula.

            
Where I got my stuff from
Message #15 Posted by Gene on 25 Nov 2003, 7:07 p.m.,
in response to message #13 by Gene

Found my formula here:

http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001147

and

http://mathworld.wolfram.com/DoubleFactorial.html

Note that the second link shows for (5) on the right side the (2N+1)!/((2^N)*N!) formula. That's what I used.

                  
Re: Where I got my stuff from
Message #16 Posted by Paul Brogger on 25 Nov 2003, 7:40 p.m.,
in response to message #15 by Gene

Well, let's try one . . .

For the example, n=4, the result has to equal 1 x 3 x 5 x 7 (the first four successive odd numbers multiplied together) or 105.

 (2*4+1)! / (2**4 * 4!) 
=      9! / (16 * 24) 
= 362,880 / 384 
=     945.

  (2*4)! / (2**4 * 4!) 
=     8! / (16 * 24) 
= 40,320 / 384 
=    105.

It's interesting that your formula seems to produce the same sequence of values, but they're "off by one". That is, if your formula is "g" and mine "p", then it appears that g(n) = p(n+1).

(I've got to get home, but I'll be playing with this some more. If I've got something wrong in the above, do set me straight!)

      
Not Fair !!
Message #17 Posted by Tom Sherman on 25 Nov 2003, 9:02 a.m.,
in response to message #1 by Valentin Albillo

Valentin's daughter would take out her Sharp 1350 and quickly write something like this:

10 INPUT "Number of terms =";N

20 A=1

30 X=1

40 FOR I=1 TO N

50 A=A*X

60 X=X+2

70 NEXT I

80 PRINT A

90 END

Execution time for N=52 on the HP-71B is a little over 2 seconds.

The rest of us would be left wondering why anyone would program in RPN anymore. Answer: it is fun, and more satisfying, because it is harder and takes much more time out of an otherwise dull evening.

I think that the above scheme can be done using a loop counter, index register, STO* or RCL* to save steps, etc., but it is too many years since I have done RPN programming to remember.

Tom

            
Brute Force
Message #18 Posted by Victor Koechli on 25 Nov 2003, 9:56 a.m.,
in response to message #17 by Tom Sherman

Alright, if you're going brute force, here you are:

<< DUP + 1 DUP ROT FOR i i * 2 STEP >>

.552s (HP-48SX), .367s (HP-49G, approx mode), .875s (HP-49G, exact mode). Works for n up to 202 (approx mode).

At least you can see how compact RPL is. Certainly not exactly what Valentin was asking for, though. I keep testing with my 15C...

Cheers, Victor 12345

                  
Re: Brute Force
Message #19 Posted by Arnaud Amiel on 25 Nov 2003, 10:14 a.m.,
in response to message #18 by Victor Koechli

And 0.1837 approx abd 0.2065 exact on a 49g+

Arnaud

                  
Force, but not brute...
Message #20 Posted by Tizedes Csaba on 25 Nov 2003, 11:32 a.m.,
in response to message #18 by Victor Koechli

PROD.EQ
<< -> n
   << n DUP 2 * SWAP PERM 2 n ^ / >>
>>

TEST.PRG
<< TICKS 52 PROD.EQ TICKS >>

I measured three times, and I modified the TEST.PRG:

TEST.PRG
<< TICKS 52 TICKS >>

The difference of running times (the real running time): 0.225s, on my 48SX.

Csaba

                        
Re: Force, but not brute... CASIO FX-850P
Message #21 Posted by Tizedes Csaba on 25 Nov 2003, 11:51 a.m.,
in response to message #20 by Tizedes Csaba

1 N=52:BEEP:FORI=1TO100:PERM=NPR(2*N,N)/2^N:NEXT:BEEP
Running time: A=19.51s

1 N=52:BEEP:FORI=1TO10000:NEXT:BEEP
Running time: B=26.68s

The result: A/100-B/10000=0.192s

Csaba

                        
LN(...*...*...) -> ...+...+...
Message #22 Posted by Tizedes Csaba on 25 Nov 2003, 4:21 p.m.,
in response to message #20 by Tizedes Csaba

<< DUP 2 INV - ! LN SWAP 2 LN * + PI LN 2 / - EXP >>

N=52 -> 0.188s on my 48SX

Csaba

                  
DUP's and ROT's
Message #23 Posted by Tom Sherman on 25 Nov 2003, 3:06 p.m.,
in response to message #18 by Victor Koechli

Victor,

This is beautiful. But I feel like a DUP, my brain quite ROTated, just looking at it. Nice job!

Cheers,

Tom

            
Re: Not Fair !!
Message #24 Posted by Valentin Albillo on 25 Nov 2003, 11:05 a.m.,
in response to message #17 by Tom Sherman

Hi, Tom:

Tom posted:

"Valentin's daughter would take out her Sharp 1350 and quickly write something like this:"

Actually, she *did*.

:-)

She took out her SHARP 1350 (which I presented to her a few months ago), and produced the following: 

10 INPUT "N = "; N: 
   A = 1: 
   FOR I = 1 TO 2*N - 1 STEP 2: 
       A = A * I: 
   NEXT I: 
   PRINT A: 
   END

which is only *one* (multi-statement) line of BASIC and uses STEP 2 to automatically increment the multiplier, thus avoiding any extra auxiliary variables. It executes fast, too, 1.5 seconds for N = 60, which is the limit for f(N) < 10^100.

... and I agree, it just isn't fair ... :-)

Best regards from V. and L.

                  
Re: Not Fair !!
Message #25 Posted by Victor Koechli on 25 Nov 2003, 11:17 a.m.,
in response to message #24 by Valentin Albillo

You must be quite happy with your daughter! Well done! Cheers, Victor

                        
Re: Not Fair !!
Message #26 Posted by Valentin Albillo on 25 Nov 2003, 11:38 a.m.,
in response to message #25 by Victor Koechli

Thanks a lot, Victor !

The equivalent HP-15C's RPN "loop" version, as Tom described, would be something like this: 

   LBL A
   STO I
   STO+I
    1
   LBL 0
   DSE I
   RCL*I
   DSE I
   GTO 0
   RTN

which works Ok for N=1 to N=60. It certainly will look less "intuitive" or "clear" to any non-RPN fan, mefears ! :-)

Best regards from V.

                              
A+ for L.
Message #27 Posted by Tom Sherman on 25 Nov 2003, 12:34 p.m.,
in response to message #26 by Valentin Albillo

Hi Valentin,

Please tell your daughter that this old retired prof. gives her an A+.

And thanks to you for the RPN loop listing.

Cheers,

Tom

      
OK, Valentin; and what is your solution??? [NO TEXT]
Message #28 Posted by Tizedes Csaba on 25 Nov 2003, 11:55 a.m.,
in response to message #1 by Valentin Albillo

.

      
Re: HP-15C (11C/34C/42S/etc) Arguably Useful Mini-Challenge
Message #29 Posted by hugh steers on 25 Nov 2003, 2:58 p.m.,
in response to message #1 by Valentin Albillo

missing a step

LBL A . 5 - ! 2 UP ^ * PI SQRT / RTN

      
Re: HP-15C (11C/34C/42S/etc) Arguably Useful Mini-Challenge
Message #30 Posted by Paul Brogger on 25 Nov 2003, 3:07 p.m.,
in response to message #1 by Valentin Albillo

I came up with the following, but noticed it looks a lot like others' work (above) . . .

01 LBL A
02 DUP
03 2
04 *
05 x!
06 SWAP
07 x!
08 2
09 LASTx
10 y^x
11 *
12 /
13 RTN

            
11 Steps on a 32Sii
Message #31 Posted by Michael Fink on 25 Nov 2003, 5:21 p.m.,
in response to message #30 by Paul Brogger

LBL B ENTER + LASTx Pn,r LASTx 2 x<>y y^x / RTN

Cheers! Michael

                  
Whoops! 10 Steps
Message #32 Posted by Michael Fink on 25 Nov 2003, 5:51 p.m.,
in response to message #31 by Michael Fink

LBL B ENTER + LASTx Pn,r 2 LASTx y^x / RTN

Cheers! Michael

                        
Re: Whoops! 10 Steps
Message #33 Posted by Tizedes Csaba on 25 Nov 2003, 6:00 p.m.,
in response to message #32 by Michael Fink

Good trick! ;)

Cs.

            
Re: HP-15C (11C/34C/42S/etc) Arguably Useful Mini-Challenge
Message #34 Posted by hugh on 25 Nov 2003, 5:21 p.m.,
in response to message #30 by Paul Brogger

hey paul, you have it. you dont need the dup at the start.

[ Return to Index | Top of Index ]

Go back to the main exhibit hall