Génération de pseudo-nombre

Question

Voici le texte de la structure de données et l'analyse d'algorithme par Mark Allen Wessis.

Après x (i + 1) devrait être lu comme x indice de i + 1, et x (i) devrait être lu comme x indice i.

x (i + 1) = (a * x (i)) mod m.

Il est également courant pour renvoyer un nombre réel aléatoire dans l'intervalle ouvert (0, 1) (0 et 1 ne sont pas des valeurs possibles); cela peut être fait par en divisant par m. A partir de cela, un nombre aléatoire dans un intervalle fermé [a, b] peut être calculé en normalisant.

Le problème avec cette routine est que la multiplication peut débordement; Bien que ce ne soit pas une erreur, il affecte le résultat et donc le pseudo-aléatoire. Schrage a donné une procédure dans laquelle tous les calculs peuvent être effectués sur une machine 32 bits sans débordement. Nous calculer le quotient et reste de m/a et définissons ceux-ci comme q et r, respectivement.

Dans notre cas M = 2147483647 A = 48271, q = 127773, r = 2,836 et r < q.

Nous avons

x(i + 1) = (a*x(i))mod m.---------------------------> Eq 1. 
      = ax(i) - m (floorof(ax(i)/m)).------------> Eq 2 

Aussi l'auteur est mentionnions sur:

x(i) = q(floor of(x(i)/q)) + (x(i) mod Q).--->Eq 3 

Ma question

1. qu'est-ce que l'auteur entend par nombre aléatoire est calculé en normalisant?

2. Comment l'auteur est-il venu avec Eq 2 de Eq 1?

3. Comment l'auteur est-il venu avec Eq 3?

Answer 1

1. Si vous avez un nombre aléatoire dans l'intervalle [0,1], vous pouvez obtenir un numéro dans l'intervalle [2,5] (par exemple) en multipliant par 3 et en ajoutant 2.

Answer 2

1. Normaliser signifie que si vous avez X ∈ [0,1] et vous devez obtenir Y ∈ [a, b] vous pouvez calculer

   Y = a + X * (b - a)

EDIT: 2. Supposons que

a = 3, x = 5, m = 9 

Ensuite, nous avons

où [ax/m] signifie une partie entière. Nous avons donc 15 = [ax/m]*m + 6
Nous avons besoin de 6. 15 - [ax/m]*m = 6 =>ax - [ax/m]*m = 6 =>x(i+1) = ax(i) - [ax(i)/m]*m