Discussion :

[macErmite]

Bonjour,

Je cherche a obtenir un nombre aleatoire equiprobable, entre -10 et +10 (des entiers au pas de 0.5 : -10;-9.5;-9;...;+9;+9.5;+10) SANS utiliser la fonction random .

Je suis perdu sur la determination des coef de cette formule : Un+1 = ( a * Un + b ) % c


Avez-vous des idées ?

[DonQuiche]

Bonjour.

Il existe de très nombreux algorithmes pour ça. Le standard est le Mersenne Twister. Tu peux aussi utiliser "Xorshift1024*" (attention à l'étoile et au 1024).

Note que ces générateurs ne doivent pas être utilisés pour de la cryptographie. Dans ces cas-là il faut d'autres algorithmes, plus lents.


Si toutefois tu insistes pour utiliser ta formule (qui donnera un générateur pseudo-aléatoire médiocre), alors...
* C doit valoir 10 pour produire des résultats variables entre -10 et +10. -10 devrait également fonctionner, à vérifier.
* A doit être négatif. Sinon tous les nombres générés (après un certain temps) seraient positifs ou négatifs selon le signe de B.
* A doit être non-nul. Sinon on générerait toujours le même nombre.
* Hormis cela, A et B peuvent être quelconques. Mais il doit y avoir d'autres critères de qualité pour accroître la période.

[Flodelarab]

Bonjour

Qu'as-tu contre la fonction random ?

Il faut tirer 1 valeur parmi 41. Donc déjà, il est probable que le modulo "c" soit 41, avec la bijection suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
0 -> -10
1 -> -9.5
2 -> -9
3 -> -8.5
4 -> -8
5 -> -7.5
6 -> -7
7 -> -6.5
8 -> -6
9 -> -5.5
10 -> -5
11 -> -4.5
12 -> -4
13 -> -3.5
14 -> -3
15 -> -2.5
16 -> -2
17 -> -1.5
18 -> -1
19 -> -0.5
20 -> 0
21 -> 0.5
22 -> 1
23 -> 1.5
24 -> 2
25 -> 2.5
26 -> 3
27 -> 3.5
28 -> 4
29 -> 4.5
30 -> 5
31 -> 5.5
32 -> 6
33 -> 6.5
34 -> 7
35 -> 7.5
36 -> 8
37 -> 8.5
38 -> 9
39 -> 9.5
40 -> 10

Il ne reste plus qu'à trouver a et b générateur.

Vue la base 41, il y a des chances que b=0.

[macErmite]

que proposes-tu pour a ?

[Flodelarab]

Au temps pour moi, ça ne marche pas. J'explique mon erreur.

Le modulo 41 apporte forcément 41 valeurs réparties entre 0 et 40.
Or, avec un groupe cyclique basé sur un nombre premier (41), il a forcément un générateur.
Et effectivement, il y a 6, 7, 11, 12, 13, 15, 17, 19, 22, 24, 26, 28, 29, 30, 34, 35 comme générateurs.

Mais là où ça ne marche pas c'est que le 0 est exclu de la génération.
Donc elle fournit 40 valeurs et non 41.

On pourrait dire "Prenons 42 comme base".
Mais 42 n'est pas premier.
Et ce n'est pas facile de trouver un générateur.

Le but de ta formule est

• de couvrir toutes les valeurs de 0 à 40.
• de ne pas voir la logique.

C'est le deuxième point qui fait travailler.
Car on pourrait prendre Un+1 = ( 1 * Un + 1 ) % 41 et ça marcherait.
Mais là, la logique est trop apparente.

Tu peux par exemple prendre 17 pour b et 1 pour a:
Un+1 = ( 1 * Un + 17 ) % 41
1 18 35 11 28 4 21 38 14 31 7 24 0 17 34 10 27 3 20 37 13 30 6 23 40 16 33 9 26 2 19 36 12 29 5 22 39 15 32 8 25

[macErmite]

Merci à tous pour vos participations.

[Flodelarab]

Euh ... qu'est-ce que ça veut dire ? "oui" ? "non" ? "m***e" ?
Vas-tu utiliser la dernière séquence ?

[macErmite]

" Merci à tous pour vos participations " cela veux dire que sans votre aide je serai encore sur ce problème. Cela fonctionne très bien grâce à vos messages.

[tbc92]

Et pour qu'on apprenne un peu, tu peux partager ce que tu as fait. Parce que je n'ai rien vu ici qui permettrait de générer une fonction random.

[wiwaxia]

Bonjour,

Les réponses apportées sont quelque peu déroutantes, et je ne dois pas être le seul dans l'embarras ...

Et pour qu'on apprenne un peu, tu peux partager ce que tu as fait. Parce que je n'ai rien vu ici qui permettrait de générer une fonction random.

D'abord les liens cités:

... Il existe de très nombreux algorithmes pour ça. Le standard est le Mersenne Twister. Tu peux aussi utiliser "Xorshift1024*"

L'intérêt de ces articles est incontestable, mais faut-il d'emblée propulser le demandeur à des altitudes stratosphériques, en lui proposant des textes qui ne sont compréhensibles, en première lecture, qu'à des spécialistes de haut niveau (dont je ne fais pas partie) ?
Il semble que l'auteur de la question cherche seulement à s'initier à l'utilisation du générateur congruentiel linéaire ...

... Je cherche à obtenir un nombre aléatoire équiprobable, entre -10 et +10 (des entiers au pas de 0.5 : -10;-9.5;-9;...;+9;+9.5;+10) SANS utiliser la fonction random .
Je suis perdu sur la détermination des coef de cette formule : Un+1 = ( a * Un + b ) % c
Avez-vous des idées ?

... et (sans que les liens précités soient exclus !) la documentation suivante lui serait probablement plus utile :

# Produire des Nombres au Hasard
http://www.alrj.org/docs/algo/random.php

# Générateur de nombres pseudo-aléatoires
https://fr.wikipedia.org/wiki/G%C3%A...l%C3%A9atoires

# Nombres pseudo-aléatoires
http://math.univ-lyon1.fr/~jberard/genunif-www.pdf

# Méthodes de Monte Carlo
http://www.ressources-actuarielles.net/EXT/ISFA/fp-isfa.nsf/2b0481298458b3d1c1256f8a0024c478/767ceb7e2d32524ec125710b0047fcef/$FILE/poly-ensai-mc.pdf

Quant aux calculs ... du passé faisons allègrement table rase Tant pis pour les engueulades.

1°) La liste des 41 valeurs entières et semi-entières consécutives allant de -10 à +10 s'exprime en fonction des 41 premiers entiers positifs par la relation affine: g = (m - 21)/2 . On passe ainsi à une variable aléatoire entière du domaine [1 ... 41] .

