🚀 go-pugleaf

A few days ago, someone asked what kind of RNG typical spreadsheets use.  I 
was curious, so I worked it out for Quattro Pro SE 1.0.  (This is a 
repackaging of Quattro Pro 1.0 for the "home or small business".  The 
regular QPro is up to version 4.0 now.)

It's a pretty reasonable guess that a linear congruential generator would be 
used, so I started on that assumption.  I multiplied 20 UNIF(0,1) values 
from @RAND by 2^32, and saw that the results all ended in .5; that seemed 
like pretty good evidence that the floating point @RAND was based on adding 
0.5 to an unsigned 32 bit integer, and dividing by 2^32.

Assuming that Borland wouldn't really mess up the distribution, that was 
also pretty good evidence that the random integer covered the full range of 
values, i.e. if linear congruential, it was modulo 2^32.

Assuming a sequence X_n of the form

  X_{n+1} = A X_n + B mod M

and defining differences D_n = X_n - X_{n-1} mod M, it's not hard to see
that 

  A = D_n * Inverse(D_{n-1}) mod M

and
  
  B = X_n - A * X_{n-1} mod M

where Inverse() is the multiplicative inverse in mod M arithmetic.  

Doing these calculations within a spreadsheet isn't easy; I can't think of
any simple formula for that Inverse() function.  I took a list of 20 
realizations out of the spreadsheet and did the calculations in a little 
Turbo Pascal program.  With M=2^32, all odd numbers have an inverse, and no 
even ones do.   All differences but the first I calculated were odd, so
I went ahead.  It turned out that the updating formula used in all the 
other cases was indeed linear congruential, with M = 2^32, A = 1103515245 
and B = 12345.  

I suspect the reason the first case was different was that it was the 
prototype formula; all of the other realizations were created in a block 
copy of that formula. 

I also applied these methods to the internal random number generator in 
Turbo Pascal; it too is linear congruential, with M = 2^32, A =  134775813 
and B = 1.  

Duncan Murdoch
dmurdoch@mast.queensu.ca