HP49-50G: help for recursive
|
02-02-2024, 12:46 PM
(This post was last modified: 02-02-2024 01:26 PM by Gil.)
Post: #1
|
|||
|
|||
HP49-50G: help for recursive
I have, from Albert Chan, the following recursive program:
200 DEF FNL(X) ! = ln(1+X) - X, but more accurate 210 IF ABS(X)>=.4 THEN X=X/(SQRT(1+X)+1) @ FNL=FNL(X)*2-X*X @ GOTO 250 220 X2=X/(X+2) @ X4=X2*X2 230 X4=X4*(5005-X4*(5082-X4*969))/(15015-X4*(24255-X4*(11025-X4*1225))) 240 FNL=X2*(X4+X4-X) 250 END DEF I transformed the FNL function for the HP50G, but without the recursion formulae: « 0 0 0 { } -> x X2 X4 fnl l « WHILE x .4 >= REPEAT x l + 'l' STO 'x/(sqrt(1+x)+1)' ->NUM 'x' STO END 'x/(x+2)' ->NUM 'X2' STO X2 DUP * 'X4' STO 'X4*(5005-X4*(5082-X4*969))/(15015-X4*(24255-X4*(11025-X4*1225)))' ->NUM 'X4' STO 'X2*(X4+X4-x)' ->NUM 'fnl' STO x l + 'l' STO l SIZE 1 > IF THEN 1 l SIZE 1 - FOR i fnl 2 * l i GET SQ - 'fnl' STO NEXT END fnl » » 'FNL' STO Or, with INOUT transcription: Code: \<< 0 0 0 { } \-> x X2 X4 fnl l I try now to have a HP50G recursive version FNL2: « 0 0 0 -> x X2 X4 fnl « IF x .4 >≠ THEN 'x/(sqrt(1+x)+1 )' ->NUM FNL2 2 * x SQ - ELSE 'x/(x+2)' ->NUM 'X2' STO X2 DUP * 'X4' STO 'X4*(5005- X4*(5082-X4*969))/( 15015-X4*(24255-X4*( 11025-X4*1225)))' ->NUM 'X4' STO 'X2*(X4 +X4-x)' ->NUM END » » Suppose I have an initial value of 2 for x. Then its successive values will be, as expected: .732050807569 and .316074012953. Then, as .316074012953 <0.4, we jump to the ELSE branch to get a value of -4.14209407856E-2 before the END instruction. Now the program carries on just after the FNL2. Unfortunately, before multiplying the last result -4.14209407856E-2 by 2, it closes one of the ». Consequence: the last value of x, 316074012953, disappears, and we get instead the previous value of x, 732050807569. Question: How could we change the program into a correct recursive version? Thanks for your help. Regards, Gil |
|||
02-02-2024, 01:52 PM
(This post was last modified: 02-03-2024 12:28 PM by Gil.)
Post: #2
|
|||
|
|||
RE: HP49-50G: help for recursive
I just found a simple solution by putting, each time, the values of x in the stack and using those values recursively for "2*FNL - x²", but with SWAP SQ -, instead of x²
FNL4 « 0 0 > x X2 X4 « IF x ABS .4 >= THEN 'x/(sqrt(1+x )+1)' ->NUM DUP FNL4 2 * SWAP SQ - ELSE 'x/(x+2)' ->NUM 'X2' STO X2 DUP * 'X4' STO 'X4*(5005- X4*(5082-X4*969))/( 15015-X4*(24255-X4*( 11025-X4*1225)))' ->NUM 'X4' STO 'X2*(X4 +X4-x)' ->NUM END » » |
|||
02-02-2024, 04:27 PM
Post: #3
|
|||
|
|||
RE: HP49-50G: help for recursive
FYI, FNL(X) code does not need recursion.
At the time, I try to make FNL(X) simple, recursion with a base case. I did not consider when to switch to fast-path, LOGP1(X)-X Cas> fnl(x) := ln(1+x)-x Cas> x1 := fsolve(fnl(x)=-0.1, x=0.4) → 0.516221161425 Cas> x2 := fsolve(fnl(x)=-0.1, x=-0.4) → -0.383183168208 If x is outside x1 .. x2, we don't have catastrophic cancellations. Try it! FNL base case = log1p_sub_tiny(x), abserr ≈ -1/176679360 * (x/(1+x/2))^15 Cas> abserr(x) := -1/176679360 * (x/(1+x/2))^15 Cas> abserr(x1) / fnl(x1) → 8.90366916672e−14 Cas> abserr(x2) / fnl(x2) → -7.75261380424e−13 Relative error below machine epsilon. FNL(X) recursion replaced with direct fast-path: 200 DEF FNL(X) ! = ln(1+X) - X, but more accurate 210 IF X<-.3832 OR X>.5163 THEN FNL=LOGP1(X)-X @ GOTO 250 220 X2=X/(X+2) @ X4=X2*X2 230 X4=X4*(5005-X4*(5082-X4*969))/(15015-X4*(24255-X4*(11025-X4*1225))) 240 FNL=X2*(X4+X4-X) 250 END DEF |
|||
02-02-2024, 04:48 PM
Post: #4
|
|||
|
|||
RE: HP49-50G: help for recursive
Hi, Gil
I am unclear which of your code (FNL, FNL2, FNL4) work. Some examples would be nice. Ignore the fact that FNL(X) does not need recursion (see previous post) Ignore also global variables should really be local, as SUB program. Here is how we simulate recursions for machine that does not support it, with a stack. 200 DIM S(99) @ DEF FNL(X) ! = ln(1+X) - X, but more accurate 210 FOR I=1 TO 99 @ IF ABS(X)<.4 THEN 230 220 X=X/(SQRT(1+X)+1) @ S(I)=X @ NEXT I ! fill stack 230 X2=X/(X+2) @ X4=X2*X2 240 X4=X4*(5005-X4*(5082-X4*969))/(15015-X4*(24255-X4*(11025-X4*1225))) 250 L=X2*(X4+X4-X) 260 WHILE I>1 @ I=I-1 @ X=S(I) @ L=L+L-X*X @ END WHILE ! undo stack 270 FNL=L @ END DEF Again, this is for illustration only. We don't want recursions (with rounding errors) when it is not needed. |
|||
02-02-2024, 06:13 PM
(This post was last modified: 02-03-2024 12:26 PM by Gil.)
Post: #5
|
|||
|
|||
RE: HP49-50G: help for recursive
Thanks, Albert, for your replies.
Both following functions FNL & FNL4 work nicely. With function FLN, no recursive process : 1) save the intermediate values of x in a list 2) pick the values of the list to build fln=... ; fln=... fln=... « 0 0 0 { } -> x X2 X4 fnl l « WHILE x .4 >= REPEAT x l + 'l' STO 'x/(sqrt(1+x)+1)' ->NUM 'x' STO END 'x/(x+2)' ->NUM 'X2' STO X2 DUP * 'X4' STO 'X4*(5005-X4*(5082-X4*969))/(15015-X4*(24255-X4*(11025-X4*1225)))' ->NUM 'X4' STO 'X2*(X4+X4-x)' ->NUM 'fnl' STO x l + 'l' STO l SIZE 1 > IF THEN 1 l SIZE 1 - FOR i fnl 2 * l i GET SQ - 'fnl' STO NEXT END fnl » » 'FNL' STO With recursive changed FLN4 suppression of unused 'fnl' variable [b]FNL4 « 0 0 -> x X2 X4 « IF x ABS .4 >= THEN 'x/(sqrt(1+x )+1)' ->NUM DUP FNL4 2 *SWAP SQ - ELSE 'x/(x+2)' ->NUM 'X2' STO X2 DUP * 'X4' STO 'X4*(5005- X4*(5082-X4*969))/( 15015-X4*(24255-X4*( 11025-X4*1225)))' ->NUM 'X4' STO 'X2*(X4 +X4-x)' ->NUM END » » FNL4' STO Code: \<< 0 0 \-> x X2 X4 Question Suppose now that the red instructions were a complicated function of x, and that we wanted to avoid to play with the stack with SWAP, DUP, etc. commands, how could we use instead the variable x here? I ask, because, by writing 2 * x² after FLN4, the program does not take the last x[n], but always the previous one, ie x[n-1], as at the end of the IF... THEN... END, it closes one ». |
|||
02-03-2024, 10:19 AM
(This post was last modified: 02-03-2024 10:51 AM by Gil.)
Post: #6
|
|||
|
|||
RE: HP49-50G: help for recursive
Some results
{ :CHAN (.3): -3.76357355325E-2 : LNP1(x)-x: -.037635735533 } { :CHAN (.4): -6.35277633788E-2 :LNP1(x)-x: -.063527763379 } "" { :CHAN (.458): -8.09343664135E-2 :LNP1(x)-x: -.080934366414 } "" { :CHAN (.467): -8.37805008392E-2 :LNP1(x)-x: -.083780500839 } "" { :CHAN (.5): -9.45348918922E-2 :LNP1(x)-x: -.094534891892 } "" { :CHAN (1): -.306852819442 :LNP1(x)-x: -.30685281944 } "" { :CHAN (2): -.901387711332 :LNP1(x)-x: -.90138771133 } { :CHAN (10): -7.60210472716 :LNP1(x)-x: -7.6021047272 } "" { :CHAN (100): -95.3848794836 :LNP1(x)-x: -95.3848794832 } "" { :CHAN (1000): -993.09124522 :LNP1(x)-x: -993.091245221 } "" { :CHAN (100000.): -99988.487064 :LNP1(x)-x: -99988.4870645 } "" { :CHAN (1000000): -999986.184488 :LNP1(x)-x: -999986.184488 |
|||
02-04-2024, 12:06 PM
(This post was last modified: 02-04-2024 01:10 PM by Gil.)
Post: #7
|
|||
|
|||
RE: HP49-50G: help for recursive
Here below FLN5, almost the same recursive program as FLN4.
Difference Here, contrarily to previous recursive program FLN4, we don't play fully with the stack (with such commands as SWAP or others) after the call of FLN5 in the THEN branch, but with the variable x (the different, calculated variables x) explicitly called back each time (2* x² -). Observation 1 Such a solution might be clearer if the above expression in x in the parenthesis (2* x² -, in our case) were really complicated to play fully with the stack commands such as SWAP — and that we had instead an algebraic expression 'f(x)'. Observation 2 Regarding the ELSE branch, it concerns normally the last n transformed value of x, x[n]. Therefore, when we jump back, at the end of the ELSE branch, to the THEN branch, the x value of that THEN branch won't be anymore x[n], but the previous one, x[n-1]. In other words, in the THEN branch, the expected execution of 2* x[n]² - will never occurr. However, it must be executed exactly once before the execution of 2* x[n-1]² in the THEN branch. Remedy: add that missing special 2* x[n]² - at the end of the ELSE branch, just before the jump to the THEN branch. Observation 3 The above remedy should never be applied for the special cases when the absolute value of (initial input xo) <0.4, ie when the THEN branch was never executed. Hence a special test (with the variable 'max') at the end of that ELSE branch. Observation 4 We don't want that, in the THEN branch, the sequence 2* x²- to be carried out when last called back value of x is equal to initial input xo. In other words, the sequence 2* x²- in the THEN branch is ok for x[n-1], x[n-2], ..., x[1], but not for x[0]. Hence a special test (with the variable 'max') at the end of that THEN branch. « 0 0 -> x X2 X4 « IF x ABS .4 >≠ THEN IFERR 'max' RCL THEN x SWAP STO ELSE DROP END 'x/(sqrt(1+x)+1)' ->NUM FNL5 IF x max ≠ THEN 2 * x SQ - ELSE 'max' PURGE END ELSE 'x/(x+2)' ->NUM 'X2' STO X2 DUP * 'X4' STO 'X4*(5005-X4*(5082-X4*969))/(15015-X4*(24255-X4*(11025-X4*1225)))' ->NUM 'X4' STO 'X2*(X4+X4-x)' ->NUM IFERR 'max' RCL THEN DROP ELSE DROP 2 * x SQ - END END » » Learning purpose My solution with the 'max' variable seems to me very cumbersome. As I lack of practice with recursive programming, if somebody comes with a simpler/better approach for that recursive program playing with the algebraic mode/expression containing the effective x[i] called back variables (such as 'f(x)', and not fully with the stack), it would be of course most appreciated. Code: \<< 0 0 \-> x X2 X4 |
|||
02-06-2024, 11:14 AM
Post: #8
|
|||
|
|||
RE: HP49-50G: help for recursive
Hi,
Not sure if this solves your case but at least to avoid global variable 'max' you could use a "compiled local variable", that is, a local variable with first character is an arrow (left or right) I don't remember, but is is in the (advanced) user guide. Those variables are accessible to subsequent calls. Brgds Gjermund |
|||
02-06-2024, 11:57 AM
Post: #9
|
|||
|
|||
RE: HP49-50G: help for recursive
Thanks for your suggestion.
It's left arrow. I would have rather used such a variable. « -> x « IFERR '<-max' RCL THEN x -> <-max « » ELSE DROP END <-max » » What I then need is the <—max variable outside the IF... THEN... END structure. But as the red «» are closed, the <—max after the END vanishes, creating logically an error, having finished its job, unless another program is called internally. But putting <—max inside the red «» means that a lot will also have to be inside the red «». Not that easy to solve properly — for me, at least. Regards, |
|||
02-06-2024, 01:14 PM
Post: #10
|
|||
|
|||
RE: HP49-50G: help for recursive
(02-06-2024 11:57 AM)Gil Wrote: « -> x Why not simply create <-max at the same time you create x? It appears that you initialize the value of <-max to be whatever value x has, so I would think you could change the first line in your code to: « DUP -> x <-max ... That way the scope of <-max is now the same as x, which I believe may be what you want here. This keeps you from having to test if <-max exists, since it is now guaranteed to exist everywhere that x exists. |
|||
02-06-2024, 01:29 PM
Post: #11
|
|||
|
|||
RE: HP49-50G: help for recursive
No!
I want to have max =x, yes, but with the following 2 conditions: - only for the first initial input value of x (afterwards, x is tranformed to a new x at each recursive loop) - and only in the THEN condition for x was fulfilled before (if first IF test never gave THEN once, then max should not exist) |
|||
02-06-2024, 03:51 PM
Post: #12
|
|||
|
|||
RE: HP49-50G: help for recursive
(02-06-2024 01:29 PM)Gil Wrote: I want to have max =x, yes, but Apologies, my suggestion was based on the small snippet you showed, not as a result of studying the previous posts. A quick perusal showed me that I'm not likely to understand what you're actually trying to solve here with the limited time that I can apply to it at present. I'll just make a couple of general observations:
|
|||
02-06-2024, 05:48 PM
Post: #13
|
|||
|
|||
RE: HP49-50G: help for recursive
For my narrow mind, my solution with global variable seems simpler :
1) create max by first execution of the program, and assign to it the initial value of xo. 2) when the recursive loop start again (at the very beginning of the program), as the variable max already exist, leave its value as it is, ie initial input value xo. 3) exception for special case when initial input xo is < 0.4 from the very beginning of the program (the program never executes the THEN condition, but directly and only the ELSE condition and stops. 4) At the end, before terminating the program, we delete maf But I do feel, though it's logical, it's heavy stuff, not elegant at all. |
|||
02-06-2024, 08:51 PM
Post: #14
|
|||
|
|||
RE: HP49-50G: help for recursive
(02-06-2024 05:48 PM)Gil Wrote: But I do feel, though it's logical, it's heavy stuff, not elegant at all. There is no distinctly right or wrong way, just advantages and disadvantages inherent to different approaches. The most important thing is to do it whichever way makes the most sense to you. That ends up being the best way, as it will help over time if you end up having to maintain it. |
|||
02-06-2024, 08:53 PM
(This post was last modified: 02-06-2024 11:11 PM by Gil.)
Post: #15
|
|||
|
|||
RE: HP49-50G: help for recursive
True, and thanks, David.
But understanding new ways permits also to accept and learn from them and adopt them when we think that they are better than our initial answer/solution. And, very often, HP Forum solutions are most inspiring for me — when simply reproduced or, better, understood. Just as a remembrsnce, the basic idea is/was to reproduce, with a recursion on the HP50G, this following small recursive program from Albert Chan: 200 DEF FNL(X) ! = ln(1+X) - X, but more accurate 210 IF ABS(X)>=.4 THEN X=X/(SQRT(1+X)+1) @ FNL=FNL(X)*2-X*X @ GOTO 250 220 X2=X/(X+2) @ X4=X2*X2 230 X4=X4*(5005-X4*(5082-X4*969))/(15015-X4*(24255-X4*(11025-X4*1225))) 240 FNL=X2*(X4+X4-X) F(.3) —>-3.76357355325E-2 F(2.) —> -.901387711332 F(100.) —> -95.3848794836 Regards, Gil |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 6 Guest(s)