Threaded Mode | Linear Mode

Dave Britten · 10-17-2022, 06:29 PM

(10-17-2022 06:01 PM)Valentin Albillo Wrote:
Dave Britten Wrote:Sharp PC-1403H version of Valentin's 71B program (I didn't really have to change much, aside from minor syntactic/keyword differences) [...] This model takes about 4 hours to run for the 30, 60 case [...]

Thanks for taking the trouble to key in my program into the PC-1403H, appreciated. That model is slow as molasses and the fact that you had to use FOR..NEXT loops to clear and copy matrices at each of the 60 steps slows down the program even further.

I would be curious to know how long does it take Mr. Chan's fastest non-symmetric (general) program to run the (30, 60) case in: (a) The 1403H, and (b) a physical HP-71B, if you'd obligue.

V.

The results are in: it took around 4 hours to run the 30, 60 scenario on the pure-BASIC 1403H program. But it looks like I can speed this up by using the ROM-based matrix routines to handle copying/swapping/zeroing the matrices. Current estimates with smaller parameters suggests I might trim 1/3 off the runtime. We'll see! It's only been going about 20 minutes now.

I'll have to take a look at Albert's program and see if that might be usable (and possibly faster) here.

Albert Chan · 10-17-2022, 08:16 PM

(10-17-2022 06:29 PM)Dave Britten Wrote: I'll have to take a look at Albert's program and see if that might be usable (and possibly faster) here.

My flattened array code use little memory, and fast (fastest so far, without using symmetry)

The code use MAT Q=P, but it is not necessary.
All it need is to swap the name of 2 arrays. Sadly, VARSWAP P, Q does not work.

Here is a version that simulate swapping of array name.

Array P of x ≡ A(P, x)
Array Q of x ≡ A(Q, X)

Note: P, Q are now numbers 0 or 1, P+Q=1, not the array itself.

10 DESTROY ALL @ INPUT "[VA]SRC012A R,S= ";R,S @ SETTIME 0
20 OPTION BASE 0 @ REAL A(1,(R+1)*(R+4)/2) @ P=0
30 A(P,2)=1 @ M=2
40 FOR K=1 TO S
50 Q=P @ P=1-P @ A(Q,2)=A(Q,2)*3 @ T=3 ! BUILD Q
60 FOR I=2 TO M-(M=R) @ X=T+1 @ A(Q,X)=A(Q,X)*1.5 @ X=T+I @ A(Q,X)=A(Q,X)*1.5 @ T=X+1 @ NEXT I
70 IF M<>R THEN 100
80 FOR X=T+2 TO T+R-1 @ A(Q,X)=A(Q,X)*1.5 @ NEXT X
90 T=T+1 @ A(Q,T)=A(Q,T)*3 @ A(Q,X)=A(Q,X)*3
100 T=1 @ FOR I=1 TO M @ FOR X=T+1 TO T+I ! BUILD P
110 A(P,X)=A(Q,X-I-1)+A(Q,X-I)+A(Q,X-1)+A(Q,X+1)+A(Q,X+I+1)+A(Q,X+I+2)
120 NEXT X @ T=X @ NEXT I
130 M=M+(M<R)
140 DISP K;TIME
150 NEXT K
160 T=0 @ K=R*(R+1)/2 @ FOR X=K+1 TO K+R @ T=T+A(P,X) @ NEXT X
170 DISP TIME;R;S;T/6^S

>RUN
[VA]SRC012A R,S= 30,60
...
91.38 30 60 9.51234350205E-6

Not as good as original flattened array version (83.1 sec), but not too bad.

Valentin Albillo · 10-17-2022, 08:38 PM

(10-17-2022 08:16 PM)Albert Chan Wrote: Here is a version that simulate swapping of array name [...]
>RUN
[VA]SRC012A R,S= 30,60
...
91.38 30 60 9.51234350205E-6

Just one question: the quoted time (91.38 seconds) applies when your program is run on what machine ? A physical HP-71B ? If not, what's the time for a physical HP-71B ?

Thanks and regards.
V

