Re: 35s SEED  Long (but I hope interesting, with a little theory) Message #9 Posted by Andrés C. Rodríguez on 11 Aug 2007, 8:03 p.m., in response to message #8 by Karl Schneider
Pseudorandom number generators were a "hot topic" some decades ago. The ability to use a randomized variable was a desirable feature to be used in software, from games to simulators to statistics methods (such as MonteCarlo). However, for such random features, there were some concerns: how to implement them, and how "good" they are at, well, randomness.
At that time, hardware resources were scarce and expensive, and sophisticated functions may be prohibitive in terms of execution time. One of the preferred models was the congruential generator, which takes a seed (a number between 0 and 1) and generates the next number in a pseudorandom sequence, by means of a multiplication, an addition and a fractionalpart operation.
If the randomsequence numbers are called s(1), s(2)...s(i), the generator works as:
s(i+1) = FRAC {s(i) * A + B}
In the HP25 and HP41 application programs manuals, there were programs with examples for such generators, because those calculators lack an internal random function.
A classic RPN program looked like
LBL "RANDOM"
RCL 0 ; recall the seed or the last number in the sequence
9821
x ; multiply by A
.211327
+ ; add B
FRAC ; take fractional part...
STO 0 ; ...keep it as the next number in the sequence...
RTN ; and return it in X to the user convenience.
So a program to simulate a dice was as simple as
LBL "DICE"
XEQ "RANDOM"
6
x ; multiply by six to obtain a number from 0 to 5.999
1
+ ; add one to offset it to the 1 to 6.999 range
INT ; finally, just keep the 1 to 6 integer value
RTN
And a MonteCarlo example which slowly converges to Pi looked like
LBL "PI MC" ; Pi by MonteCarlo
0
STO 1 ; Initialize iterations counter
STO 2 ; Initialize hits counter
LBL "LOOP"
XEQ "RANDOM" ; Obtain two random numbers between 0 and 1
XEQ "RANDOM" ; and use them as the components of a vector,
R > P ; obtain the vector module
1
STO + 1 ; Increment the iterations counter...
x > y? ; and, if the vector module is less than one,
STO + 2 ; ...increment the hits counter too.
RCL 2
RCL 1 ; Obtain the hits to iterations ratio...
/ ; ...which should converge to Pi / 4,
4 ; as you may notice, thinking about the raindrops
x ; falling on a square tile of unit side.
VIEW X ; Show the current approximation and
GTO LOOP ; ...keep looping!!
Note that these programs intend to be clear to understand, and are not optimized for speed.
The random number generation was one important part of Donald Knuth's "The Art of Computer Programming, Vol II: Seminumerical Algorithms". There, Knuth shows how a frequent mistake was to "choose a random method to create random numbers". He dramatically illustrates the point, presenting a program that does a lot of complex permutations and operations on a number ot obtain the next in a pseudorandom sequence... only to show that the program soon falls in a very short sequence which repeats itself forever. Hardly random, indeed.
Then he goes a long way presenting methods to assess the "goodness" of a random number generator routine; the most powerful (and very hard to understand) was the Spectral Test, which HP claims to pass with the abovementioned routine included in the HP41 Standard Pac.
Later calculator models incorporated builtin pseudorandom functions, which also depend on an initial value, called the seed. However, for the same seed, we get the same sequence; this may be good for debugging and testing purposes, but not desirable in true operation. The same happened in the BASIC computers of those years, and hence a RANDOMIZE statement appeared, which initializes the seed with a soconsidered random value, unknown to the user, and so attaining an acceptable random behaviour. In HP calculators, a value of 0 for the seed causes a similar initialization. The "randomized" seed is usually taken from some timer or counter insude the processor, which value changes very rapidly all the time, and which is not correlated to the program operation.
For real randomness, some diecast engineers resort to auxilliary circuits that sampled the thermal noise of a diode junction or similar devices. Thermal noise circuits are as close as "random" as we may meet in a whole life.
