Comment fonctionne un générateur de nombres aléatoires ? Générateurs de nombres aléatoires

Avez-vous déjà vérifié l'affirmation selon laquelle sur 10 tours de roulette, un nombre pair revient 5 fois ? Ou peut-être avez-vous participé plusieurs fois à des loteries et avez même réussi à gagner ? Si nous acceptons que tous les résultats sont véritablement aléatoires, nous pouvons alors parler de probabilité d’occurrence d’un événement particulier.

Pour paraphraser la dernière affirmation, répétons les paroles de personnes qui participent depuis des mois à des événements aux résultats aléatoires : le tout-puissant œuvre aléatoire.

Alors comment vérifier si le principe de distribution est aléatoire ? Un générateur peut gérer cette tâche. nombres aléatoires. Son principal avantage est qu'il fonctionne en ligne, ce qui signifie qu'il est très rapide et ne dépend pas de la présence d'une connexion Internet après le téléchargement.

Comment fonctionne un générateur de nombres aléatoires ?

Pour décrire l'œuvre, vous n'avez pas besoin de beaucoup de lettres, tout est très simple : vous devez sélectionner les nombres minimum et maximum possibles, saisir le nombre de valeurs générées, si nécessaire, cocher la case « Exclure les répétitions », ce qui empêche le apparition de numéros ayant déjà existé, puis cliquez sur le bouton Générer. Après cela, chaque clic ultérieur sur le bouton produira de nouvelles options de distribution.

Pourquoi cela pourrait-il être nécessaire ? Par exemple, pour obtenir numéros chanceuxà la loterie ou à la roulette. De plus, le générateur de nombres pseudo-aléatoires est capable d'émuler des barils de loto ou un tirage au sort pour une compétition - pile et face sont représentés par zéro ou un. Mais l'essentiel est qu'après avoir chargé la page, vous n'avez pas besoin d'une connexion Internet - le code est écrit en JavaScript et exécuté du côté de l'utilisateur, dans son navigateur.

Tester le fonctionnement de ce générateur en ligne a parfois donné des résultats très intéressants : l'utilisation des chiffres 0 et 1, avec 10 options, produisait pas si rarement une distribution dans le rapport de 7 pour 3, voire 6. numéros identiques contracter.

Pour quoi d'autre, outre le loto et les exemples ci-dessus, le hasard peut-il être utile pour distribuer des numéros ? Au moins pour le jeu de devinettes. Vous avez probablement joué à ce jeu dans votre enfance : l'animateur devine un nombre de 1 à 100, et les autres essaient de le deviner. Par rapport à ce générateur, vous agissez en tant que leader, et l'ordinateur tente de deviner ce qui se cache.

Vous pouvez même jouer Bataille navale, recevant immédiatement un groupe de nombres compris entre 0 et 99. Dans ce cas, le chiffre le plus significatif du nombre est utilisé comme lettres (qui sont indiquées horizontalement) - 0 ... 9 est un ... et, le dans ce cas, les chiffres faibles remplacent la plage 1 ... 10, puis un seul est ajouté. Peut-être que cette approche ne semble pas très claire à l’heure actuelle, mais c’est une question d’habitude.

Un autre manière intéressante utilisez - vérifiez votre intuition. Vous essayez de prédire quels nombres (un par un ou en groupe) le générateur produira, appuyez sur un bouton et vérifiez à quel point vous étiez proche du résultat correct. Qui sait, peut-être qu'après plusieurs tentatives, vous serez en mesure de prédire avec précision le résultat ?

Mais il faut garder à l’esprit que le générateur de nombres aléatoires s’appelle ainsi pour une raison. Les méthodes actuelles ne sont pas en mesure de fournir une valeur véritablement aléatoire - cela dépend de nombreux facteurs, parmi lesquels le nombre précédent, heure actuelle, le contenu d'une cellule mémoire particulière et d'autres données. Mais pour les besoins domestiques, leur fonctionnalité est généralement suffisante à 100 %.

Eh bien, j'espère que vous trouverez une utilisation plus étendue du générateur que les options décrites ici. Et peut-être que tu peux même suggérer bonne idée pour étendre les fonctionnalités existantes. En fin de compte, ce sont les pensées les plus incroyables qui sont finalement passées d’une vague idée à une véritable incarnation.