Albert Chan · 10-17-2022, 09:19 PM

(10-17-2022 08:38 PM)Valentin Albillo Wrote:
(10-17-2022 08:16 PM)Albert Chan Wrote: Here is a version that simulate swapping of array name [...]
>RUN
[VA]SRC012A R,S= 30,60
...
91.38 30 60 9.51234350205E-6

Just one question: the quoted time (91.38 seconds) applies when your program is run on
what machine ?

It was Emu71/DOS, running under DOSBOX, at cycles = max 50%, on my laptop

Running [VA] code on same condition, it clocked at 126.92 seconds.
Fastest so far is my flattened array code, clocked at 83.10 seconds.

All 3 codes can handle non-symmetrical starting conditions.

Albert Chan · 10-17-2022, 09:36 PM

When I time MAT P=ZER vs. MAT P=(0), I see no difference.

Is it the same on an actual HP71B ?

Fernando del Rey · 10-17-2022, 10:49 PM

In a physical HP-71B I got the following timing for AC's program in post #62

2464.74 30 60 9.51234350205E-6

Thus, a little over 41 minutes.

J-F Garnier · 10-18-2022, 08:00 AM

(10-17-2022 06:29 PM)Dave Britten Wrote: The results are in: it took around 4 hours to run the 30, 60 scenario on the pure-BASIC 1403H program.

What is the numeric result? I'm curious to compare the accuracy too, is the 1403H a 12-digit machine and does it manage the "round-to -even" rule? I gave a simple test to check it above.

(10-17-2022 08:16 PM)Albert Chan Wrote: Here is a version that simulate swapping of array name.
Array P of x ≡ A(P, x)
Array Q of x ≡ A(Q, X)
Note: P, Q are now numbers 0 or 1, P+Q=1, not the array itself.
[..]

20 OPTION BASE 0 @ REAL A(1,(R+1)*(R+4)/2) @ P=0

I don't see the benefit of this version, you are still using the same amount of memory, and the access to the array A is slower which is not compensated by the gain of the MAT copy.

(10-17-2022 09:36 PM)Albert Chan Wrote: When I time MAT P=ZER vs. MAT P=(0), I see no difference.

There is a difference, MAT P=ZER is about 2x faster:
10 DIM A(4096)
20 T=TIME @ MAT A=ZER @ T=TIME-T @ DISP T
20 T=TIME @ MAT A=(0) @ T=TIME-T @ DISP T
>RUN
.38
.76
(physical HP-71B)
However, if you target the smallest code, MAT A=(0) is one byte shorter :-)

J-F

Werner · 10-18-2022, 08:19 AM

(10-18-2022 08:00 AM)J-F Garnier Wrote:
(10-17-2022 08:16 PM)Albert Chan Wrote: Here is a version that simulate swapping of array name.
Array P of x ≡ A(P, x)
Array Q of x ≡ A(Q, X)
Note: P, Q are now numbers 0 or 1, P+Q=1, not the array itself.
[..]

20 OPTION BASE 0 @ REAL A(1,(R+1)*(R+4)/2) @ P=0
I don't see the benefit of this version, you are still using the same amount of memory, and the access to the array A is slower which is not compensated by the gain of the MAT copy.

No, it uses only half the memory, roughly?
Werner

J-F Garnier · 10-18-2022, 09:08 AM

(10-16-2022 05:52 PM)Valentin Albillo Wrote: So, this is my original solution, a 13-line, 683-byte program.
[..]
Now for the big (30, 60) case:
>RUN
Rows,Steps= 30,60 [ENDLINE] -> 9.51234350207E-6 27.46"

(10-17-2022 08:38 PM)Valentin Albillo Wrote:
(10-17-2022 08:16 PM)Albert Chan Wrote: Here is a version that simulate swapping of array name [...]
>RUN
[VA]SRC012A R,S= 30,60
...
91.38 30 60 9.51234350205E-6

Just one question: the quoted time (91.38 seconds) applies when your program is run on what machine ? A physical HP-71B ? If not, what's the time for a physical HP-71B ?

