HP 38G: Better than Prime for some Sequences using the built in Sequence App

[Thomas Ritschel]

(03-07-2015 10:53 AM)Gerald H Wrote:  I entered the prog exactly as above, respecting capitalization.

I have read elsewhere on the forum that capitals or uncials can make all the difference. I shall try.

Just tested on the Prime and it works.

For convenience here the full program:

Code:

EXPORT TT(n)
BEGIN
  IF n<=2 THEN
    RETURN(1);
  ELSE
    LOCAL TT1:=TT(n-1);
    RETURN(TT(TT1)+TT(n-TT1));
  END;
END;

[Gerald H]

(03-07-2015 10:46 AM)Thomas Ritschel Wrote:  

(03-07-2015 10:41 AM)Gerald H Wrote:  Still won't work on Prime.

Make sure that you changed the line

Code:

IF N<=2 THEN

into

Code:

IF n<=2 THEN

Otherwise the Prime may recognize N and n as different variables...

Below the prog as now on my Prime. When called from home with argument 5 causes a freeze that's difficult to escape from.

How have I erred?

   

[Gerald H]

(03-07-2015 10:58 AM)Thomas Ritschel Wrote:  

(03-07-2015 10:53 AM)Gerald H Wrote:  I entered the prog exactly as above, respecting capitalization.

I have read elsewhere on the forum that capitals or uncials can make all the difference. I shall try.

Just tested on the Prime and it works.

For convenience here the full program:

Code:

EXPORT TT(n)
BEGIN
  IF n<=2 THEN
    RETURN(1);
  ELSE
    LOCAL TT1:=TT(n-1);
    RETURN(TT(TT1)+TT(n-TT1));
  END;
END;

Yes, this works.

[Gerald H]

In Home view TT(99) takes 130 sec.

Compare this with

http://www.hpmuseum.org/forum/thread-3292.html

Bravo BruceH & Thomas Ritschel, the best solution so far.

I take my hat off to you.

[Gerald H]

(03-07-2015 11:16 AM)Gerald H Wrote:  In Home view TT(99) takes 130 sec.

Compare this with

http://www.hpmuseum.org/forum/thread-3292.html

Bravo BruceH & Thomas Ritschel, the best solution so far.

I take my hat off to you.

On the 38G 99 takes 122sec

& 40gs takes 39 sec.

The performance of the Prime is disappointing.

[Marcus von Cube]

(03-07-2015 11:29 AM)Gerald H Wrote:  On the 38G 99 takes 122sec

& 40gs takes 39 sec.

The performance of the Prime is disappointing.

There is a reason: The implementation with the TT routine evaluates each element of the sequence from scratch while the sequence app recurses on the previous results. Maybe storing the previous values in a list instead of performing a recursive call will give better run times. This of course makes the calls to TT not independent from each other.

[BruceH]

(03-07-2015 11:39 AM)Marcus von Cube Wrote:  

(03-07-2015 11:29 AM)Gerald H Wrote:  On the 38G 99 takes 122sec

& 40gs takes 39 sec.

The performance of the Prime is disappointing.

There is a reason: The implementation with the TT routine evaluates each element of the sequence from scratch while the sequence app recurses on the previous results. Maybe storing the previous values in a list instead of performing a recursive call will give better run times. This of course makes the calls to TT not independent from each other.

and I did say it was my 'revenge' :-)

Here is a list optimised version that is much quicker. Make sure you delete the contents of L1 before the first run. The results go into L1 and can be viewed from the List view (shift + 7).

Code:

EXPORT TT(n)
BEGIN
  LOCAL k, s;
  s := SIZE(L1);
  IF s <= 2 THEN
    L1 := {1,1}; s:= 2;
  END;
  IF s < n THEN
    FOR k FROM s+1 TO n DO
      L1(k) := L1(L1(k-1))+L1(k-L1(k-1));
    END
  END;
  RETURN L1(n);
END;

NB: Sometimes you get "Error:invalid input" on the first run. Just run it again. You can still use it from the sequence app if you wish, just assign U1(3) := TT(N) as before.

[Gerald H]

(03-07-2015 11:39 AM)Marcus von Cube Wrote:  

(03-07-2015 11:29 AM)Gerald H Wrote:  On the 38G 99 takes 122sec

& 40gs takes 39 sec.

The performance of the Prime is disappointing.

There is a reason: The implementation with the TT routine evaluates each element of the sequence from scratch while the sequence app recurses on the previous results. Maybe storing the previous values in a list instead of performing a recursive call will give better run times. This of course makes the calls to TT not independent from each other.

Indeed.

All the more reason to regret that the Sequence App in the Prime can't do the calculation as easily as it's useless predecessors.

[Didier Lachieze]

Here is a way to do it on the Prime Sequence app without performance issues by using the Sequence app variables:

• select the Sequence app
• go to Home
• got to Programs
• open Sequence(App)
• replace the program with the one below:
  

Code:

EXPORT TT(n)
BEGIN
IF n≤2 THEN
  RETURN(1);
ELSE
  RETURN(U1(U1(n-1))+U1(n-U1(n-1)));
END;
END;

• then go back to the Sequence app
• enter U1(N)=TT(N)
• go to Num view to see all the values
  

EDIT: display is smooth until N=361, after that it's much slower. I don't know why.

[Gerald H]

(03-07-2015 11:58 AM)BruceH Wrote:  

(03-07-2015 11:39 AM)Marcus von Cube Wrote:  There is a reason: The implementation with the TT routine evaluates each element of the sequence from scratch while the sequence app recurses on the previous results. Maybe storing the previous values in a list instead of performing a recursive call will give better run times. This of course makes the calls to TT not independent from each other.

