▼
Posts: 1,755
Threads: 112
Joined: Jan 2005
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.
▼
Posts: 107
Threads: 22
Joined: May 2006
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
▼
Posts: 14
Threads: 1
Joined: Jan 1970
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
Posts: 14
Threads: 1
Joined: Jan 1970
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
Posts: 93
Threads: 15
Joined: Jan 1970
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
▼
Posts: 93
Threads: 15
Joined: Jan 1970
LBL C
ENTER
+
LSTx
Py,x
LSTx
2
x<>y
y^x
/
RTN
11 steps, N=52 -> 9.39s
Csaba
▼
Posts: 93
Threads: 15
Joined: Jan 1970
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)
▼
Posts: 93
Threads: 15
Joined: Jan 1970
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
Posts: 4
Threads: 0
Joined: Mar 2012
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 ....
▼
Posts: 93
Threads: 15
Joined: Jan 1970
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
Posts: 48
Threads: 7
Joined: Jan 1970
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.
▼
Posts: 48
Threads: 7
Joined: Jan 1970
Sorry, I guess I don't know how to format the form properly.
2^N should be in the denominator.
Posts: 1,107
Threads: 159
Joined: Jan 1970
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?
▼
Posts: 1,153
Threads: 94
Joined: Mar 2006
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.
Posts: 1,107
Threads: 159
Joined: Jan 1970
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.
▼
Posts: 1,153
Threads: 94
Joined: Mar 2006
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!)
Posts: 95
Threads: 7
Joined: Jan 1970
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
▼
Posts: 182
Threads: 9
Joined: Jun 2013
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
▼
Posts: 362
Threads: 30
Joined: Jul 2005
And 0.1837 approx abd 0.2065 exact on a 49g+
Arnaud
Posts: 93
Threads: 15
Joined: Jan 1970
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
▼
Posts: 93
Threads: 15
Joined: Jan 1970
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
Posts: 93
Threads: 15
Joined: Jan 1970
<< DUP 2 INV - ! LN SWAP 2 LN * + PI LN 2 / - EXP >>
N=52 -> 0.188s on my 48SX
Csaba
Posts: 95
Threads: 7
Joined: Jan 1970
Victor,
This is beautiful. But I feel like a DUP, my brain quite ROTated, just looking at it. Nice job!
Cheers,
Tom
Posts: 1,755
Threads: 112
Joined: Jan 2005
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.
▼
Posts: 182
Threads: 9
Joined: Jun 2013
You must be quite happy with your daughter! Well done!
Cheers, Victor
▼
Posts: 1,755
Threads: 112
Joined: Jan 2005
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.
▼
Posts: 95
Threads: 7
Joined: Jan 1970
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
Posts: 93
Threads: 15
Joined: Jan 1970
Posts: 536
Threads: 56
Joined: Jul 2005
missing a step
LBL A . 5 - ! 2 UP ^ * PI SQRT / RTN
Posts: 1,153
Threads: 94
Joined: Mar 2006
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
▼
Posts: 5
Threads: 1
Joined: Jan 1970
LBL B
ENTER
+
LASTx
Pn,r
LASTx
2
x<>y
y^x
/
RTN
Cheers! Michael
▼
Posts: 5
Threads: 1
Joined: Jan 1970
LBL B ENTER + LASTx Pn,r 2 LASTx y^x / RTN
Cheers! Michael
▼
Posts: 93
Threads: 15
Joined: Jan 1970
Posts: 189
Threads: 23
Joined: Jan 1970
hey paul, you have it. you dont need the dup at the start.
|