With the various machines and platforms running HP-71 code (Android, Windows, go71, Emu71/Win, Emu71/DOS w/ or w/o DOSBox), it's difficult to compare execution times.
Downloading and running each code on a physical HP-71 is not convenient, and not everybody has the means to do it - although they should :-)

So I propose the use Valentin's solution as the reference.
Here are the results for my solution:
VA's reference solution: 91"
my solution : 63" = 0.69 in Valentin's units :-)
Note I used the symmetry of the problem.

J-F

Albert Chan · 10-18-2022, 11:16 AM

(10-18-2022 08:00 AM)J-F Garnier Wrote:
(10-17-2022 08:16 PM)Albert Chan Wrote: Here is a version that simulate swapping of array name.
Array P of x ≡ A(P, x)
Array Q of x ≡ A(Q, X)
Note: P, Q are now numbers 0 or 1, P+Q=1, not the array itself.
[..]

20 OPTION BASE 0 @ REAL A(1,(R+1)*(R+4)/2) @ P=0
I don't see the benefit of this version, you are still using the same amount of memory, and the access to the array A is slower which is not compensated by the gain of the MAT copy.

That's why it is called simulate swapping of array name.
True variable name swapping should be almost cost free.

It is a proof of concept, showing MAT Q=P is not needed.
The code is useful for machine that use slow FOR-NEXT for MAT copy.
Simulated array name swapping removed the slow FOR-NEXT loops.

Perhaps add MAT SWAP to HP Article VA044 - HP-71B Math Pac 2 Comments and Proposals.pdf ?

Flattened A array of 1 dimension, array access cost almost matched removal of MAT COPY
However, for optimized code, it may be hard to deduce where A is pointing to.
That's why I posted the slower A(P, x) version, instead of faster A(P + x)

Anyway, this was my flattened A version.

Note: we reduced array elements required by 1, but still safe.
Note: Build Q part, to simplify code, T is triangular number minus one, plus Q

10 DESTROY ALL @ INPUT "[VA]SRC012A R,S= ";R,S @ SETTIME 0
20 OPTION BASE 0 @ P=0 @ Q=(R+1)*(R+4)/2 @ REAL A(2*Q)
30 A(2)=1 @ M=2
40 FOR K=1 TO S
50 VARSWAP P,Q @ T=Q+2 @ A(T)=A(T)*3 ! BUILD Q
60 FOR I=1 TO M-(M=R)-1 @ T=T+2 @ A(T)=A(T)*1.5 @ T=T+I @ A(T)=A(T)*1.5 @ NEXT I
70 IF M<>R THEN 100
80 FOR X=T+3 TO T+R @ A(X)=A(X)*1.5 @ NEXT X
90 T=T+2 @ A(T)=A(T)*3 @ A(X)=A(X)*3
100 T=Q+1 @ Y=P-Q @ FOR I=1 TO M @ FOR X=T+1 TO T+I ! BUILD P
110 A(X+Y)=A(X-I-1)+A(X-I)+A(X-1)+A(X+1)+A(X+I+1)+A(X+I+2)
120 NEXT X @ T=X @ NEXT I
130 M=M+(M<R)
140 DISP K;TIME
150 NEXT K
160 T=0 @ K=P+R*(R+1)/2 @ FOR X=K+1 TO K+R @ T=T+A(X) @ NEXT X
170 DISP TIME;R;S;T/6^S

>RUN
[VA]SRC012A R,S= 30,60
...
84.49 30 60 9.51234350205E-6

Very close to fastest MAT Q=P version, clocked at 83.1 sec.

Dave Britten · 10-18-2022, 12:25 PM

(10-18-2022 08:00 AM)J-F Garnier Wrote:
(10-17-2022 06:29 PM)Dave Britten Wrote: The results are in: it took around 4 hours to run the 30, 60 scenario on the pure-BASIC 1403H program.
What is the numeric result? I'm curious to compare the accuracy too, is the 1403H a 12-digit machine and does it manage the "round-to -even" rule? I gave a simple test to check it above.