Sur les processus aléatoires macroscopiques utilisant de tels objets simples, Comment dé, roulette ou pièce de monnaie, peut être basé générateurs de nombres aléatoires. La théorie du chaos et la théorie des systèmes dynamiques instables peuvent expliquer la présence d'imprévisibilité dans les données, et même les systèmes macroscopiques entièrement définis par les équations de Newton ont souvent des résultats imprévisibles en pratique, car ils dépendent de détails microscopiques des conditions initiales.

À propos, sur notre site Web, vous pouvez générer un nombre aléatoire à l'aide du générateur de nombres aléatoires en ligne.

Qu'est-ce qu'un générateur de nombres aléatoires et comment utilise-t-il des processus physiques aléatoires ?

Vitesse d'obtention de nombres aléatoires, suffisant pour les problèmes appliqués, ne peut pas être fourni par des dispositifs basés sur des processus aléatoires macroscopiques. La source de bruit dont sont extraits les bits aléatoires est donc au cœur des AGNG modernes. Il existe deux types de sources de bruit : celles qui sont de nature quantique et celles qui n'utilisent pas de phénomènes quantiques.

Quelques phénomène naturel, comme la désintégration radioactive des atomes, sont absolument aléatoires et, en principe, ne peuvent être prédits (l'expérience Davisson-Germer peut être considérée comme l'une des premières expériences prouvant le caractère probabiliste de certains phénomènes), ce fait est une conséquence de les lois la physique quantique. Et de la mécanique statistique, il s'ensuit que chaque système dans ses paramètres a fluctuations aléatoires, si la température n'est pas égale au zéro absolu.

Générateur de nombres aléatoires complexes.

Pour AGS, le « gold standard » est constitué par certains processus de mécanique quantique, car ils sont complètement aléatoires. Utiliser dans générateurs de nombres aléatoires Les phénomènes comprennent :

• Le bruit de grenaille est le bruit qui, dans les circuits électriques, est causé par la discrétion des porteurs. charge électrique et ce terme fait également référence au bruit provoqué par instruments optiques discrétion du porteur léger.
• La diffusion paramétrique spontanée peut également être utilisée dans générateurs de nombres aléatoires.
• Désintégration radioactive - présente le caractère aléatoire de chacun des événements de désintégration individuels, elle est donc utilisée comme source de bruit. En conséquence, un nombre différent de particules à différents intervalles de temps frappent le récepteur (il peut s'agir d'un compteur Geiger ou d'un compteur à scintillation).

Il est beaucoup plus facile de détecter des phénomènes non quantiques, mais sur cette base générateurs de nombres aléatoires, alors ils auront une forte dépendance à la température (par exemple, la quantité de bruit thermique sera proportionnelle à la température environnement). Parmi ceux utilisés dans AGNG, on peut noter les processus suivants :

• Bruit thermique dans une résistance, qui après amplification produit générateur de tension aléatoire. En particulier, le générateur de nombres de l’ordinateur Ferranti Mark 1 était basé sur ce phénomène.
• Le bruit atmosphérique, qui est mesuré par un récepteur radio, peut également inclure la réception de particules arrivant de l'espace vers la Terre, enregistrées par le récepteur, et leur nombre sera aléatoire, à différents intervalles de temps.
• La différence de vitesse des horloges est un phénomène qui signifie que les vitesses des différentes horloges ne coïncideront pas du tout.

Pour obtenir à partir d’un processus physique aléatoire séquence de bits aléatoires, alors il existe plusieurs approches pour cela. L'un d'eux est que le rapport signal/bruit reçu est amplifié, puis filtré et introduit dans l'entrée d'un comparateur de tension à grande vitesse pour obtenir un signal logique. La durée des états comparateurs sera aléatoire et cela vous permettra de créer séquence de nombres aléatoires, en prenant des mesures de ces états.

La deuxième approche consiste à appliquer un signal aléatoire à l'entrée d'un convertisseur analogique-numérique (des appareils spéciaux et l'entrée audio d'un ordinateur peuvent être utilisés), représentant une séquence de nombres aléatoires, ce qui entraînera un résultat numérisé. signal et en même temps il peut être traité dans un logiciel.

Qu'est-ce qu'un générateur de nombres aléatoires et quels autres phénomènes utilise-t-il ?

Utiliser des processus physiques aléatoires générateurs de nombres aléatoires, permettent d'obtenir de bons nombres aléatoires, mais leur production est coûteuse et relativement difficile (c'est particulièrement vrai pour les ANGN basés sur désintégration radioactive), mais il existe d'autres sources d'aléatoire plus accessibles :

