🧜🏽 🚾 🗻 Algorithmes aléatoires 🙌🏾 👩‍👦‍👦 ‼️

Dans cet article, vous verrez les algorithmes de ~~vélo~~ les plus divers pour générer des nombres aléatoires.

À propos de quel article

A propos des algorithmes générant des nombres pseudo-aléatoires qui diffèrent par la qualité du résultat et la vitesse d'exécution. L'article sera utile à ceux qui souhaitent obtenir une génération de nombres haute performance dans leurs programmes ou aux développeurs de logiciels pour microcontrôleurs et anciennes plates-formes comme ZX Spectrum ou MSX.

Rand C ++

La première chose qu'un programmeur C ++ novice apprend à obtenir une maison aléatoire est la fonction rand, qui génère un nombre aléatoire entre 0 et RAND_MAX. La constante RAND_MAX est décrite dans le fichier stdlib.h et vaut 32'767, mais cela peut ne pas être le cas, par exemple, sous Linux ( voir commentaire ). Si rand () dans votre compilateur génère des nombres dans 32'767 (0x7FFF) et que vous souhaitez obtenir un nombre aléatoire de grande taille, le code ci-dessous peut être considéré comme une solution à ce problème:

int64_t A = rand();
A <<= 15; //   15,   7FFF  15 
A |= rand();
A <<= 15;
A |= rand();
A <<= 15;
A |= rand();
A <<= 3;
A |= rand() & 0b111; //  3

L'implémentation de la fonction rand dans l'ancien C était simple et ressemblait à ceci:

static unsigned long int next = 1;

int rand()
{
  next = next * 1103515245 + 12345;
  return (unsigned int)(next / 65536) % 32768;
}

Cette implémentation n'avait pas une très bonne distribution des nombres et est maintenant améliorée en C ++. De plus, la bibliothèque C ++ standard offre des moyens supplémentaires d'obtenir un nombre aléatoire, qui sont abordés ci-dessous.

C ++ 11 STL aléatoire

Cette variété d'aléatoire est apparue en C ++ 11 et se compose de l'ensemble de classes suivant: minstd_rand, mt19937, ranlux, knuth_b et leurs diverses variations.

Pour éviter que la séquence de nombres aléatoires ne se répète à chaque démarrage du programme, le «grain» du générateur pseudo-aléatoire est défini sous la forme de l'heure actuelle ou, dans le cas de certains jeux rétro (et pas seulement), les intervalles entre les frappes du clavier / joystick. La bibliothèque aléatoire suggère d'utiliser std :: random_device pour obtenir un grain meilleur que le temps (NULL), cependant, dans le cas du compilateur MinGW sous Windows, la fonction ne fonctionne pratiquement pas comme elle le devrait. Encore…

// ,   :
#include <random>
#include <ctime>

std::mt19937 engine; // mt19937    
engine.seed(std::time(nullptr));
/*
 ,    UNIX--    MinGW
std::random_device device;
engine.seed(device());
*/
int val = engine(); //

Certains des algorithmes de STL random peuvent fonctionner plus rapidement que rand (), mais donnent une séquence de nombres aléatoires de qualité inférieure.

PRNG - Générateur de nombres pseudo-aléatoires

Vous pouvez considérer ce nom comme synonyme de la méthode congruente linéaire. Les algorithmes PRNG sont similaires à l'implémentation rand en C et ne diffèrent que par les constantes.

unsigned PRNG()
{
  static unsigned seed = 1; //     0
  seed = (seed * 73129 + 95121) % 100000;
  return seed;
}

Les algorithmes PRNG sont rapides et faciles à implémenter dans de nombreux langages, mais n'ont pas une longue période.

Xorshift

L'algorithme présente de nombreuses variantes, différentes les unes des autres par la période et les registres utilisés. Les détails et les variétés de XorShift peuvent être consultés sur Wikipedia ou Habré. Je donnerai l'une des options avec une séquence de 2 au 128e degré.

struct seed_t
{
  unsigned x = 1; //     
  unsigned y = 123;
  unsigned z = 456;
  unsigned w = 768;
};

unsigned XorShift128()
{
  static seed_t s;
  unsigned t = s.x^(s.x<<11);
  s.x = s.y;
  s.y = s.z;
  s.z = s.w;
  s.w = (s.w^(s.w>>19)) ^ (t^(t>>8));
  return s.w;
}

Ce générateur est très bon car il n'y a aucune opération de division et de multiplication - cela peut être utile sur les processeurs et les microcontrôleurs dans lesquels il n'y a pas d'instructions de division / multiplication d'assembleur (PIC16, Z80, 6502).

Émulateur aléatoire 8 bits dans z26

Z26 est un émulateur d'un ancien préfixe Atari2600, dans le code duquel vous pouvez trouver un aléatoire orienté pour fonctionner avec des registres à 1 octet.

