The Museum of HP Calculators

HP Forum Archive 13

 HP-15C (11C/34C/42S/etc) Arguably Useful Mini-ChallengeMessage #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-ChallengeMessage #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-ChallengeMessage #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 slowMessage #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: Too long (14 steps with LBL and RTN) Too slow Limited by N=34 (because (2*N)!) But I'm working... ;) Csaba

 Re: HP-15C:Slow, but not limited by NMessage #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-ChallengeMessage #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-ChallengeMessage #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 HP41Message #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 fromMessage #15 Posted by Gene on 25 Nov 2003, 7:07 p.m.,in response to message #13 by Gene Found my formula here: and 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 fromMessage #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 ForceMessage #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 ForceMessage #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-850PMessage #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'sMessage #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-ChallengeMessage #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-ChallengeMessage #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 32SiiMessage #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 StepsMessage #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 StepsMessage #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-ChallengeMessage #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.

Go back to the main exhibit hall