2°) L'entier premier immédiatement supérieur est N = 43, lequel admet 12 racines primitives (a):
{ 3 , 5 , 12 , 18 , 19 , 20 , 26 , 28 , 29 , 30 , 33 , 34 }
à chacune desquelles correspond une suite géométrique modulaire de la forme: v_k+1 = a * v_k mod (N) , de période N - 1 = 42 , et dont toutes les valeurs successives se situent dans [1 ... 42].
Il suffira donc de partir de la graine v₀ = 42 pour obtenir ensuite toutes les valeurs utiles appartenant au domaine [1 ... 41] .
Le zéro, solution stationnaire ici exclue de la liste, doit sa particularité au choix simplificateur de la seconde constante de l'énoncé (b = 0), qui ne dénature en rien le problème. Envisager par la suite (b>0) conduit en première approximation à une permutation des termes de la suite.

3°) L'aspect aléatoire de la suite obtenue exige une dispersion convenable dans le plan des points de coordonnées (x_k = v_k , y_k = v_k+1 ) ; or ces points appartiennent à un réseau ponctuel plan dont la maille est construite sur deux vecteurs indépendants (U₁, U₂), dont les normes (U₁, U₂) représentent les plus courtes distances séparant les points du réseau, et qui vérifient par convention:
(a) 0 < U₁ < U₂ (b) U_1x > 0 ; U_2y > 0 (c) Det(U₁, U₂) > 0 .
La recherche des plus courts vecteurs conduit systématiquement au résultat: Det(U₁, U₂) = N = 43 , car il s'agit de l'aire algébrique du parallélogramme (U₁, U₂) associé à chacun des (N) points - (0, 0) compris - répartis dans le carré d'arête (N) et d'aire (N²).
Une calculette donne les résultats suivants:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
 
	 a    U1x    U1y    U2x    U2y    Det   U1^2   U2^2
 
         3     1      3     -13     4     43     10     185
	 5     1      5      -8     3     43     26      73
        12     4      5      -7     2     43     41      53
	18     5      4      -2     7     43     41      53
	19     2     -5       7     4     43     29      65
	20     2     -3       9     8     43     13     145
	26     5      1      -3     8     43     26      73
	28     3     -2       8     9     43     13     145
	29     3      1      -4    13     43     10     185
	30     3      4      -7     5     43     25      74
	33     4      3      -5     7     43     25      74
	34     5     -2       4     7     43     29      65

Les meilleures suites (du point de vue de l'éloignement mutuel des points) sont celles qui correspondent aux normes maximales du plus court vecteur, soit ainsi a = 12 ou 18 (U₁² = 41).

En utilisant un nombre premier plus élevé (par ex. 100003, 100019 ...) et en ne retenant que les valeurs contenues dans un domaine arbitraire [h, h+40], les ennuis d'alignement s'estompent sans doute, mais je n'ai pas eu le temps de tester cela.
Un ennui: l'inventaire des racines primitives, et plus encore celui des vecteurs de base devient très long (temps de calcul proportionnel à N²), et la machine doit ramer pendant une heure pour N ~ 10^5 .

Cordialement, W.