Pourquoi la nouvelle bibliothèque aléatoire est-elle meilleure que std :: rand ()?

Pratiquement toutes les implémentations de “old” rand() utilisent un LCG ; bien qu’ils ne soient généralement pas les meilleurs générateurs du marché, vous ne les verrez généralement pas échouer lors d’un test aussi élémentaire – l’écart type et l’écart moyen sont généralement corrects, même par les pires PRNG.

Les échecs courants de “mauvais” – mais assez commun – les implémentations de rand() sont:

• faible caractère aléatoire des bits de poids faible;
• courte période;
• RAND_MAX faible;
• une certaine corrélation entre les extractions successives (en général, les GCL produisent des nombres sur un nombre limité d’hyperplans, même si cela peut être atténué).

Cependant, aucun d’entre eux n’est spécifique à l’API de rand() . Une implémentation particulière pourrait placer un générateur de la famille xorshift derrière srand / rand et, algoritiquement, obtenir un PRNG à la pointe de la technologie sans modification d’interface, ainsi aucun test comme celui que vous avez fait ne montrerait de faiblesse dans la sortie.

Edit: @R. remarque correctement que l’interface rand / srand est limitée par le fait que srand prend un unsigned int , de sorte que tout générateur qu’une implémentation peut placer derrière est insortingnsèquement limité aux UINT_MAX départ UINT_MAX possibles (et donc aux séquences générées). C’est vrai, bien que l’API puisse être étendue de manière sortingviale pour que srand prenne une unsigned long long , ou que l’on ajoute une surcharge distincte srand(unsigned char *, size_t) .

En effet, le problème actuel de rand() ne concerne pas beaucoup la mise en œuvre mais:

• rétrocompatibilité; beaucoup d’implémentations actuelles utilisent des générateurs sous-optimaux, généralement avec des parameters mal choisis; Un exemple notoire est Visual C ++, qui RAND_MAX un RAND_MAX de RAND_MAX seulement. Cependant, cela ne peut pas être changé facilement, cela briserait la compatibilité avec le passé – les utilisateurs de srand avec une valeur de départ fixe pour des simulations reproductibles ne seraient pas trop heureux (en effet. , IIRC, la mise en œuvre susmentionnée remonte aux premières versions de Microsoft C – ou même de Lattice C – datant du milieu des années 80);

• interface simpliste; rand() fournit un seul générateur avec l’état global pour l’ensemble du programme. Bien que cela convienne parfaitement (et en fait très pratique) pour de nombreux cas d’utilisation simples, cela pose des problèmes:

  • avec un code multithread: pour résoudre ce problème, vous avez besoin d’un mutex global, ce qui ralentirait tout sans aucune raison et supprimerait toute possibilité de répétabilité, car la séquence d’appels devient elle-même aléatoire, ou un état de thread-local; ce dernier a été adopté par plusieurs implémentations (notamment Visual C ++);
  • si vous voulez une séquence “privée”, reproductible dans un module spécifique de votre programme qui n’affecte pas l’état global.

Enfin, l’état du rand :

• ne spécifie pas une implémentation réelle (la norme C ne fournit qu’un exemple d’implémentation); par conséquent, tout programme destiné à produire une sortie reproductible (ou s’attendre à un PRNG d’une qualité connue) sur différents compilateurs doit lancer son propre générateur;
• ne fournit aucune méthode multiplateforme pour obtenir une graine décente ( time(NULL) n’est pas suffisamment granulaire, et souvent – pensez aux périphériques embarqués sans RTC – pas même assez au hasard).

D’où le nouvel en-tête , qui tente de réparer ce désordre en fournissant des algorithmes qui sont:

• entièrement spécifié (vous pouvez donc obtenir une sortie reproductible entre les compilateurs croisés et des caractéristiques garanties – disons, la plage du générateur);
• généralement de qualité supérieure ( depuis la conception de la bibliothèque ; voir ci-dessous);
• encapsulé dans des classes (aucun état global ne vous est imposé, ce qui évite les problèmes de threading et de non-localisation);

… et un random_device par défaut random_device .

Maintenant, si vous me demandez, j’aurais aussi aimé une API simple construite au-dessus de cela pour les cas “facile”, “devinez un nombre” (similaire à la façon dont Python fournit l’API “compliquée”, mais aussi l’ random.randint sortingvial random.randint & Co. utilise un PRNG global pré-ensemencé pour les personnes simples qui ne voudraient pas se noyer dans des périphériques / moteurs / adaptateurs / aléatoires à chaque fois que nous voulons extraire un numéro pour les cartes de bingo), mais il est vrai que vous pouvez facilement le construire vous-même par rapport aux installations actuelles (il ne serait pas possible de construire la “complète” API par rapport à une API simpliste).

Enfin, pour revenir à votre comparaison de performances: comme d’autres l’ont déjà précisé, vous comparez une GCL rapide à une qualité plus lente (mais généralement considérée comme de meilleure qualité) Mersenne Twister; si vous êtes d’accord avec la qualité d’un LCG, vous pouvez utiliser std::minstd_rand au lieu de std::mt19937 .

En effet, après avoir peaufiné votre fonction pour utiliser std::minstd_rand et éviter les variables statiques inutiles pour l’initialisation

 int getRandNum_New() { static std::minstd_rand eng{std::random_device{}()}; static std::uniform_int_dissortingbution dist{0, 5}; return dist(eng); } 

