What comes next?

[Gil]

Gilles, hi.

I want to try your code but I don't use libraries (LstX library).


In your code
«
DUPDUP RHEAD SWAP
2 OVER SIZE START
ΔLIST DUP RHEAD ROT + SWAP
NEXT
+ ADD

how are defined
RHEAD & ΔLIST, please?

Thanks for your help.

Regards,
Gil

[Thomas Klemm]

(10-15-2024 01:34 PM)Gil Wrote:  My next question is if I may ask: what is the code algorithm you used in your first post to get the binomial coefficient?

Let me again add some comments:

Code:

00 { 24-Byte Prgm }         ; a_n
01 1                        ; 1 a_n
02 RCL+ 00                  ; n+1 a_n
03 STO 00                   ; n=n+1 a_n
04 X<>Y                     ; a_n n
05 ENTER                    ; a_n Σa=a_n n
06 GTO 01                   ; jump to label 01
07▸LBL 00                   ; repeat
08 RCL- IND ST Z            ; Δa_k=a_{k+1}-a_k Σa k
09 STO+ ST Y                ; Δa_k Σa=Σa+Δa_k k
10▸LBL 01                   ; a_k Σa k
11 STO IND ST Z             ; R[k]=a_k
12 DSE ST Z                 ; a_k Σa k=k-1
13 GTO 00                   ; until k==0 
14 R↓                       ; Σa
15 END

We keep the increasing number of elements \(n\) in register 00.
Let's assume we're at the situation of post #4 and we want to add 35.

The difference is calculated in register X while the sum for the next value is calculated in register Y:

\(
\begin{array}{|l|l|l|}
\hline
X & Y & Z \\
\hline
35 & 35 & 6 \\
15=35-20 & 50=35+15 & 5 \\
5=15-10 & 55=50+5 & 4 \\
1=5-4 & 56=55+1 & 3 \\
0=1-1 & 56=56+0 & 2 \\
0=0-0 & 56=56+0 & 1 \\
\hline
\end{array}
\)

Meanwhile the counter in register Z is decremented until it is 0.

---

I suggest to give Free42 a try.
You can copy and paste the program when the simulator is in program mode: PRGM.
Switch back and clear the registers with CLEAR ▼ CLRG.
And then just follow the example.
Press ▼ to single step through the program.

[Thomas Klemm]

(10-15-2024 01:34 PM)Gil Wrote:  Last question, what will you get in your calculator or l'émulation for the next number of the following list?
{ 17 72 97 8 32 15 63 97 57 60 83 48 26 12 62 3 49 55 77 97 98 0 89 57 34 92 29 75 13 40 3 2 3 83 69 1 48 87 27 54 92 3 67 28 97 56 63 }

Using Free42:
-313'323'742'215'540

---

This is the contents of the registers:

00: 47
01: 5'958'939'610'275
02: -78'383'926'242'917
03: -81'440'397'593'595
04: -61'857'014'876'959
05: -41'068'588'193'054
06: -25'166'184'482'905
07: -14'575'039'183'813
08: -8'077'783'405'239
09: -4'315'910'331'471
10: -2'233'812'545'366
11: -1'123'843'700'063
12: -551'048'120'900
13: -263'882'576'032
14: -123'622'702'625
15: -56'724'531'441
16: -25'506'257'595
17: -11'232'717'406
18: -4'834'604'086
19: -2'024'788'492
20: -819'077'008
21: -316'401'610
22: -114'802'997
23: -38'274'698
24: -11'472'693
25: -3'158'214
26: -1'009'379
27: -554'630
28: -400'969
29: -243'086
30: -83'702
31: 34'596
32: 95'896
33: 109'634
34: 95'153
35: 70'112
36: 45'767
37: 27'055
38: 14'703
39: 7'456
40: 3'600
41: 1'701
42: 805
43: 376
44: 158
45: 48
46: 7
47: 63

[Gilles]

(10-15-2024 01:53 PM)Gil Wrote:  how are defined
RHEAD & ΔLIST, please?

In NewRPL ?

RHEAD : << DUP SIZE GET >>
ΔLIST is the the same than in stock RPL
In NewRPL with lists, the commands + and ADD are switched.

With stock HP50, the program could be (not tested) :

Code:

«
 DUPDUP DUP SIZE GET SWAP
 2 OVER SIZE START
   ΔLIST DUPDUP SIZE GET ROT + SWAP 
 NEXT
 + +