Génération simple de nombres aléatoires.

Travaux caméras vidéo numériques, qui utilisent l'enregistrement de phénomènes macroscopiques, doivent être classés parmi les générateurs les plus inhabituels. Par exemple, générer des nombres aléatoires, une équipe de Silicon Graphics a utilisé des séquences vidéo d'une lampe à lave car la cire change de forme de manière chaotique dans la lampe. Les jets d'un ventilateur dans le courant d'air ou les bulles dans un aquarium peuvent également être utilisés comme sujet de photographie.

• Traduction

Imaginez que nous sommes en 1995 et que vous êtes sur le point d'effectuer votre premier achat en ligne. Vous ouvrez votre navigateur Netscape et sirotez votre café tout en page d'accueil Se charge lentement. Votre chemin se trouve sur Amazon.com, une nouvelle boutique en ligne dont un ami vous a parlé. Lorsque vient le temps de finaliser l’achat et de saisir les données personnelles, l’adresse dans le navigateur passe de « http » à « https ». Cela indique que l'ordinateur a établi une connexion cryptée avec le serveur Amazon. Vous pouvez désormais transférer les informations de votre carte de crédit vers le serveur sans craindre les fraudeurs qui souhaitent intercepter les informations.

Malheureusement, votre premier achat en ligne a été compromis dès le début : vous découvrirez bientôt que le protocole soi-disant sécurisé utilisé par le navigateur pour établir une connexion n'est en réalité pas très sécurisé.

Le problème est que les clés secrètes utilisées par Netscape n'étaient pas assez aléatoires. Leur longueur n'était que de 40 bits, ce qui représente environ un billion de dollars. combinaisons possibles. Il semble un grand nombre, mais les pirates ont réussi à déchiffrer ces codes, même sur des ordinateurs des années 1990, en 30 heures environ. Le nombre supposément aléatoire utilisé par Netscape pour générer la clé secrète était basé uniquement sur trois significations: l'heure de la journée, le numéro d'identification du processus et le numéro d'identification du processus mère sont tous prévisibles. Grâce à cela, l'attaquant a pu réduire le nombre d'options de force brute et trouver la clé souhaitée beaucoup plus tôt que prévu par Netscape.

Les programmeurs de Netscape auraient adoré utiliser des nombres complètement aléatoires pour générer la clé, mais ils ne savaient pas comment les obtenir. La raison en est que ordinateurs numériques sont toujours dans un état précisément défini, qui ne change que lorsqu'une certaine commande est reçue du programme. Le mieux que vous puissiez faire est d'imiter le caractère aléatoire en générant des nombres dits pseudo-aléatoires à l'aide d'une fonction mathématique spéciale. Un ensemble de ces nombres semble à première vue complètement aléatoire, mais quelqu'un d'autre utilisant la même procédure pourrait facilement générer exactement les mêmes nombres, ils sont donc généralement médiocres pour le cryptage.

Les chercheurs ont réussi à inventer des générateurs de nombres pseudo-aléatoires qui se révèlent cryptographiquement sécurisés. Mais ils doivent démarrer avec une bonne graine aléatoire, sinon ils généreront toujours le même ensemble de nombres. Et pour cette valeur initiale, vous avez besoin de quelque chose de vraiment impossible à deviner ou à prédire.

Heureusement, il n'est pas difficile d'obtenir des valeurs vraiment imprévisibles en utilisant l'univers chaotique qui entoure de tous côtés le monde strictement déterministe des bits informatiques. Mais comment faire exactement ?

Pendant dernières années il existe une source de nombres aléatoires en ligne appelée Lavarand. Il a été créé en 1996 pour générer automatiquement des valeurs aléatoires en traitant des photographies d'une lampe décorative - une lampe à lave, qui change d'apparence de manière imprévisible à chaque seconde. Depuis, les valeurs aléatoires de cette source ont été utilisées plus d’un million de fois.

