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

[Fernando del Rey]

I must admit it’s pure chance that my method seems to be more accurate than J-F’s. I started by summing the corners first and borders next as it seemed easier to program, but I was not considering that those cells would have smaller values and thus give a more accurate result when adding values as commented by Werner.

In my first code I had introduced a silly error in one of the corner cells (I forgot to divide it by 2 in the propagation). I was checking that the addition of all values in the probability matrix B was close to 1, and I noticed that it was a bit higher than 1, but initially I thought the difference was coming from the accumulation of rounding errors.

Later, I discovered the error in the code, and after correcting it I got a value of 1 accurate to 2 ULP, which gave me confidence that the code was now correct.
I have some ideas to improve the program for speed and memory usage. For speed, you can consider that if you are in iteration M all cells below row M+1 will be zero, and you can save the divisions and additions of zeros.

For memory usage, as the matrices A and B are not used to the right of their diagonal, you could work with a single matrix of size Nx(N+1) using the left side of the diagonal for holding results of iteration M and the right side of the diagonal to calculate results of iteration M+1. But I’m afraid it would make the code much less readable.

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.

In the end, getting the result of the 30/60 case in less than two hours on a plain 71B (with no Math ROM), might still have been considered acceptable at the times of the 71B.

But I am convinced that Valentin will show us a much cleverer and faster method to arrive at the correct solution