and I did say it was my 'revenge' :-)

Here is a list optimised version that is much quicker. Make sure you delete the contents of L1 before the first run. The results go into L1 and can be viewed from the List view (shift + 7).

Code:

EXPORT TT(n)
BEGIN
  LOCAL k, s;
  s := SIZE(L1);
  IF s <= 2 THEN
    L1 := {1,1}; s:= 2;
  END;
  IF s < n THEN
    FOR k FROM s+1 TO n DO
      L1(k) := L1(L1(k-1))+L1(k-L1(k-1));
    END
  END;
  RETURN L1(n);
END;

NB: Sometimes you get "Error:invalid input" on the first run. Just run it again. You can still use it from the sequence app if you wish, just assign U1(3) := TT(N) as before.

Excellent stuff. Input 9999 & answer returned in 45 sec. A student of mine confirms 5372 is the correct answer.

Once again bravo, BruceH.

Concerning revenge, 'tis sweet, & so is learning something new.

Edit: Title of thread updated.

[Tugdual]

Can you explain how you do that on the 38G?
I did the same on the 48G and it simply takes ages...

This is what I used:

Code:


U1
« → N
  « N 3 <
    « 1
    »
    « N 1 - U1 DUP U1 SWAP N - NEG U1 +
    » IFTE
  »
»

[Gerald H]

(03-07-2015 01:08 PM)Tugdual Wrote:  Can you explain how you do that on the 38G?
I did the same on the 48G and it simply takes ages...

This is what I used:

Code:


U1
« → N
  « N 3 <
    « 1
    »
    « N 1 - U1 DUP U1 SWAP N - NEG U1 +
    » IFTE
  »
»

Yes, first item in this thread:

http://www.hpmuseum.org/forum/thread-3278.html

[Tugdual]

That simple? I thought it was the problem statement

[Gerald H]

(03-07-2015 02:02 PM)Tugdual Wrote:  That simple? I thought it was the problem statement

In truth, very simple on the 38G.

[Tugdual]

I had a quick look on the hp38 user guide. I guess you used RECURSE didn't you? There is nothing equivalent on the 48G.

[Gerald H]

(03-07-2015 04:58 PM)Tugdual Wrote:  I had a quick look on thé hp38 user guide. I guess you used RECURSE didn't you? There is nothing equivalent on the 48G.

Here are the two progs that install the sequence symbolics in the Sequence App:

SEQSET sets flags & clears any previous symbolics.

HP38AscD 6 SEQSETSELECT Sequence:
UNCHECK 0:
0\|>NumFont:
0\|>Simult:
2\|>Angle:
1\|>InvCross:
1\|>NumStep:
1\|>Format:
1\|>NumCol:
1\|>NumStart:
6\|>NumRow:
RECURSE(U,0,0,0)\|>U1(N):
Ans\|>U2(N):
Ans\|>U3(N):
Ans\|>U4(N):
Ans\|>U5(N):
Ans\|>U6(N):
Ans\|>U7(N):
Ans\|>U8(N):
Ans\|>U9(N):
Ans\|>U0(N):

A004001 sets the symbolics for the sequence.

HP38AscD 7 A004001RUN SEQSET:
RECURSE(U,U(U(N-1))+U(N-U(N-1)),1,1)\|>U1(N):
CHECK 1:

[Gerald H]

(03-07-2015 04:58 PM)Tugdual Wrote:  I had a quick look on the hp38 user guide. I guess you used RECURSE didn't you? There is nothing equivalent on the 48G.

You're correct, there's no such instruction for 48S or G.

[Tugdual]

Thank you Gerald very much appreciated you spent the time to document. In the mean time I learn RPL on the 48, will try to improve the speed of my first attempt using lists to reduce the number of loops.

[Tugdual]

Using a buffer list I could finally achieve decent times on the 48G. I have 4 objects.
1. PU1 creates the list
2. U1 "optimized" recursion loop
3. STPW a simple stop watch
4. TU1 is the variable that contains the list of U(n) values.

Code:

PU1
« → N
  « 'TU1' PURGE
    « 0
    » 'X' 1 N 1 SEQ TU1 STO
  »
»

Code:

U1
« → N
  « TU1 N GET DUP 0 ==
    « DROP N 3 <
      « 1
      »
      « N 1 - U1 DUP U1 SWAP N - NEG U1 +
      » IFTE
    » IFT DUP 'TU1' N 3 ROLL PUT
  »
»

Code:

STPW
« TICKS → T 
  « EVAL TICKS T - 8192 / B→R
  »
»

Usage:
99 ENTER
Call PU1 from VAR menu

99 ENTER
'U1' ENTER
Call STPW from VAR menu

2: 56
1: 75 (1'15'')

Decent results. I can't help thinking that the 38G does something similar to avoid 2 millions recursions... The previous pure recursion version I posted was not finished after +30mn.
Was cool to play with RPL. What a strange language :-)

[Gerald H]

(03-07-2015 05:29 AM)BruceH Wrote:  

(03-07-2015 01:41 AM)Joe Horn Wrote:  Fascinating. The 40gs handles it fine too. I wonder why the 39gii and Prime balk at it.

It's to do with the use of U1 as the index to U1. I tried setting U2 to be U1(N-1) and making the appropriate substitution and that still fails. Creating a user defined function TT(N)=U1(N-1) and substituting also fails. So I think the Sequence app is scanning the parse tree in an effort to avoid a recursive loop and is rejecting cases that would actually work.

Explanation not correct.

Try:

U1(1)=3
U1(2)=8
U1(N)=U1(N-1)-U1(N-2)

Tickable, ticked & numerically correct!