Il existe également des générateurs matériels de nombres aléatoires plus sophistiqués qui enregistrent effets quantiques, par exemple, des photons frappant un miroir. Vous pouvez obtenir des nombres aléatoires sur un ordinateur ordinaire en enregistrant des événements imprévisibles, tels que l'heure exacte à laquelle vous avez appuyé sur un bouton du clavier. Mais pour obtenir un grand nombre de ces valeurs aléatoires, vous devez appuyer sur de nombreux boutons.

Mes collègues et moi chez Intel avons décidé que nous devions créer une méthode plus simple. C'est pourquoi nombre de nos chipsets incluent un générateur de nombres aléatoires analogique depuis plus d'une décennie. Le problème est que son circuit analogique gaspille de l’énergie. De plus, il est difficile de maintenir la fonctionnalité de ces circuits analogiques à mesure que le processus de fabrication des puces s’améliore et se miniaturise. Par conséquent, nous avons maintenant développé un nouveau système entièrement numérique qui permet au microprocesseur de générer un riche flux de valeurs aléatoires sans ces problèmes. Ce nouveau générateur de nombres aléatoires numériques arrivera bientôt chez vous avec un nouveau processeur.

La première tentative d'Intel La création du meilleur générateur de nombres aléatoires sur les PC classiques remonte à 1999, lorsque Intel a introduit le composant Firmware Hub pour les chipsets. Le générateur de nombres aléatoires (PDF) de la puce est une conception d'oscillateur en anneau analogique qui détecte le bruit thermique des résistances, l'amplifie et utilise le signal résultant pour faire varier la période d'un générateur d'horloge relativement lent. Pour chaque « tick » imprévisible de ce générateur lent, le microcircuit imposait la fréquence d'oscillation d'un deuxième générateur rapide, qui change régulièrement de valeur entre deux états binaires : 0 et 1. Le résultat est une séquence imprévisible de zéros et de uns.

Le problème est que l'oscillateur en anneau, responsable de l'amplification du signal thermique, consomme trop d'énergie - et il fonctionne en permanence, que l'ordinateur ait ou non besoin de nombres aléatoires. ce moment. Ces composants analogiques constituent également une nuisance lorsqu’une entreprise modifie son processus de fabrication de puces. Toutes les quelques années, l’entreprise modernise ses lignes de production pour fabriquer des puces à plus petite échelle. Et chaque fois que ce fragment analogique doit être calibré et testé d'une nouvelle manière, ce travail complexe et minutieux est devenu un véritable casse-tête.

C'est pourquoi, en 2008, Intel a décidé de développer un générateur de nombres aléatoires fonctionnant exclusivement sur base numérique. Des chercheurs de l'entreprise de Hillsboro (Oregon, États-Unis), en collaboration avec des ingénieurs du Design Lab de Bangalore (Inde), ont commencé à étudier un problème clé : comment obtenir un flux aléatoire de bits sans utiliser de circuits analogiques.

Ironiquement, la solution proposée viole la règle de base de la conception numérique selon laquelle un circuit doit toujours être dans une position spécifique et renvoyer soit un 0 logique, soit un 1. Bien entendu, un élément numérique peut passer de courtes périodes de temps dans une position indéterminée, commutant entre ces deux valeurs. Cependant, il doit fonctionner de manière extrêmement précise et ne doit jamais osciller entre eux, sinon cela entraînerait des retards, voire des pannes, dans le système. Dans notre générateur de bits aléatoires, les fluctuations sont une fonctionnalité et non un bug.

Notre précédent générateur analogique n'était capable de produire que quelques centaines de kilobits de nombres aléatoires par seconde, tandis que le nouveau les génère à un débit d'environ 3 Gb/s. Cela commence par collecter les valeurs presque aléatoires des deux inverseurs dans des blocs de 512 bits. Ces blocs sont ensuite divisés en paires de nombres de 256 bits. Bien entendu, si les 512 bits d’origine ne sont pas complètement aléatoires, ces nombres de 256 bits ne le seront pas non plus. Mais ils peuvent être combinés mathématiquement pour produire un nombre de 256 bits proche de l’idéal.

