Comment tester des nombres aléatoires?
j'ai écrit en matlab, un programme, qui est supossed pour générer des nombres aléatoires entre 0 et 1. j'ai test avec la seule runstest dans matlab, et te résultat est que la séquence est aléatoire. j'ai vu les histogrammes de trop, et ils ont une distribution bêta. je veux tester ce rng avec d'autres tests, tels que les irréductibles, ent, ou du nist, mais je ne sais pas comment. quelqu'un peut m'expliquer comment les utiliser, ou me suggérer quelques autres aléatoire tests. merci
- Ici vous pouvez trouver inconditionnels de programmes de test et le code source pour différents systèmes d'exploitation. Un autre lien sympa pourrait être la celui-ci.
- Habituellement, vous ne devriez pas rouler votre propre Rng, même si, comme ils sont très durs à obtenir le droit. Même les tests peuvent ne pas vous avertir à l'échec, car ils chaque test seulement un cas très spécifique. Nous avons mis en œuvre la plupart des NIST 800-22 pour la modélisation et la simulation package et ces tests sont pour le cryptage des applications—et pourtant, même de mauvais générateurs comme une simple GRILLE de réussir tous les tests (bien que RANDU échoue pour certains, qui est au moins une petite victoire).
- c'est un genre de petit thèse( s'il peut être nommé thèse en physique, où une carte unimodale (logistique de la carte) est utilisé dans un caotic régime, pour générer de l'aléatoire nr entre 0 et 1. j'ai wrriten mon propre rng, et maintenant, je dois tester et puis faire la conclusion: peut unimodale de la carte utilisée comme générateur de nombres aléatoires, ce qui est le algotithm que d'utiliser les autres standart prng, etc. donc, c'est ma première étape: tester ma propre rng.
- Ah, ok. Eh bien, puis aller avec ce que vous pouvez trouver. NIST, jusqu'au-boutiste, DieHarder, TestU01, ent sont ceux qui viennent à mon esprit au monent. l'utilisation est généralement documentée et la plus devrait être en mesure de faire face avec des fichiers contenant des octets aléatoires ou des chiffres.
- Numérique Recettes 3e Édition: L'Art de l'Informatique Scientifique par William H. Appuyez sur a un chapitre complet consacré aux générateurs de nombres aléatoires, qui est très intéressant si vous voulez comprendre pourquoi leur qualité est un problème.
Vous devez vous connecter pour publier un commentaire.
Avec la plupart des tests que vous pouvez fournir un grand fichier de nombres aléatoires (entier ou à virgule flottante) et de lancer différents tests sur l'échantillon de fichier. IRRÉDUCTIBLES travaillé de cette façon, si je me souviens bien, et quelques autres n', trop. Si vous voulez vraiment voir votre générateur échouent, vous pouvez essayer d'utiliser TestU01 par Pierre L'Ecuyer qui a assez de tests pour laisser presque chaque générateur de l'échec à au moins un test 🙂
Encore, pour la plupart des suites de test il existe une documentation abondante, au moins je sais que cela pour Jusqu'au-boutiste, à la suite de tests de NIST SP 800-22 ainsi que DieHarder et TestU01 (liens vers les docs). Les méthodes pour la fourniture de nombres aléatoires de test sont généralement différents, mais mentionné dans la documentation correspondante.
Les tests disponibles sont:
Dieharder - http://www.phy.duke.edu/~rgb/General/dieharder.php
TestU01 - http://simul.iro.umontreal.ca/testu01/tu01.html
RaBiGeTe - http://cristianopi.altervista.org/RaBiGeTe_MT/
NIST STS - http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html
PractRand - http://pracrand.sourceforge.net/
L'un de ceux qui peuvent tester les bits à partir d'un fichier. Certains (PractRand, Dieharder, ce n'est pas sûr TestU01) pouvez tester de données transmis dans l'entrée standard. Certains ont également en charge la liaison de votre PRNG directement à la suite de tests, de manière dynamique (uniquement RaBiGeTe offre un réel soutien dynamique de la liaison de votre GÉNÉRATEUR à elle) ou de façon statique.
La qualité n'est pas égale. Si vous avez beaucoup de bits du GÉNÉRATEUR de sortie, PractRand pouvez trouver la plus grande variété de préjugés plus rapide (plein diclosure: j'ai écrit PractRand), suivie par TestU01. Si vous n'avez pas beaucoup de bits, RaBiGeTe pourrait faire mieux. NIST STS et Dieharder généralement à la traîne.
La commodité de l'interface est également pas égaux. PractRand et Dieharder sont mis en place pour la ligne de commande d'automatisation. PractRand et TestU01 ont tendance à avoir la plus simple de sortie à interpréter, à mon avis. Dieharder n'est pas mauvais dans ce domaine. RaBiGeTe et le NIST STS, eh bien... ils à la fois de promouvoir ce qui me semble être trop compliqué & inutile de visualisations des distributions des résultats de l'essai.
Aussi, NIST STS et Dieharder les deux ont des problèmes de faux positifs.
Il y a aussi des ENT, ne peut pas trouver de lien pour le moment... il est assez commode de l'interface de l'IIRC, mais n'est pas très bon à trouver des biais.
Il y a beaucoup de choses à tester, si vous voulez tester votre RNG sur votre propre. Voici quelques fonctions de base qui peut révéler votre numéro de séquence, pas vraiment au hasard, ou peut-être impossible à distinguer de hasard?
Prendre un coup d'oeil à:
La distribution - vous avez déjà fait un peu d'analyse sur votre distribution. Vous voulez que chaque nombre possible d'avoir la même probabilité de se produire.
Comportement cyclique - fait la même séquence se répète encore et encore? La séquence répétitive peut être assez long.
Occurence de doublons (...C B B A F F...) , des triplets (...C B A A A F...) etc. Statistiquement, dans une séquence de nombres aléatoires, vous avez une certaine probabilité de dulplicates (le même nombre généré deux fois de suite), triplets, etc. Calculer cette probabilité et de vérifier si votre séquence pseudo-aléatoire de nombres a la même probabilité de doublons se produit?
Noter que pour la plupart de ces tests, vous devez avoir une assez longues séquences de nombres aléatoires afin d'être en mesure d'obtenir sensible et l'exactitude des résultats de l'analyse statistique.
Je suppose peudo séquences de nombres aléatoires de nombres entiers, ce qui est facilement résolu en multipliant votre [0, 1] nombres par une constante appropriée.
Pour votre cas d'utilisation, je recommande d'écrire l'
0et1nombres générés par votre rng comme des caractères dans un fichier et ensuite utiliser ce fichier comme données d'entrée pour la suite de test du programme.Noter que la séquence doit être d'au moins 1000 caractères pour être testé par STS.
Lorsque vous l'exécutez, n'oubliez pas d'utiliser le drapeau
-F 'a', pour dire au programme que le fichier d'entrée est faite de ASCII0et1caractères.Je recommande également d'essayer cette version non officielle du NIST, de la Statistique de la Suite de tests, où j'ai trafiqué avec l'original NIST code source et a essayé de l'optimiser.
Pour votre commodité, voici la commande, je voudrais suggérer que vous utilisez pour exécuter les tests avec elle (après avoir compilé le programme à partir des sources avec
$ make):Vous pouvez augmenter le nombre de chaînes de bits testé (indiqué par la
-idrapeau) pour une plus grande utilisation de plus de données à partir de l'entrée. Par exemple, vous pouvez choisir:Une fois tous les tests ont été exécutés, le programme va générer un rapport dans un fichier appelé
result.txt, que vous pouvez utiliser pour évaluer la qualité de votre rng.Noter que ce programme, il n'est pas NIST officiel bien. Aussi, notre suite de test modifications ne subissent pas de tests 3ème partie; il est donc AUSSI-sans garantie que ce soit.
J'ai été à la recherche à ce problème pour la dernière année, et je suis venu à la conclusion qu'il n'y a pas de méthode standard de test pour le hasard dans le monde réel. Je pense que c'est juste ce que vous faire à l'aise. Vous ne pouvez pas prouver qu'une suite est aléatoire, et vous ne pouvez pas prouver facilement qu'une séquence n'est pas aléatoire.
(Je suis écarté de séquences aléatoires qui sont vraiment vraiment pas au hasard, comme 0123456789...répété.)
user3535668 les listes de certains tests connus, et toute une liste de questions avec eux. Je peux en ajouter d'autres. Jusqu'au-boutiste - quelle taille doit avoir le fichier d'entrée, et il devrait se composer uniquement de 32 bits entiers? ENT - semble tout à fait adapté pour les erreurs grossières, mais le chi test est utile. Le NIST manuel de l'utilisateur >100 pages - bonne chance. TestU01 - même compilation des questions. Et une fois que vous avez entassé dans votre ordinateur, s'il fonctionne correctement? Comment pouvez-vous alors faire confiance à la sortie? Et comment savez-vous si un test a échoué? Quel est le niveau de p ou KS est considéré comme trop extrême?
Je tiens à ajouter que vous devriez considérer le développement de l'aléatoire des suites de test vis-à-vis de la real-politique. C'est dans un universitaire de l'intérêt à développer des tests qui discréditer générateurs de nombres aléatoires. Après tout, vous n'obtenez pas de financement à produire des résultats qui disent "c'est bon, rien trouvé, pas de travaux requis".
Les lecteurs ne seront pas d'accord avec ce principe, mais je vous suggère de considérer ce qui se passe dans le monde réel où nous vivons, pas à un programme d'étagère. Il n'existe pas de test standard. Prendre en compte:-
Random.org - utilisé le premier cycle de procéder à certains homebrew tests pour une thèse. Et essentiellement compter le nombre de 1 et de 0. ENT n'similaire.
Hotbits - champion de l'simpliste ENT, et une version piratée de Dieharder que la plupart des gens ont de la difficulté à s'exécuter, jamais l'esprit d'essayer de comprendre myriade de test initialisers.
Académique générateur de documents de beaucoup le recours à Knuth écrits et familiale techniques. Certains d'utiliser certains des outils mentionnés ci-dessus. Certains acceptent un certain nombre d'erreurs de test à l'intérieur de ces suites.
Le seul exemple que j'ai trouvé jusqu'à présent dans cet homme de l'univers, qui semble porter tout le poids réel (c'est à dire si elle échoue, vous allez à la prison de type de poids) est la certification de Playtech PLC, royaume-UNI fournisseur de logiciels de jeux de casino. Ils fournissent certains des plus grands en ligne des sociétés de paris où de l'argent change de mains. Encore, ils utilisent des homebrew, les tests et les Inconditionnels de test.
Personnellement, j'aime:-
Je pense que si un fichier passe mon 1 - 3, vous aurez du mal à prouver le contraire. Me semble être un bon point de départ comme tout...
Limiter les résultats à une gamme spécifique (éventuellement à l'aide de l'opérateur mod), l'exécution de votre code quelques millions de fois, et compter combien de fois vous voyez chaque nombre dans l'intervalle. Assurez-vous que les chiffres sont à peu près les mêmes, et que vous n'avez pas de parti pris pour l'une quelconque de valeurs spécifiques.
La route que je serais probablement aller serait de faire une analyse visuelle des résultats. Le code est assez simple, comme indiqué dans le psudo-code basé sur tson article.
Aussi, Random.org a plus d'informations sur l'analyse statistique des algorithmes, mais ils utilisent aussi l'article précité que leur exemple de l'analyse visuelle.
Je suis actuellement à la recherche d'un test similaire, a été l'espoir de le trouver ici, mais n'a pas. Je vais essayer math.stackoverflow.com où je vais probablement être en mesure de demander à ce que la réponse est une mesure statistique.
Mes connaissances des statistiques est assez modéré pour savoir ce que vous cherchez sans être en mesure de fournir les détails.
Essentiellement, vous effectuez un test de régression pour savoir si vos numéros sont conformes à une distribution uniforme. Nous pouvons donc créer un chi-carré du modèle (je pense). Cela conduira à l'obtention d'un t-stat et une p-valeur. Plus un t-stat et inférieure de la p-valeur signifie qu'il n'est pas conforme à la distribution (donc nous rejetons l'hypothèse nulle). La valeur de p entre 0 et 1. Si c'est dire 0.06 ensuite, nous pouvons rejeter l'hypothèse nulle avec un intervalle de confiance de 94%.
Et pour répondre à ceux qui disent "nous ne devrions pas être en train de créer des nombres aléatoires", peut-être pas réelle des nombres aléatoires, mais on peut obtenir les données et souhaitez tester si elle correspond à une distribution uniforme, et pour les programmeurs on peut souhaiter pour tester si une fonction de hachage produit d'une distribution uniforme sur un grand nombre d'instances aléatoires de la des objets qui nous sont hachage.
Que pour un peu de code pour le NIST tests, il y a quelques-uns ici:
http://sourceforge.net/projects/randomanalysis/
qui peut vous donner ce que vous voulez.
@Anna, j'ai eu la même question que vous, et nous avons maintenant découvert Jusqu'au-boutiste grâce à certains des autres réponses.
La situation avec mon RNG est qu'il crée les 1 et les 0 et les stocke dans un fichier ASCII. Lorsque vous essayez de télécharger ce fichier en ligne de l'aléatoire des tests, il n'a pas, sans doute parce que les données doivent être au format binaire.
Et c'est effectivement le cas jusqu'au-boutiste. Si vous installez Irréductibles, vous trouverez un fichier appelé
DIEHARD.DOCqui parle à travers les étapes de la façon de convertir votre fichier ASCII dans les fichiers binaires (avec quelques autres changements que vous devez apporter à votre programme).Ce sont mes premiers pas, de toute façon. Espérons que cela aide quelqu'un.