PowerAda 65

From OC Systems Wiki!
Jump to: navigation, search

(65) The algorithms for random number generation.

See A.5.2(32).

The implementation was taken from LSN-1055 which is a Language Study Note done by Ken Dritz on the "Evolution of the Random Number Generator" dated 94/01/31:

"This implementation uses the venerable multiplicative linear congruential generator with a multiplier of 16_807 (7**5), no additive constant, and a modulus of 2_147_483_647 (2**31-1). This generator has a period of 2**31-2. It can NOT generate the value 0.0, but it CAN generate the value 1.0 if 2_147_483_646.0 / 2_147_483_647.0 rounds up to 1.0 when the result is coerced to Float. It is customary to perform integer arithmetic in this algorithm, using 32-bit integers, and convert to floating point just before the end. In the customary implementation, the state is an integer between 1 and 2**31-2. A new state is obtained from the current state by integer arithmetic operations (that in general require multiple precision arithmetic). The result is obtained by converting the new state to floating point and dividing by a constant (e.g., one less than the modulus) to normalize the range so that its maximum value is 1.0 (or by the modulus itself, or an even larger value, to give a maximum of less than 1.0). This implementation does not use integer arithmetic and does not represent the state as a 32-bit integer. Instead, the state is a floating point number with a precision of at least 31 bits, so that the integers from 1.0 to 2_147_483_646.0 can all be represented exactly. The arithmetic that is performed to obtain the new state creates a product that is the floating point representation of an integer value requiring at most 46 bits of precision. Thus, customary 64-bit double precision hardware suffices. Resetting the state from an initiator has to allow all Integer values and has to map the initiator value into a state value in the range 1 .. 2**31-2. This is accomplished with an integer mod and an addition. I have chosen to generate and throw away five random numbers after setting the state so that the first random number called for by the user after setting the state with an initiator will not appear highly correlated with the initiator value. Resetting the state without an initiator computes a state using the current value of the system clock. The values obtained by Splitting the value returned by Clock are used in an appropriate mixed-radix computation to yield a state value between 26_000_700 and 1_873_119_999. This version of Reset yields different states for two calls spaced at least a second and not more than fifty years apart."