TROIS NIVEAUX DE CHIFFRES : Le générateur de nombres aléatoires Intel Bull Mountain empêche toute variation de prévisibilité grâce à un processus en trois étapes. Premièrement, le circuit numérique génère un flux de bits aléatoires. Ensuite, le « normalisateur » (conditionneur) génère de bonnes graines aléatoires basées sur ce flux. Dans la troisième étape, le générateur de nombres pseudo-aléatoires produit un flux de chiffres à utiliser dans logiciel.

Tout cela est mieux illustré par une simple illustration. Supposons un instant que le générateur de bits aléatoires produise des modèles de 8 bits, c'est-à-dire des nombres compris entre 0 et 255. Supposons également que ces nombres de 8 bits ne soient pas complètement aléatoires. Imaginez maintenant que, par exemple, un défaut subtil dans le circuit décale les valeurs de sortie de partie inférieure gamme. À première vue, le flux de nombres aléatoires semble bon, mais si vous traitez des millions de valeurs, vous remarquerez que les nombres en haut de la plage sont légèrement moins courants que les nombres en bas.

Un des solutions possibles Le problème est simple : prenez toujours une paire de nombres de 8 bits, multipliez-les, puis supprimez les huit premiers bits du nombre de 16 bits obtenu. Cette procédure éliminera presque complètement la distorsion.

Bull Mountain ne fonctionne pas avec des nombres de 8 bits : il fonctionne, comme déjà indiqué, avec des nombres de 256 bits. Et il ne les multiplie pas, mais effectue des opérations cryptographiques plus complexes. Mais l'idée de base est la même. Vous pouvez considérer cette étape comme une « normalisation » pour éliminer ces écarts par rapport à distribution aléatoire nombres qui peuvent survenir dans un circuit avec deux onduleurs.

Nous voulons vraiment bien dormir la nuit, c'est pourquoi nous avons conçu des circuits supplémentaires qui testent les flux de nombres de 256 bits qui entrent dans le « normaliseur » afin qu'ils ne soient pas trop biaisés dans une direction. Si cela est constaté, nous le marquons comme défectueux et non conforme aux normes. Ainsi, les opérations sont effectuées uniquement avec des paires de nombres de haute qualité.

Le caractère aléatoire garanti ne suffit pas si les valeurs aléatoires ne sont pas produites assez rapidement pour répondre aux normes. Bien que la boucle matérielle génère des threads beaucoup plus rapidement que ses prédécesseurs, elle n’est toujours pas suffisante pour certaines tâches modernes. Pour que Bull Mountain puisse produire des nombres aléatoires aussi rapidement que les générateurs logiciels de nombres pseudo-aléatoires produisent un flux, tout en économisant haute qualité nombres aléatoires, nous avons ajouté un niveau supplémentaire au schéma. Ici, des nombres aléatoires de 256 bits sont utilisés comme graines aléatoires cryptographiquement sécurisées pour générer un grand nombre de nombres pseudo-aléatoires de 128 bits. Étant donné que les nombres 256 bits sont délivrés à 3 GHz, il existe suffisamment de matériel garanti pour générer rapidement des clés cryptographiques.

La nouvelle instruction, appelée RdRand, permet à un programme ayant besoin de nombres aléatoires d'adresser une requête au matériel qui les produit. Conçue pour les processeurs Intel 64 bits, l'instruction RdRand est la clé du générateur Bull Mountain. Il extrait des valeurs aléatoires de 16, 32 ou 64 bits et les place dans un registre accessible par le programme. L'instruction RdRand a été rendue publique il y a environ un an et le premier processeur Intel à la prendre en charge sera Ivy Bridge. Le nouveau chipset est 37 % plus rapide que son prédécesseur et la taille de ses éléments minimaux a été réduite de 32 à 22 nanomètres. L'augmentation globale des performances correspond bien aux besoins de notre générateur de nombres aléatoires.

Bien que lampes à lave cool, ils ne s'intégreront pas dans tous les intérieurs. Nous pensons, au contraire, que notre approche de génération de nombres aléatoires trouvera l'application la plus universelle.

