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

[Albert Chan]

(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.