»

[John Keith]

(10-14-2024 08:35 PM)Gilles Wrote:  newRPL with LstX library. Enter the first numbers as a list and you get a list with a new guess number. etc.

Code:

«
 DUPDUP RHEAD SWAP
 2 OVER SIZE START
   ΔLIST DUP RHEAD ROT + SWAP 
 NEXT
 + ADD
»

For "Old RPL" with the ListExt Library, RHEAD can be replaced by LPOPR NIP.

[John Keith]

(10-15-2024 04:08 PM)Gilles Wrote:  In NewRPL with lists, the commands + and ADD are switched.

With stock HP50, the program could be (not tested) :

Code:

«
 DUPDUP DUP SIZE GET SWAP
 2 OVER SIZE START
   ΔLIST DUPDUP SIZE GET ROT + SWAP 
 NEXT
 + +
»

The last line should be ADD + .

[FLISZT]

(10-15-2024 05:39 PM)John Keith Wrote:  

(10-14-2024 08:35 PM)Gilles Wrote:  newRPL with LstX library. Enter the first numbers as a list and you get a list with a new guess number. etc.

Code:

«
 DUPDUP RHEAD SWAP
 2 OVER SIZE START
   ΔLIST DUP RHEAD ROT + SWAP 
 NEXT
 + ADD
»

For "Old RPL" with the ListExt Library, RHEAD can be replaced by LPOPR NIP.

… and with the GoferLists (1.0) Library (another jewel), RHEAD can be replaced by Last (with a capital L).

[Thomas Klemm]

(10-15-2024 04:08 PM)Gilles Wrote:  With stock HP50, the program could be (not tested) :

Code:

«
 DUPDUP DUP SIZE GET SWAP
 2 OVER SIZE START
   ΔLIST DUPDUP SIZE GET ROT + SWAP 
 NEXT
 + +
»

This works mostly with an HP-48:

Code:

DIR
  NXT
    \<< DUP LST OVER 2 OVER SIZE
      START \GDLIST DUP LST ROT + SWAP
      NEXT DROP +
    \>>
  LST
    \<< DUP SIZE GET
    \>>
END

For a list with a single element I get:

ΔLIST Error: Invalid Dimension

[Thomas Klemm]

I wondered why I used this in my T program but now NXT also works with a single element list:

Code:

\<< DUP LST OVER
  WHILE DUP SIZE 1 >
  REPEAT \GDLIST DUP LST ROT + SWAP
  END DROP
\>>

Also the usage is similar to my initial program since the last + command was removed.
If the prediction of what comes next matches, add it to the list.
Otherwise DROP it and add the proper one.

[Gil]

Question to Gilles relative to his post #24

Changing last line + + into ADD +

Code:


\<< DUPDUP DUP SIZE GET SWAP 2 OVER SIZE
  START \GDLIST DUPDUP SIZE GET ROT + SWAP
  NEXT ADD +
\>>

and building

Code:


\<< { } 0 3
  FOR i '2*i^2+3*i+5' EVAL +
  NEXT
\>>

we get { 5 10 19 32 }.

Deleting the number 32 from the above list,
we get { 5 10 19 }
and with that latter list as argument with your program we get 36 instead of "my" 32.

Question:
How is it possible?
If the 4th number were indeed 36, as given by your program, then the underlying polynomial should be f(x): '2/3*x^3+13/3*x+5'
and the next number after 36 would be (with the above given new polynomial) 65.
But, with the sequence list {5 10 19 36}, your output is then 69, and not 65.

Regards,
Gil

[Thomas Klemm]

(10-16-2024 10:14 AM)Gil Wrote:  How is it possible?

It's a bug in the program: the last number is counted twice.
Once from extracting the element with GET from the list { 4 } and then ADD-ing it to { 4 }.
The fix is to replace ADD by DROP.

[Gil]

Thanks again to all contributers.

Just test Gilles' astonishing compact and extremely fast program : less than 0.05 second vs several minutes with my program to get the next number after { 17 72 97 8 32 15 63 97 57 60 83 48 26 12 62 3 49 55 77 97 98 0 89 57 34 92 29 75 13 40 3 2 3 83 69 1 48 87 27 54 92 3 67 28 97 56 63 }, which is -313323742215540.