Comme déjà mentionné, l'enregistrement du moment exact des pressions sur les touches a été utilisé dans le passé comme source pratique de valeurs de départ aléatoires pour les générateurs. Dans le même but, nous avons utilisé les mouvements de la souris et même la vitesse de recherche des secteurs sur le disque dur. Mais de tels événements ne vous donnent pas toujours suffisamment de bits aléatoires, et après un certain temps de mesure, ces bits deviennent prévisibles. Pire encore, puisque nous vivons désormais dans un monde de serveurs avec

Tous les phénomènes qui nous arrivent sont de deux types : aléatoires et naturels. Par exemple, vous n'aviez pas assez de factures pour acheter un magnétophone et vous avez décidé d'acheter un lecteur - c'est-à-dire l'action est logique et attendue. Mais, en vous dirigeant vers le magasin, vous découvrez le montant requis, ce qui a accidentellement changé vos plans. Le fonctionnement du générateur de nombres aléatoires dépend entièrement du mécanisme spécifié dans l'opérateur, de sorte que tous les nombres émis sont pseudo-aléatoires dans l'événement en cours. Opérateurs qui reviennent nombres aléatoires, se réfère à l'heure, à savoir l'heure du système. Ceux. Tant dans le monde qu’en programmation, rien n’est complètement absolu.

fonction rand

En programmation C, des opérateurs intégrés ont été inventés pour obtenir des valeurs aléatoires, qui nous donnent les résultats requis. Et donc, pour créer un nombre aléatoire, utilisez fonction rand, lequel opérateur Rand utilisé pour obtenir des nombres aléatoires qui renvoient une plage de 0 à une certaine constante. De plus, cette constante est déclarée dans la directive système « stdlib.h », où est basée cette fonction rand. La syntaxe de cette fonction est simple : int m= rand(); ceux. un entier est renvoyé. Après avoir testé l'opérateur en pratique, vous verrez que les chiffres qui apparaissent au démarrage de l'application sont identiques. L'oubli est que l'opérateur Rand travaille avec la même heure système, qui a été préservée lors de la compilation. Ce générateur les nombres aléatoires sont liés à un algorithme permettant de modifier la durée du programme, alors tout ne fonctionne pas correctement.

Parlons maintenant du sable et du hasard

Pour ce problème, une fonction qui remettrait le temps intégré à zéro à chaque fois que l'opérateur rand était appelé était indispensable, et les développeurs de logiciels l'ont fait. fonction srand. L'action permet à la fonction Rand d'accéder à chaque fois non pas à la minuterie installée, mais à la minuterie intégrée actuelle, ce qui permet au générateur de fonctionner correctement - pour produire des valeurs aléatoires. Récemment, dans la programmation C++, le mécanisme d'émission de nombres aléatoires a été amélioré en raison de l'apparition des microsecondes. De plus, la gamme de valeurs s'est élargie et toutes les innovations actuelles ont été transformées en fonction aléatoire.

Qu’est-ce que le hasard dans un ordinateur ? Comment les nombres aléatoires sont-ils générés ? Dans cet article, nous avons essayé d’apporter des réponses simples à ces questions.

Dans les logiciels, et dans la technologie en général, il existe un besoin de caractère aléatoire reproductible : les nombres et les images qui semblent aléatoires sont en réalité générés par un algorithme spécifique. C'est ce qu'on appelle le pseudo-aléatoire et nous examinerons des moyens simples créer des nombres pseudo-aléatoires. À la fin de l’article, nous formulerons un théorème simple pour générer ces nombres apparemment aléatoires.

Déterminer ce qui constitue exactement un accident peut être assez difficile. Il existe des tests (comme la complexité de Kolmogorov) qui peuvent vous donner une valeur exacte du caractère aléatoire d'une séquence particulière. Mais nous ne nous embêterons pas, nous essaierons simplement de créer une séquence de nombres qui sembleront sans rapport les uns avec les autres.

Souvent, il ne suffit pas d’un seul nombre, mais de plusieurs nombres aléatoires générés en continu. Par conséquent, étant donné la valeur de départ, nous devons créer d’autres nombres aléatoires. Cette valeur initiale est appelée graine, et nous verrons comment l'obtenir plus tard. Pour l'instant, concentrons-nous sur la création d'autres valeurs aléatoires.