I get 9.512343561E-06 for the 30, 60 bottom-row case, and the full probability map sums up to 1.000 000 009. I believe most Sharps are 10-digit machines.

Here's an amended version of the program that uses two of the ROM routines for matrix handling. Now it only takes a little over 3 hours to run the full 30, 60. :)

10 CLEAR:INPUT "ROWS?";M:INPUT "STEPS?";N:DIM Y(M,M):DIM X(M,M)
15 Y(1,1)=1:W=M-1:FOR I=1 TO N:X=0:CALL 26153
20 P=Y(1,1)/2:IF P LET X(2,1)=X(2,1)+P:X(2,2)=X(2,2)+P
25 P=Y(M,1)/2:IF P LET X(W,1)=X(W,1)+P:X(M,2)=X(M,2)+P
30 P=Y(M,M)/2:IF P LET X(W,W)=X(W,W)+P:X(M,W)=X(M,W)+P
35 FOR X=2 TO W:U=X-1:V=X+1:P=Y(X,1)/4:Q=Y(X,X)/4:R=Y(M,X)/4
40 IF P LET X(U,1)=X(U,1)+P:X(V,1)=X(V,1)+P:X(X,2)=X(X,2)+P:X(V,2)=X(V,2)+P
45 IF Q LET X(U,U)=X(U,U)+Q:X(V,V)=X(V,V)+Q:X(X,U)=X(X,U)+Q:X(V,X)=X(V,X)+Q
50 IF R LET X(M,U)=X(M,U)+R:X(M,V)=X(M,V)+R:X(W,U)=X(W,U)+R:X(W,X)=X(W,X)+R
55 NEXT X:FOR X=3 TO W:U=X-1:V=X+1:FOR Y=2 TO U:R=Y-1:S=Y+1:P=Y(X,Y)/6
60 IF P LET X(U,R)=X(U,R)+P:X(U,Y)=X(U,Y)+P:X(X,R)=X(X,R)+P
65 IF P LET X(X,S)=X(X,S)+P:X(V,Y)=X(V,Y)+P:X(V,S)=X(V,S)+P
70 NEXT Y:NEXT X:CALL 26163:NEXT I:P=0:FOR Y=1 TO M:P=P+Y(M,Y):NEXT Y:BEEP 3:PRINT P:END
300 "A"S=0:FOR I=1 TO M:FOR J=1 TO I:S=S+Y(I,J):NEXT J:NEXT I:PRINT S:END

The list of matrix routine addresses can be found in message 51 of this thread. These are the two I used:

26153 - Multiply array X() by scalar variable X and store the result back in X() (in this case, I multiply by 0 to zero out the array)
26163 - Swap X() and Y() arrays

J-F Garnier · (This post was last modified: 10-18-2022 03:55 PM by J-F Garnier.)

(10-17-2022 10:49 PM)Fernando del Rey Wrote: In a physical HP-71B I got the following timing for AC's program in post #62

2464.74 30 60 9.51234350205E-6

Thus, a little over 41 minutes.

To restore a little the HP-75 prestige, the same post #62 program (with minor changes°) runs on the 75 as:

1353.469 30 60 9.51234350246E-6

About 23 minutes, or about 2x faster than the HP-71.
Of course the price of the 75, at the time, was also in the prestige class.

° Changes:
5 OPTION BASE 0 @ REAL A(1,527)
10 INPUT "[VA]SRC012A R,S= "; R,S @ T0=TIME
20 REDIM A(1,(R+1)*(R+4)/2) @ P=0
25 MAT A=ZER ! init vars
170 DISP TIME-T0;R;S;T/6^S (I hate to change the clock setting with SETTIME)

J-F

Valentin Albillo · 10-18-2022, 05:15 PM

Hi, J-F,

J-F Garnier Wrote:So I propose the use Valentin's solution as the reference [...]
VA's reference solution: 91"
my solution : 63" = 0.69 in Valentin's units :-)
Note I used the symmetry of the problem.

I don't get it. You say my "reference solution" runs in 91", but ... on which hardware/software !?

As far as I can tell, so far my solution runs in these times:

3496.49" (58’16.49”) on an actual, physical HP-71B (Fernando del Rey dixit)
27.46" on my 4-yo Samsung Galaxy Tab A 6 tablet (Android)
~ 3 hr on a Sharp PC-1403H (Dave Britten dixit)
126.92" on Emu71/DOS, running under DOSBOX, unknown hardware (A.Chan dixit)

so from where did you take those 91" you adscribe to my solution ?

As an additional comment, I don't think that merely comparing runtimes among different solutions is meaningful even for the exact same hardware/software, because other factors also play a big role, among them the following come to mind:

general program (works for any starting positions because it doesn't rely on symmetry) vs. program particularized for symmetric starting positions (rely on symmetry to halve memory requirements and speed up the computation but won't work at all on non-symmetric starting positions.)
didactic program whose inner workings are readily understandable to any newcomer upon seeing the problem's definition and the listing vs. highly-optimized but overwhelmingly unfathomable code to most people upon looking at the listing.
ability to answer the additional questions very easily from the command line once the program has been run vs. very dificult/impossible to answer those additional questions from the command line due to very intrincate element addressing.

As you can see, without taking those factors and others into accound the comparisons are mostly meaningless.

Thanks for your continued interest in this problem and best regards.
V.

Albert Chan · 10-19-2022, 09:55 PM

(10-18-2022 11:16 AM)Albert Chan Wrote: Anyway, this was my flattened A version.

Note: we reduced array elements required by 1, but still safe.
Note: Build Q part, to simplify code, T is triangular number minus one, plus Q

We might as well reduce memory use to its absolute minimum, remove 1 more element.
For consistency, Build P part also defined T as triangular number minus one, plus Q
In other words, A(T) is triangle Q right edge, A(T+2) is Q left edge.

10 DESTROY ALL @ INPUT "[VA]SRC012A R,S= ";R,S @ SETTIME 0
20 OPTION BASE 0 @ P=0 @ Q=(R+1)*(R+4)/2-1 @ REAL A(2*Q+1)
30 A(2)=1 @ M=2
40 FOR K=1 TO S
50 VARSWAP P,Q @ T=Q+2 @ A(T)=A(T)*3 ! BUILD Q
60 FOR I=1 TO M-(M=R)-1 @ T=T+2 @ A(T)=A(T)*1.5 @ T=T+I @ A(T)=A(T)*1.5 @ NEXT I
70 IF M<>R THEN 100
80 FOR X=T+3 TO T+R @ A(X)=A(X)*1.5 @ NEXT X
90 T=T+2 @ A(T)=A(T)*3 @ A(X)=A(X)*3
100 T=Q @ Y=P-Q+1 @ FOR I=1 TO M @ FOR X=T+1 TO T+I ! BUILD P
110 A(X+Y)=A(X-I)+A(X-I+1)+A(X)+A(X+2)+A(X+I+2)+A(X+I+3)
120 NEXT X @ T=X @ NEXT I
130 M=M+(M<R)
140 DISP K;TIME
150 NEXT K
160 T=0 @ K=P+R*(R+1)/2 @ FOR X=K+1 TO K+R @ T=T+A(X) @ NEXT X
170 DISP TIME;R;S;T/6^S

>RUN
[VA]SRC012A R,S= 5,4
...
82.79 30 60 9.51234350205E-6

This version is currently the fastest, but only by a hair.

I like MAT Q=P version better; code is more clear.

Quote:Flattened A array of 1 dimension, array access cost almost matched removal of MAT COPY
However, for optimized code, it may be hard to deduce where A is pointing to.

Albert Chan · (This post was last modified: 10-19-2022 10:05 PM by Albert Chan.)

Running Emu71/Dos under DosBox is slow, with bad timing info.
Running it in WinXP is faster, with more consistent timing.

This despite my Toshiba laptop is supposed to be 10x faster than my 22 years old Dell ... go figures.

HP71B codes so far, running in Dell Optiplex GX110 866MHz, with 512M Ram
All codes adjusted to return only P(R=30,S=60), and time needed.

