🌁 🤳🏿 🌮 Algoritmos Aleatórios ☄️ 👩🏿‍🤝‍👨🏼 🍐

Neste artigo, você verá os algoritmos de ~~bicicleta~~ mais diversos para gerar números aleatórios.

Sobre que artigo

Sobre algoritmos que geram números pseudo-aleatórios que diferem na qualidade do resultado e na velocidade de execução. O artigo será útil para quem deseja obter geração de números de alto desempenho em seus programas ou desenvolvedores de software para microcontroladores e plataformas antigas como ZX Spectrum ou MSX.

C ++ rand

A primeira coisa que um programador iniciante em C ++ aprende sobre como obter uma casa aleatória é a função rand, que gera um número aleatório entre 0 e RAND_MAX. A constante RAND_MAX é descrita no arquivo stdlib.h e é 32'767, mas isso pode não ser o caso, por exemplo, no Linux ( consulte o comentário ). Se rand () no seu compilador gerar números dentro de 32'767 (0x7FFF) e você desejar obter um número aleatório de tamanho grande, o código abaixo poderá ser considerado uma solução para esse problema:

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

A implementação da função rand no antigo C era simples e tinha a seguinte aparência:

static unsigned long int next = 1;

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

Essa implementação não teve uma distribuição muito boa de números e agora foi aprimorada em C ++. Além disso, a biblioteca C ++ padrão oferece maneiras adicionais de obter um número aleatório, discutidas abaixo.

C ++ 11 STL aleatório

Essa variedade de aleatoriedade apareceu no C ++ 11 e consiste no seguinte conjunto de classes: minstd_rand, mt19937, ranlux, knuth_b e suas diversas variações.

Para impedir que a sequência de números aleatórios se repita cada vez que o programa é iniciado, o "grão" do gerador pseudo-aleatório é definido na forma da hora atual ou, no caso de alguns jogos retrô (e não apenas), os intervalos entre as teclas do teclado / joystick. A biblioteca aleatória sugere o uso de std :: random_device para obter granulação melhor que o tempo (NULL), no entanto, no caso do compilador MinGW no Windows, a função praticamente não funciona como deveria. Ainda…

// ,   :
#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(); //

Alguns dos algoritmos no STL random podem funcionar mais rapidamente que rand (), mas fornecem uma sequência de números aleatórios de qualidade inferior.

PRNG - Gerador de números pseudo-aleatórios

Você pode considerar esse nome um sinônimo para o método congruente linear. Os algoritmos PRNG são semelhantes à implementação de rand em C e diferem apenas em constantes.

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

Os algoritmos PRNG são rápidos e fáceis de implementar em muitos idiomas, mas não têm um período grande.

Xorshift

O algoritmo possui muitas variações, que diferem entre si pelo período e pelos registros utilizados. Detalhes e variedades do XorShift podem ser vistos na Wikipedia ou Habré. Vou dar uma das opções com uma sequência de 2 no 128º grau.

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;
}

Este gerador é muito bom, pois não há operações de divisão e multiplicação - isso pode ser útil em processadores e microcontroladores nos quais não há instruções de divisão / multiplicação de montadores (PIC16, Z80, 6502).

Aleatório de 8 bits no emulador z26

O Z26 é um emulador de um prefixo Atari2600 antigo, no código do qual você pode encontrar um aleatório orientado para trabalhar com registros de 1 byte.

// 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;
}

Uma vez eu tive que fazer uma implementação desse algoritmo para z80:

Código de montagem

;    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

Aleatório compacto para Z80 de Joe Wingbermuehle

Se você está interessado em escrever programas para carros com zilog, apresento a você um algoritmo de Joe Wingbermuehle (funciona apenas no 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

Random House Generator em DOOM

No código-fonte do jogo Doom, existe um arquivo tão interessante chamado m_random.c (consulte o código) , que descreve a função da aleatoriedade da “tabela”, ou seja, não há fórmulas e mágicas com mudanças de bits.

Darei um código mais compacto que mostra claramente o funcionamento desta função.

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

Obviamente, isso não é aleatório e é fácil prever a sequência de números aleatórios, mesmo no nível de intuição durante o jogo, mas tudo funciona extremamente rapidamente. Se a força criptográfica não é particularmente importante para você e você deseja algo que gere rapidamente “tipo aleatório”, essa função é para você. A propósito, no Quake3, o aleatório parece simples - rand () e 0x7FFF.

RDRAND

Alguns processadores modernos são capazes de gerar números aleatórios com uma única instrução montadora - RDRAND. Para usar esta função no C ++, você pode escrever manualmente as instruções necessárias com inserções do assembler ou conectar o arquivo immintrin.h no GCC e selecionar qualquer uma das variações da função _rdrandXX_step, em que XX significa o número de bits no registro e pode ser 16, 32 ou 64.

#include <immintrin.h>

unsigned val;
_rdrand32_step(&val);

Se você vir um erro de compilação, significa que você não ativou o sinalizador -mrdrnd ou seu compilador / processador não suporta esta ferramenta. Pode ser o gerador de números aleatórios mais rápido, mas há perguntas sobre sua força criptográfica, então pense nisso.

Final

A classe std :: minstd_rand da biblioteca aleatória STL é mais rápida que a rand comum () e pode se tornar uma substituição alternativa se você não estiver particularmente preocupado com a duração do período no minstd. Pode haver diferenças na forma como essas funções funcionam no Windows e Unix.

Informação sobre o tema

Um artigo sobre C ++ 11 aleatório e alguns recursos para trabalhar com ele: Geração de número aleatório em C ++ moderno
Quais são os geradores aleatórios no STL? exílio
Artigo do Wiki sobre o XorShift com diferentes implementações: tyk
G26 emulador z26. Código aleatório no arquivo c_pitfall2.c: git
Gerador aleatório Dumchik: git

PS Meu primeiro artigo. Escreva o que é supérfluo, o que adicionar / reduzir

Algoritmos Aleatórios