Fonction aléatoire sans la fonction RND

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 ?

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.

Bonjour :coucou:

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:

---

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.

que proposes-tu pour a ?

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

Merci à tous pour vos participations.

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

" 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.

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.

Bonjour, :)

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

Citation:

---

Envoyé par 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.

---

D'abord les liens cités:

Citation:

---

Envoyé par DonQuiche

... 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 ...

Citation:

---

Envoyé par macErmite

... 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 :aie: 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:

---

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.