Timings from best of 3
Symmetry of Yes meant starting condition must be symmetric.

Post    Member              Time(s)    Symmetry    Array elements
21      Fernando del Rey    34.29      No          2*R^2
22      J-F Garnier         12.91      Yes         2*R^2
33      C.Ret               34.94      Yes         3*R^2
35      Albert Chan          9.79      Yes         2*R^2
40      Albert Chan         26.09      Yes         3*R^2
42      Albert Chan          9.79      Yes         2*R^2 + (R+2)*(ceil(R/2)+2)
48      C.Ret                9.79      Yes         2*R^2 + (R+2)*(ceil(R/2)+2)
49      Albert Chan          6.72      Yes         2*(R+2)*(ceil(R/2)+2)
50      Valentin Albillo    17.82      No          2*R^2
51      Albert Chan         12.14      No          2*(R+2)^2
56      Albert Chan         11.42      No          (R+2)*(R+3)
62      Albert Chan         12.79      No          (R+2)*(R+3)
70      Albert Chan         11.86      No          (R+2)*(R+3) - 1
74      Albert Chan         11.32      No          (R+2)*(R+3) - 2

Albert Chan · 10-20-2022, 06:57 PM

(10-13-2022 12:04 PM)Fernando del Rey Wrote: And you could also consider the symmetry of the solution if the man is starting at cell (1,1), calculating only half of the grid. But then the algorithm would not be valid for a starting position which is not located in the central column of the grid, which is therefore not symmetrical.

If the goal is row probability, symmetric solution can still work.

Say, D is starting distribution, D' is its mirror image, P_i is i-th row probability
Note: sum of probability distribution = 1.0

Symmetry: P_i(D) = P_i(D') = P_i(D + D')

Example, below 3 initial conditions produce same row probability.

A(1,1)=1/2 @ A(3,2)=1/6 @ A(3,1)=1/3 ! asymmetric distribution
A(1,1)=1/2 @ A(3,2)=1/6 @ A(3,3)=1/3 ! mirror image
A(1,1)=1/2 @ A(3,2)=1/6 @ A(3,1)=1/6 @ A(3,3)=1/6 ! symmetric distribution

For row probability, we can transform to symmetric distribution, then process only half the grid.

Gjermund Skailand · 10-20-2022, 09:39 PM

This has been a very interesting thread.
This is a sys-rpl version for HP50g of CReth SRC12a.
On an actual HP50g the calculation time for the 30 60 problem is 5 min 21sec.
p= 9.51234350207E-6

"
!RPL
!NO CODE
!JAZZ
::
CK2NOLASTWD
CK&DISPATCH2
#11
:: COERCE2
'
CODE
GOSBVL POP2# RSTK=C SAVE
B=A.A A*A.A A-B.A ASRB.A
C=RSTK A+C.A
GOSBVL PUSH#ALOOP
ENDCODE
3PICK DUP 3PICK EVAL SWAP 2 SWAPOVER
{{ r s d m Tind ii }}
r #1+_ONE_DO (i)
INDEX @ #1+_ONE_DO (j)
3
DUP INDEX@ #1<> ?SKIP #1-
JINDEX@ INDEX@ #<> ?SKIP #1-
JINDEX@ r #<> ?SKIP #1-
UNCOERCE %/
LOOP (j)
LOOP (i)
d UNCOERCE ONE{}N FPTR2 ^XEQ>ARRY
DUP %0 xCON
%1 BINT1 PUTREALEL
s #1+_ONE_DO (k)
INDEX@ #>$ BIGDISPROW1
2DUP m m 2GETEVAL DUP4UNROLL TOTEMPOB (n)
#1+_ONE_DO (q)
SWAP INDEX@ PULLREALEL
ROT INDEX@ PULLREALEL
ROT %* 4UNROLL
LOOP (q)
2DROP
UNCOERCE ONE{}N x>ARRY
m #1+_ONE_DO (i)
INDEX@ #2 #/ #+ #1+_ONE_DO (j)
JINDEX@ INDEX@ 2GETEVAL
PULLREALEL
%CHS
JINDEX@ TOTEMPOB !ii
1 JINDEX@ #1- #MAX
JINDEX@ #1+ m #MIN
#1+ SWAP DO (a)
1 JINDEX@ INDEX@ ii #> ?SKIP #1- MAX
JINDEX@ ii INDEX@ #> ?SKIP #1+ INDEX@ MIN
#1+SWAP DO (b)
SWAP JINDEX@ INDEX@ 2GETEVAL PULLREALEL
ROT %+
LOOP (b)
LOOP (a)
ROT
JINDEX@ INDEX@ 2GETEVAL
3PICKSWAP PUTREALEL
JINDEX@ #1+ INDEX@ #-
2GETEVAL
ROTSWAP
PUTREALEL
SWAP
LOOP (j)
LOOP (i)
DROP
m DUP r #>=_ ?SKIP #1+ !m
LOOP (k)
SWAP %0 xCON
r 1 2GETEVAL
UNCOERCE
xDO %1 xPUTI xUNTIL
% -64 xFS?
xENDDO
xDROP
xDOT
%6
s UNCOERCE
x^
x/
ABND
;
;
@
"
I hope I got it without typing errors.
The small code object "Tind" reduces calculation time with 29%, from about 450sec to 321.
I lost the userRPL version, but it was many times slower.
br Gjermund

