| Proc code - Solutions - RANDOM GENERATOR |
|
| $language |  |
 |
 |
A
Pseudo-Random Number Generator
The
below given random service returns a pseudo-random integer in the
range 0 to 999999999 inclusive. It works by creating a list ($RLIST$)
of ninety-seven integers from an initial key (or "seed") and
then partitioning the range into two subranges. The first fifty-five entries
are integers to be used in pairs to generate a random result. The next
forty-two entries are random results already generated but "on hold" until
selected in order to disturb any pattern in output caused by a poor key
and to shuffle the order of random integers on output. $P1$
and
$P2$
are the pointers for each range. The values referenced by these internal
pointers are subtracted and then adjusted to be greater than zero if needed
to form a result.
This table-subtraction method produces a good degree of randomness alone, but another technique is also used to augment its operation. The result stored in $P3$ is used to select one of the 42 entries in locations 56 to 97 in the list for replacement. The number which is being replaced at this location is both promoted up to $P3$ and tagged to be returned from the function as it's return value. The number generated by subtraction in the 1 to 55 range replaces this newly promoted number at its old position where it will wait as a possible random return value until a subtraction selects it. This additional "shuffling" serves to negate any subtle patterns that the sequence of values generated with rotating table subtractions might produce.
The InitRandom operation takes a seed key in the form of an arbitrary length ASCII string. This key is used to seed the random list used, later, by the Get operation to produce random numbers. You will notice that the algorithm adds some other values to the seed; this is to prevent poor key initialization.
Analysis
At the heart of this algorithm are two techniques described by Donald Knuth . The algorithm used in this service if fairly fast, operating in constant time while the call to InitRandom will operate in linear time.
The component.
In the random.trx file you will get :
Generació
de números pseude aleatorisAquest mètode produeix un bon grau d'aleatorietat, però es fa servir també una altra tècnica per augmentar aquesta operació. El resultat guardat a $P3$ s'usa per seleccionar una de les 42 entrades situades entre les posicions 56 i 97. El número resultant és substituit llavors en $P3$ i seleccioant per retornar-lo com a resultat.
L'operació InitRandom rep per paràmetres una clau (llavor) que serà una cadena de longitud arbitrària. Aquesta clau s'utilitza per genera la llista pseude aleatòria. Podeu comprovar que a aquesta clau se l'afegeixen alguns valors per prevenir possibles claus pobres.
Anàlisi.
Aquest algorisme està basat en dues tècniques descrites per Donald Knuth. Malgrat que l'algorisme és prou ràpid, el més interessant es que el seu comportament (complexitat algorísmica) és constant.
El component.
Al fitxer random.trx trobareu:
Generación
de números pseudo aleatorios.Este método produce un buen grado de aleatoriedad, pero se emplea otra técnica para aumentar esta operación. El resultado guardado en $P3$ se usa para seleccionar otra de las 42 entradas situadas entre las posiciones 56 y 97. El número resultante es sustituido entonces en $P3$ y seleccionado para devolverlo como resultado.
La operación InitRandom recibe por parámetros una clave (semilla) que será una cadena de longitud arbitraria. Esta clave se utiliza para generar un lista pseudo aleatoria que posteriormente se utilizará en la operación Get para generar el número aleatorio. Podréis comprobar que a esta clave se le añaden algunos valores para prevenir posibles claves pobres.
Análisis.
Este algoritmo está basado en dos técnicas descritas por Donald Knuth. Aunque es algoritmo es bastante rápido la parte más interesante es que su comportamiento (complejidad algorítmica) es constante.
El componente.
En el fichero ramdon.trx encontrareis :