Générer des nombres aléatoires à partir d'une graine

Une approche pourrait consister à appliquer une formule mathématique folle à la graine, puis à la tordre tellement que le nombre de sortie semble imprévisible, puis à la prendre comme graine pour la prochaine itération. La seule question est de savoir à quoi devrait ressembler cette fonction de distorsion.

Expérimentons cette idée et voyons où elle nous mène.

La fonction de distorsion prendra une valeur et en renverra une autre. Appelons-le R.

R (Entrée) -> Sortie

Si la valeur de notre graine est 1, alors R créera une série de 1, 2, 3, 4,... Cela n'a pas l'air aléatoire du tout, mais nous y arriverons. Laissez R ajouter maintenant une constante au lieu de 1.

Si c vaut par exemple 7, alors on obtient les séries 1, 8, 15, 22, ... Ce n'est toujours pas la même chose. De toute évidence, ce qui nous manque, c'est que les chiffres ne devraient pas seulement augmenter, mais qu'ils devraient être répartis sur une certaine plage. Nous avons besoin que notre séquence revienne au début – un cercle de chiffres !

Cercle de nombres

Regardons le cadran de l'horloge : notre rangée commence à 1 et tourne en cercle jusqu'à 12. Mais puisque nous travaillons avec un ordinateur, faisons qu'il y ait 0 au lieu de 12.

Maintenant, à partir de 1, nous ajouterons à nouveau 7. Progrès ! Nous voyons qu'après 12, notre série commence à se répéter, quel que soit le numéro avec lequel nous commençons.

Ici, nous obtenons une propriété très importante : si notre boucle est composée de n éléments, alors le nombre maximum d'éléments que nous pouvons obtenir avant qu'ils ne commencent à se répéter est n.

Réécrivons maintenant la fonction R pour qu'elle corresponde à notre logique. Vous pouvez limiter la longueur d'une boucle à l'aide de l'opérateur module ou de l'opérateur reste.

R(x) = (x + c) %m

À ce stade, vous remarquerez peut-être que certains nombres ne rentrent pas dans c. Si c = 4 et que nous commencions à 1, notre suite serait 1, 5, 9, 1, 5, 9, 1, 5, 9, ... ce qui bien sûr ne fonctionne pas pour nous, car cette suite est absolument pas aléatoire. Il devient clair que les nombres que nous choisissons pour la longueur de la boucle et la longueur du saut doivent être liés d'une manière particulière.

Si vous en essayez quelques-uns différentes significations, alors vous pouvez voir une propriété : m et c doivent être relativement premiers.

Jusqu’à présent, nous avons fait des progrès en additionnant, mais que se passerait-il si nous utilisions la multiplication ? Multiplions Xà une constante un.

R(x) = (hache + c) % m

Les propriétés auxquelles il faut obéir pour qu’un cycle complet se forme sont un peu plus spécifiques. Pour créer une boucle valide :

1. (a - 1) doit être divisible par tous les facteurs premiers m
2. (a - 1) doit être divisible par 4 si m est divisible par 4

Ces propriétés, ainsi que la règle selon laquelle m et c doivent être relativement premiers, constituent le théorème de Hull-Dobell. Nous n'examinerons pas sa preuve, mais si vous preniez un tas de valeurs différentes pour différentes constantes, vous pourriez arriver à la même conclusion.

Sélection des graines

Il est maintenant temps de parler de la partie amusante : choisir la graine initiale. Nous pourrions en faire une constante. Cela peut être utile dans les cas où vous avez besoin de nombres aléatoires, mais que vous souhaitez qu'ils soient les mêmes à chaque fois que vous exécutez le programme. Par exemple, créer la même carte pour chaque jeu.

Une autre façon consiste à obtenir une graine provenant d'une nouvelle source à chaque démarrage du programme, comme une horloge système. Ceci est utile lorsque vous avez besoin d'un nombre aléatoire total, comme dans un programme de lancer de dés.

Résultat final

Lorsqu’on applique plusieurs fois une fonction à son résultat, on obtient une relation de récurrence. Écrivons notre formule en utilisant la récursion.