Je reçois 9 ms (ancien) contre 21 ms (nouveau); enfin, si je supprime dist (qui, comparé à l’opérateur classique modulo, gère l’inclinaison de la dissortingbution pour une plage de sortie non multiple de la plage d’entrée) et retourne à ce que vous faites dans getRandNum_Old()

 int getRandNum_New() { static std::minstd_rand eng{std::random_device{}()}; return eng() % 6; } 

Je le réduis à 6 ms (donc, 30% plus rapide), probablement parce que, contrairement à l’appel à rand() , std::minstd_rand est plus facile à std::minstd_rand .

Incidemment, j’ai fait le même test en utilisant un XorShift64* roulé à la main (mais se conformant plus ou moins à l’interface standard de la bibliothèque), et il est 2,3 fois plus rapide que rand() (3,68 ms contre 8,61 ms); Étant donné que, contrairement au Mersenne Twister et aux divers LCG fournis, il réussit avec brio les suites de tests aléatoires actuelles et qu’il est extrêmement rapide, on se demande pourquoi il n’est pas encore inclus dans la bibliothèque standard.

Si vous répétez votre expérience avec une plage supérieure à 5, vous obtiendrez probablement des résultats différents. Lorsque votre plage est nettement inférieure à RAND_MAX , la plupart des applications ne RAND_MAX pas de problème.

Par exemple, si nous avons un RAND_MAX de 25, alors rand() % 5 produira des nombres avec les fréquences suivantes:

 0: 6 1: 5 2: 5 3: 5 4: 5 

Comme RAND_MAX est garanti que RAND_MAX est supérieur à 32767 et que la différence de fréquences entre les moins probables et les plus probables est de 1 seulement, pour les petits nombres, la dissortingbution est suffisamment aléatoire pour la plupart des cas d’utilisation.

Tout d’abord, étonnamment, la réponse change en fonction de l’utilisation du nombre aléatoire. Si c’est pour conduire, disons, un changeur de couleur d’arrière-plan aléatoire, utiliser rand () convient parfaitement. Si vous utilisez un nombre aléatoire pour créer une main de poker aléatoire ou une clé cryptographiquement sécurisée, alors tout va bien.

Prévisibilité: la séquence 012345012345012345012345 … fournirait une dissortingbution égale de chaque nombre de votre échantillon, mais ne serait évidemment pas aléatoire. Pour qu’une séquence soit aléatoire, la valeur de n + 1 ne peut pas être facilement prédite par la valeur de n (ou même par les valeurs de n, n-1, n-2, n-3, etc.). Clairement une séquence répétée des mêmes chiffres est un cas dégénéré, mais une séquence générée avec n’importe quel générateur de congruence linéaire peut être analysée; Si vous utilisez les parameters par défaut prêts à l’emploi d’un LCG commun à partir d’une bibliothèque commune, une personne mal intentionnée pourrait “interrompre la séquence” sans trop d’effort. Dans le passé, plusieurs casinos en ligne (et certains castrés) ont été détruits par des machines utilisant de médiocres générateurs de nombres aléatoires. Même les personnes qui devraient savoir mieux ont été rattrapées; Il a été démontré que les puces TPM de plusieurs fabricants étaient plus faciles à décomposer que la longueur en bits des clés ne le prévoirait autrement en raison des mauvais choix effectués avec les parameters de génération de clés.

Dissortingbution: comme indiqué dans la vidéo, prendre un modulo de 100 (ou toute valeur non divisible de manière égale dans la longueur de la séquence) garantira que certains résultats seront au moins légèrement plus probables que d’autres. Dans l’univers de 32767 valeurs de départ possibles modulo 100, les nombres de 0 à 66 apparaîtront 328/327 (0,3%) plus souvent que les valeurs de 67 à 99; un facteur qui peut fournir un avantage à un attaquant.

La réponse correcte est: cela dépend de ce que vous entendez par “meilleur”.

Les “nouveaux” moteurs ont été introduits en C ++ il y a plus de 13 ans. Ils ne sont donc pas vraiment nouveaux. La bibliothèque C rand() été introduite il y a plusieurs décennies et a été très utile à cette époque pour de nombreuses choses.

La bibliothèque standard C ++ fournit trois classes de moteurs générateurs de nombres aléatoires: le linéaire congruentiel (dont rand() est un exemple), le retardé de Fibonacci et le Mersenne Twister. Il y a des compromis entre chaque classe et chaque classe est “meilleure” à certains égards. Par exemple, les LCG ont un très petit état et, si les bons parameters sont choisis, assez rapidement sur les processeurs de bureau modernes. Les LFG ont un état plus étendu et utilisent uniquement des extractions de mémoire et des opérations d’addition. Ils sont donc très rapides sur les systèmes embarqués et les microcontrôleurs dépourvus de matériel mathématique spécialisé. Le MTG a un état énorme et est lent, mais peut avoir une très grande séquence non répétée avec d’excellentes caractéristiques spectrales.

Si aucun des générateurs fournis n’est suffisant pour votre utilisation spécifique, la bibliothèque standard C ++ fournit également une interface pour un générateur de matériel ou votre propre moteur personnalisé. Aucun des générateurs n’est destiné à être utilisé de manière autonome: son utilisation prévue est via un object de dissortingbution qui fournit une séquence aléatoire avec une fonction de dissortingbution de probabilité particulière.

Un autre avantage de rapport à rand() est que rand() utilise un état global, qu’il n’est ni réentrant, ni threadsafe, et permet une seule instance par processus. Si vous avez besoin d’un contrôle précis ou d’une prévisibilité (c’est-à-dire capable de reproduire un bogue en fonction de l’état initial du RNG), alors rand() est inutile. Les générateurs sont instanciés localement et ont un état sérialisable (et restaurable).