[VA] SRC #012a - Then and Now: Probability

[Albert Chan]

(10-16-2022 10:25 AM)Vincent Weber Wrote:  Memory requirements are huge. The needed registers seem in the range of 2.5*R^2 at bare minimum. For R=30 you need something like 18Kb if each register takes 8 bytes, plus extra variables, plus program stack... So you need something like 20Kb RAM. This rules out the 41, the 42, the SHARP pc-1261... You need a 32K machine basically!

I was thinking of minimum memory requirement, without code of checking corners, edges.
Also, code that would work with non-symmetrical starting conditions. (no symmetry trick)

In other words, this would still hold, collecting probabilities from hexagon vertices.
Q = weighted probability of previous P

P(I,J) = Q(I-1,J-1) + Q(I-1,J) + Q(I,J-1) + Q(I,J+1) + Q(I+1,J) + Q(I+1,J+1)

Current implementations treated (P, Q) as square matrix, with lots of 0's on the right.
But, if we flatten it, say into (p,q) of 1 dimension, all we need is 1 zero between rows.

Q(I,J) ≡ q(I*(I+1)/2 + J)

Q(1,1) = q(2)
Q(2,1), Q(2,2) = q(4), q(5)
Q(3,1), Q(3,2), Q(3,3) = q(7), q(8), q(9)
Q(4,1), Q(4,2), Q(4,3), Q(4,4) = q(11), q(12), q(13), q(14)
...

Note that q of triangular numbers are outside the triangle, with probability of 0.

Example, to get next iteration of P(3,2) = p(3*4/2+2 = 8)

p(8) = q(4) + q(5) + q(7) + q(9) + q(12) + q(13)

In general, for P(I,J) = p(x = I*(I+1)/2 + J)

p(x) = q(x-I-1) + q(x-I) + q(x-1) + q(x+1) + q(x+I+1) + q(x+I+2)

---

Q(0,0) .. Q(R+1,R+1) ≡ q(0) .. q((R+1)*(R+4)/2)

Total q elements = (R+1)*(R+4)/2 + 1= (R+2)*(R+3)/2

Technically p does not need as many spaces.
But for convenience, we like to keep both arrays with same dimensions.

Total array elements needed = (R+2)*(R+3) = floor((R+2.5)^2)

With theory out of the way, here is the flattened array version.

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

On line 90, I use the quirk the last X is outside loop limits. Q(X) == Q(T+R)
Same idea on line 120, "T=X" same as "T=T+I+1", next triangular number

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

>RUN
[VA]SRC012A R,S= 5,4
...
.31         5 4         7.98611111111E-2

>MAT P = (6^(-S)) * P ! scaled to have sum(P) = 1.0
>MAT DISP P ! note the single zero gap, between "row"
0
0
.114583333333
0
.127604166667
.127604166667
0
9.80902777778E-2
.175347222222
9.80902777778E-2
0
0
3.03819444445E-2
5.90277777778E-2
5.90277777778E-2
3.03819444445E-2
0
.0078125
1.99652777778E-2
2.43055555556E-2
1.99652777778E-2
.0078125
0
0
0
0
0
0
0