HP49-50G: help for recursive

[Gil]

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
  \<<
    WHILE x ABS .4 \>=
    REPEAT x l + 'l' STO 'x/(\v/(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
  \>>

\>>

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

[Gil]

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
»
»

[Albert Chan]

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

[Albert Chan]

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.

[Gil]

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
  \<<
    IF x ABS .4 \>=
    THEN 'x/(\v/(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
  \>>
\>>

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 ».

[Gil]

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

[Gil]

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
  \<<
    IF x ABS .4 \>=
    THEN
      IFERR 'max' RCL
      THEN x SWAP STO
      ELSE DROP
      END 'x/(\v/(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
  \>>
\>>

[Gjermund Skailand]

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

[Gil]

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,

[DavidM]

(02-06-2024 11:57 AM)Gil Wrote:  « -> 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.

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.

[Gil]

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)

[DavidM]

(02-06-2024 01:29 PM)Gil Wrote:  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)

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:

• Compiled locals only make sense to use if you want to reference a local from a program that doesn't also contain that local's instantiation (-> command). Otherwise just create a normal local, perhaps at a higher scope level within that same program.
• Instead of checking for the existence of the local variable, could you STO 0 into it (before the first recursive call) to imply that no value has yet been stored? If so, it would simplify the check by allowing you to treat max as a boolean as well as the max x value. "IF max THEN...ELSE...END" would process the ELSE clause iff max=0, otherwise the THEN clause applies. That obviously wouldn't work if max=0 could occur with the normal processing of x values. I honestly don't know if that is appropriate here, though.
  

[Gil]

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.

[DavidM]

(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.

[Gil]

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