Congratulations!

[John Keith]

(10-16-2024 01:17 PM)Gil Wrote:  Thanks again to all contributers.

Just test Gilles' astonishing compact and extremely fast program : less than 0.05 second vs several minutes with my program to get the next number after { 17 72 97 8 32 15 63 97 57 60 83 48 26 12 62 3 49 55 77 97 98 0 89 57 34 92 29 75 13 40 3 2 3 83 69 1 48 87 27 54 92 3 67 28 97 56 63 }, which is -313323742215540.

Congratulations!

You must have a very fast computer. That takes about 0.18 seconds on my old laptop which means about 7 seconds on a physical calc (I didn't bother to type the whole list into my 50g.)

Note also that the result will be meaningless unless the initial sequence is defined by a polynomial.

[Gilles]

(10-16-2024 04:54 PM)John Keith Wrote:  You must have a very fast computer. That takes about 0.18 seconds on my old laptop which means about 7 seconds on a physical calc (I didn't bother to type the whole list into my 50g.)

Note also that the result will be meaningless unless the initial sequence is defined by a polynomial.

In newRPL I confirm that it takes 0.048 sec with the physical 50g and 0 sec on my laptop with the Windows version. A 140x faster ratio between newRPL and RPL does not surprise me for this kind of calculation.

[Thomas Klemm]

This program might be faster:

Code:

\<< DUP ROT + SWAP DUP { } + SWAP ROT
  \<< - ROT OVER + SWAP ROT OVER + SWAP
  \>> STREAM DROP
\>>

It is of order \(\mathcal{O}(n)\) instead of \(\mathcal{O}(n^2)\) and works similarly to my initial program for the HP-42S.

Example

{ 1 }
2
NXT

{ 2 1 }
3

DROP 4
NXT

{ 4 2 1 }
7

DROP 8
NXT

{ 8 4 2 1 }
15

DROP 16
NXT

{ 16 8 4 2 1 }
31

NXT

{ 31 15 7 3 1 0 }
57

NXT

{ 57 26 11 4 1 0 0 }
99

NXT

{ 99 42 16 5 1 0 0 0 }
163

NXT

{ 163 64 22 6 1 0 0 0 0 }
256

[Thomas Klemm]

The same program with stack comments:

Code:

\<<                     @ A a
  DUP ROT +             @ a A=a+A
  SWAP DUP { } +        @ A Σ=a S={a}
  SWAP ROT              @ S Σ A
  \<<                   @ S Σ a a'
    -                   @ S Σ Δa=a-a'
    ROT OVER + SWAP     @ Σ S=S+Δa Δa
    ROT OVER + SWAP     @ S Σ=Σ+Δa Δa
  \>>                   @ S Σ a=Δa
  STREAM DROP           @ S Σ
\>>

[Gil]

Precisions regarding the execution (time) for finding the next number of the polynomial that creates the initial string
{ 17 72 97 8 32 15 63 97 57 60 83 48 26 12 62 3 49 55 77 97 98 0 89 57 34 92 29 75 13 40 3 2 3 83 69 1 48 87 27 54 92 3 67 28 97 56 63}:

1) time to find out f(47), the 48th number = -313323742215540: about 0.05 s (most of the time about 0.049s, but maximum time 0.058s);

2) Code used (\GS is —>capital delta)

Code:


\<< DUPDUP DUP SIZE GET SWAP 2 OVER SIZE
  START \GDLIST DUPDUP SIZE GET ROT + SWAP
  NEXT DROP +
\>>

3) No NewRPL, but original user RPL;

4) No computer, but EMU48 on Samsung phone A53;

5) Like 4, but with setting "Authentication Calculator Speed": about 5.3s —> here then more than 100 times slower.

[Gilles]

A recursive version en newRPL :

Next?

Code:

« DUP RHEAD SWAP ΔLIST DUP SIZE 1 > « Next? »  IFT + »

ex : { 0 0 0 0 1 5 15 35 70 126 } Next? -> { 210 }

[Gil]

Is really the above code complete as lastly written by Gilles?

[John Keith]

(10-18-2024 10:49 PM)Gil Wrote:  Is really the above code complete as lastly written by Gilles?

It works in "OldRPL" if you change RHEAD to DUPDUP SIZE GET and change the final + to ADD. (Remember, the functionality of + and ADD are reversed in NewRPL.)