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

[C.Ret]

(10-16-2022 10:25 AM)Vincent Weber Wrote:  Except that... 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.

For the HP-41, I am currently thinking about a version where the among of registers would depend only on the number of steps.

It is based on the idea given by Jean-François and illustrated by Chan for the case (R,S)=(5,4).
However, exploring all the paths of S STEPS is likely to take an infinite amount of time...
Especially where S is greater than R !
On the other hand, this solution requires only S=60 well-used registers (sign, integer part and fractional cleverly exploited) and a few others for counters, coordinates, multiplicative factor and final probability...

So far, my buggy prototypes have only worked on reduced grids and for ridiculously small path’s lengths. I am not very confident in the practical feasibility.
The real & practical solution would be to find a more direct and efficient calculation than listing all the paths in depth.

(10-16-2022 08:32 AM)J-F Garnier Wrote:  In Series 70 BASIC, there is no speed gain to use INTEGER variables; on the contrary it adds some overhead to convert INTEGER to REAL before evaluating the expression and convert the result back to INTEGER. This also applies to FOR .. NEXT loops and matrix indexes.

This was one of the questions I asked myself while writing my code. I didn't take the time to measure the gain or loss of time with all REAL variables.
I imagine that variables of the SHORT type do not offer any gain in speed either.

Thanks to Jean-François who answers and confirms my doubts without me having to time anything.

(10-15-2022 06:28 PM)Albert Chan Wrote:  Compare to original version, speed up = 245/173.47 - 1 ≈ 41%

Thanks to Chan who optimize my code. The time savings are far from trivial or insignificant. I like the new versions

By reading his post, I had already modified the code in my HP-71B in order to make the rounding errors disappear. But I hadn't thought of merging weight and probability in the matrix Q(,) = W(,) .* P(,). Too bad that the MATH module has no instruction making the dot-product. Is there a pretext for a third version of the MATH module?

I love the last version that smashes! thank you Chan!


This made me want to transcribe this algorithm for my HP-28S.

I get for the problem (R,S)=(30,60) exactly P =9.51234350207E-6 after a very long time of 3 hours 12 min 48sec. It must be said that this version has the two internal loops FOR a and FOR b.

Now that Chan gave the idea, I will remake my RPN code to avoid the hunting for neighbors. The next version will therefore use matrices of dimension (R+1)x(R+1), the HP-28S having enough memory (32 kb).

I transcribed this version below. Will it inspired someone or will anyone, as CHAN already does, found some elegant and effective way to improve it?

The equilateral triangle of probabilities P is stored in the form of a one-dimension vector of length \( d = \frac{r^²+r}{2} \). It is not memorized in a register but remains throughout the calculation in the stack.
Similarly, the weight coefficients, which are calculated once at the start of the computation, stay in the stack in the form of a vector of identical length.
On the other hand, the size of the vector Q is reduced (at least at the beginning) and depends on the progress variable m in order to save some effort.

When designing, I intended to calculate vector Q using the DPrdct instruction. But I realized that this instruction is not a native instruction of the HP-28S but is part of the personal programs that I usually use on this machine. So, I had to add the code of this program within the code. I took the opportunity to limit the size of Q and therefore reduce the calculations somewhat. But not the execution time, the HP-28S not being particularly quick to execute my codes.

Similarly, a Tind instruction is used to calculate the index of the triangular position (I,J) with J<=I. This is an instruction that I use elsewhere. It's very short, but I leave it in the code below which makes it 'a much more easy to read'.
As it's RPL, you have to understand 'a little less unreadable'.

SRC12a:
« OVER DUP Tind 2 → r s d m
   « 1 r FOR i
          1 i FOR j
               3 DUP j 1 == - i j == - i r == - /
          NEXT
     NEXT
     { d } →ARRY                                                   %% That's W
     DUP 0 CON 1 1 PUT                                             %% That's P = MAT ZER & P(1,1)=1
     1 s FOR k
          k 1 DISP
          DUP2 m m Tind → W P n                                    %% Embedded version of personal Dot.Product code
             « 1 n FOR q                                           %% size limited to m row since next rows all zero
                    W q GET P q GET *
               NEXT
               { n } →ARRY »                                       %% That's Q = W .* P
          1 m FOR i
               1 i 2 / CEIL FOR j
                    DUP i j Tind GET NEG                           %% Init t =- Q(i,j)
                    1 i 1 - MAX 1 i + m MIN FOR a
                         1 j a i <= - MAX j i a <= + a MIN FOR b
                              OVER a b Tind GET +                  %% Add  t += Q(a,b)
                         NEXT
                    NEXT
                    ROT                                            %% stack W t Q P order
                    i j         Tind 3 PICK PUT
                    i 1 i + j - Tind    ROT PUT
                    SWAP                                           %% back initial stack order
               NEXT
          NEXT
          DROP                                                     %% Drop Q 
          m DUP r < + 'm' STO                                      %% Increase m ( STO+ doesn't work with local variables )
     NEXT
     SWAP 0 CON
     r 1 Tind                                                      %% W = 0 except for last row where W = 1  
     DO
          1 PUTI
     UNTIL 46 FS? END                                              %% Flag 46 set when PUTI reach end of vector 
     DOT 6 s ^ / 
     CLMF 1430 .4 BEEP »                                           %% Restore stack display and bip    
»

 
Tind:                                                              %% Personal Triangular Indice
« OVER SQ ROT - 2 / + »                                            %%   Tind(i,j) = j+(i²-i)/2



Feel free to comment or ask any questions that you deem useful.

Best regards.
C.Ret