// P2_sreg - static uint8_t
void P2_Read_Random()
{
  P2_sreg =
    (((((P2_sreg & 0x80) >> 7) ^
       ((P2_sreg & 0x20) >> 5)) ^
      (((P2_sreg & 0x10) >> 4) ^
       ((P2_sreg & 0x08) >> 3))) ^ 1) |
        (P2_sreg << 1);
  DataBus = P2_sreg;
}

Une fois, j'ai dû faire une implémentation de cet algorithme pour z80:

Code d'assemblage

;    z26
; a - output
; rdseed - 1  
randz26:
    exx

    ld a,(rdseed)
    and 20h
    sra a
    sra a
    sra a
    sra a
    sra a
    ld h, a

    ld a,(rdseed)
    and 80h
    sra a
    sra a
    sra a
    sra a
    sra a
    sra a
    sra a
    xor h
    ld l, h
    
    ld a,(rdseed)
    and 08h
    sra a
    sra a
    sra a
    ld h, a

    ld a,(rdseed)
    and 10h
    sra a
    sra a
    sra a
    sra a
    xor h
    ld h, a
    ld a, l
    xor h
    xor 1

    ld h, a
    ld a,(rdseed)
    sla a
    or h
    ld (rdseed),a

    exx
    ret

Compact random pour Z80 de Joe Wingbermuehle

Si vous êtes intéressé à écrire des programmes pour les voitures avec zilog, je présente à votre attention un algorithme de Joe Wingbermuehle (ne fonctionne que sur zilog):

; By Joe Wingbermuehle
; a res 1 byte - out val
; rdseed res 1 byte - need for rand. != 0
rand8:
        exx
        ld      hl,(rdseed)
        ld      a,r
        ld      d,a
        ld      e,(hl)
        add     hl,de
        add     a,l
        xor     h
        ld      (rdseed),hl
        exx
        ret

Générateur de maison aléatoire dans DOOM

Dans le code source du jeu Doom, il existe un fichier intéressant appelé m_random.c (voir le code) , qui décrit la fonction du caractère aléatoire de la "table", c'est-à-dire qu'il n'y a pas de formules et de magie avec des décalages de bits.

Je vais donner un code plus compact qui montre clairement le fonctionnement de cette fonction.

const uint8_t random_map[] =
{
  4,  1,   63, 3,
  64, 22,  54, 2,
  0,  52,  75, 34,
  89, 100, 23, 84
};

uint8_t get_random()
{
  static uint8_t index = 0;
  index = (index + 1) & 0xF; // 0xF,      random_map
  return random_map[index];
}

Varik pour z80

;   (  DOOM)
; rand_table -    .  
;                        256    .
; a - output num
randtab:
    exx
    ; index
    ld a, (rdseed)
    inc a
    ;and filter ; for crop array index
    ld (rdseed), a
    ; calc array address
    ld hl, rand_table
    ld d, 0
    ld e, a
    add hl, de
    ld a, (hl) ; get num from arr
    exx
    ret

Bien sûr, ce n'est pas aléatoire et la séquence de nombres aléatoires est facile à prévoir même au niveau de l'intuition pendant le jeu, mais tout fonctionne extrêmement rapidement. Si la force cryptographique n'est pas particulièrement importante pour vous et que vous voulez quelque chose qui génère rapidement un "type aléatoire", alors cette fonction est pour vous. Par ailleurs, dans Quake3, aléatoire semble simple - rand () & 0x7FFF.

RDRAND

Certains processeurs modernes sont capables de générer des nombres aléatoires avec une seule instruction d'assembleur - RDRAND. Pour utiliser cette fonction en C ++, vous pouvez écrire manuellement les instructions nécessaires avec des insertions d'assembleur, ou connecter le fichier immintrin.h dans GCC et sélectionner l'une des variantes de la fonction _rdrandXX_step, où XX signifie le nombre de bits dans le registre et peut être 16, 32 ou 64.

#include <immintrin.h>

unsigned val;
_rdrand32_step(&val);

Si vous voyez une erreur de compilation, cela signifie que vous n'avez pas activé l'indicateur -mrdrnd ou que votre compilateur / processeur ne prend pas en charge cet outil. C'est peut-être le générateur de nombres aléatoires le plus rapide, mais il y a des questions sur sa force cryptographique, alors pensez-y.

Fin

La classe std :: minstd_rand de la bibliothèque aléatoire STL est plus rapide que rand () ordinaire et peut devenir un remplacement alternatif si vous n'êtes pas particulièrement préoccupé par la longueur de la période dans minstd. Il peut y avoir des différences dans le fonctionnement de ces fonctions sous Windows et Unix.

INFA sur le sujet

Un article sur C ++ 11 random et quelques fonctionnalités de son utilisation: Génération de nombres aléatoires en C ++ moderne
Quels sont les générateurs en STL aléatoires? exilé
Article wiki sur XorShift avec différentes implémentations: tyk
Émulateur Git z26. Code aléatoire dans le fichier c_pitfall2.c: git
Générateur aléatoire Dumchik: git

PS Mon premier article. Écrivez ce qui est superflu, quoi ajouter / réduire

Algorithmes aléatoires