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

[Albert Chan]

(10-13-2022 09:44 PM)C.Ret Wrote:  IF A<>I OR J<>B THEN P(I,J) = P(I,J) + Q(A,B)/W(A,B)

1. Most vertices can go 6 ways, same Q(A,B)/W(A,B) calculated upto 6 times.

It is more efficient to calculate weighted Q first.
Bonus: MAT Q=P line is not needed anymore.

2. we can remove IF THEN statement, NOT(A<>I OR J<>B) ≡ (A==I AND B==J)

3. it is faster to use regular variable, sum it, then assign to P(I,J)

Combined 1,2,3: quoted line is simply T = T+Q(A,B), with T initially set to -Q(I,J)

4. it may be more accurate to go for scaled probability (by 6^S), then unscale it.

With above optimizations, we have:

10 DESTROY ALL @ OPTION BASE 1 @ INPUT "[VA]SRC012A R,S= ";R,S @ T0=TIME
20 REAL T,W(R,R),P(R,R),Q(R,R) @ INTEGER A,B,I,J,K,M
30 FOR I=1 TO R @ FOR J=1 TO I @ W(I,J)=3/(3-(J=1)-(I=J)-(I=R)) @ NEXT J @ NEXT I
40 MAT P=ZER @ P(1,1)=1 @ M=2
50 FOR K=1 TO S
60 FOR I=1 TO M @ FOR J=1 TO I @ Q(I,J)=P(I,J)*W(I,J) @ NEXT J @ NEXT I
80 FOR I=1 TO M
90 FOR J=1 TO CEIL(I/2) @ T=-Q(I,J)
100 FOR A=MAX(1,I-1) TO MIN(I+1,M)
110 FOR B=MAX(1,J-(A<=I)) TO MIN(J+(I<=A),A)
120 T=T+Q(A,B)
130 NEXT B
140 NEXT A
150 P(I,J)=T @ P(I,1+I-J)=T
160 NEXT J
170 NEXT I
180 IF M<R THEN M=M+1
190 DISP K;TIME-T0
200 NEXT K
210 T=0 @ FOR J=1 TO R @ T=T+P(R,J) @ NEXT J
220 DISP TIME-T0;R;S;T/6^S


>RUN
[VA]SRC012A R,S= 5,4
1      .04
2      .08
3      .19
4      .36
.4            5 4         7.98611111111E-2
>T, 6^S                 ! P = 23/288      
103.5      1296

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

Compare to original version, speed up = 245/173.47 - 1 ≈ 41%