Werner · 10-21-2022, 05:27 AM

(10-16-2022 05:29 PM)Albert Chan Wrote: (*) I don't really need a copy, swapping name of array (P,Q) is enough.
Too bad ... VARSWAP don't work for arrays.

>VARSWAP P, Q
ERR:Data Type

As far as I know (which is not a lot, admittedly), VARSWAP swaps the *values* of the variables, not their names.
Cheers, Werner

Albert Chan · 10-21-2022, 04:10 PM

(10-12-2022 12:10 PM)PeterP Wrote: My code does deliver the correct result for R = 5, but I dont have a good way (especially right now on a plane and my work computer has no simulators installed…) to check if it is correct for R = 30, S=29. (It comes out to 1.311095094 e-13).

For S = R-1, we can treat triangle as without bottom edge (and the 2 corners).

First step from top corner, it gives equal probability to left or right side.
We can thus skip first iteration, simplified the problem without top corner.

Problem now is relatively simple, with only inside (6 ways) and edge (4 ways)
Only edge probability can "leak" to the inside; inside probabilities never "gets out".

Work out the geometric progression (not shown), with p=1/6, q=1/4, we have:

P(R, S=R-1) = ((2p)^(R-3) - q^(R-3)) / (2*p-q) * (2*p*q) + 2*q^(R-2)

(2*p*q) / (2*p-q) = 1 / (1/q-1/(2*p)) = 1 / (4-3) = 1. It simplified to:

P(R, S=R-1) = 3^(3-R) - 2^(5-2*R)

Example:

P(1,0) = 9 - 8 = 1
P(2,1) = 3 - 2 = 1
P(3,2) = 1 - 1/2 = 1/2
P(4,3) = 1/3 - 1/8 = 5/24
P(5,4) = 1/9 - 1/32 = 23/288
P(6,5) = 1/27 - 1/128 = 101/3456
...
P(30,29) = 1/3^27 - 1/2^55 ≈ 1.31109509664e-13

pier4r · 10-21-2022, 05:38 PM

(10-19-2022 09:56 PM)Albert Chan Wrote: This despite my Toshiba laptop is supposed to be 10x faster than my 22 years old Dell ... go figures.

semi-OT.

Because emulating a system may be done in a not too efficient way and a lot is lost on the way. For example Saturn code is emulated in the 50g, but if you take the emulation away and you write code with tools that are more optimized for the machine (newRPL for example), the speed difference is impressive.

So yes one could execute things on very powerful systems that are simply wasting a lot due to inefficiencies.

Good to know that the Dos emulator is not that great. Would be interesting if you try compatibility options offered by windows itself or virtual machines via microsoft virtual PC.

Anyway as valentin said, in the big picture execution time is only partially meanigful.