🧙🏽 🙅🏽 🍖 Algoritmos Aleatorios 🕯️ 🍍 🛴

En este artículo, verá los algoritmos de ~~bicicleta~~ más diversos para generar números aleatorios.

Sobre qué artículo

Acerca de los algoritmos que generan números pseudoaleatorios que difieren en la calidad del resultado y la velocidad de ejecución. El artículo será útil para aquellos que desean obtener una generación de números de alto rendimiento en sus programas o desarrolladores de software para microcontroladores y plataformas antiguas como ZX Spectrum o MSX.

C ++ rand

Lo primero que un programador novato de C ++ aprende acerca de obtener una casa aleatoria es la función rand, que genera un número aleatorio entre 0 y RAND_MAX. La constante RAND_MAX se describe en el archivo stdlib.h y es 32'767, pero este puede no ser el caso, por ejemplo, en Linux ( ver comentario ). Si rand () en su compilador genera números dentro de 32'767 (0x7FFF) y desea obtener un número aleatorio de gran tamaño, entonces el siguiente código puede considerarse como una solución a este 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

La implementación de la función rand en la antigua C era simple y se veía así:

static unsigned long int next = 1;

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

Esta implementación no tenía una muy buena distribución de números y ahora está mejorada en C ++. Además, la biblioteca estándar de C ++ ofrece formas adicionales de obtener un número aleatorio, que se analizan a continuación.

C ++ 11 STL aleatorio

Esta variedad de aleatoriedad apareció en C ++ 11 y consiste en el siguiente conjunto de clases: minstd_rand, mt19937, ranlux, knuth_b y sus diversas variaciones.

Para evitar que la secuencia de números aleatorios se repita cada vez que se inicia el programa, el "grano" del generador pseudoaleatorio se configura en la forma de la hora actual o, en el caso de algunos juegos retro (y no solo), los intervalos entre las pulsaciones del teclado / joystick. La biblioteca aleatoria sugiere usar std :: random_device para obtener el grano mejor que el tiempo (NULL), sin embargo, en el caso del compilador MinGW en Windows, la función prácticamente no funciona como debería. Todavía…

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

Algunos de los algoritmos en STL random pueden funcionar más rápido que rand (), pero dan una secuencia de números aleatorios de menor calidad.

PRNG - Generador de números pseudoaleatorios

Puede considerar este nombre como sinónimo del método congruente lineal. Los algoritmos PRNG son similares a la implementación de rand en C y difieren solo en constantes.

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

Los algoritmos PRNG son rápidos y fáciles de implementar en muchos idiomas, pero no tienen un período extenso.

Xorshift

El algoritmo tiene muchas variaciones, que difieren entre sí por el período y los registros utilizados. Los detalles y variedades de XorShift se pueden ver en Wikipedia o Habré. Daré una de las opciones con una secuencia de 2 en el grado 128.

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 generador es muy bueno porque no hay operaciones de división y multiplicación en absoluto; esto puede ser útil en procesadores y microcontroladores en los que no hay instrucciones de división / multiplicación de ensamblador (PIC16, Z80, 6502).

8 bits al azar en el emulador z26

Z26 es un emulador de un antiguo prefijo Atari2600, en cuyo código puede encontrar uno aleatorio orientado a trabajar con 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;
}

Una vez que tuve que hacer una implementación de este algoritmo para z80:

Código de montaje

;    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

Compacto aleatorio para Z80 de Joe Wingbermuehle

Si está interesado en escribir programas para automóviles con zilog, le presento un algoritmo de Joe Wingbermuehle (solo funciona en 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 en DOOM

En el código fuente del juego Doom hay un archivo tan interesante llamado m_random.c (ver código) , que describe la función de la aleatoriedad de la "tabla", es decir, no hay fórmulas y magia con cambios de bits.

Daré un código más compacto que muestra claramente el funcionamiento de esta función.

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

Por supuesto, esto no es aleatorio y la secuencia de números aleatorios es fácil de predecir incluso a nivel de intuición durante el juego, pero todo funciona extremadamente rápido. Si la fuerza criptográfica no es particularmente importante para usted y desea algo que genere rápidamente "tipo aleatorio", entonces esta función es para usted. Por cierto, en Quake3, el aspecto aleatorio es simple: rand () y 0x7FFF.

RDRAND

Algunos procesadores modernos son capaces de generar números aleatorios con una sola instrucción de ensamblador: RDRAND. Para usar esta función en C ++, puede escribir manualmente las instrucciones necesarias con insertos de ensamblador o conectar el archivo immintrin.h en GCC y seleccionar cualquiera de las variaciones de la función _rdrandXX_step, donde XX significa el número de bits en el registro y puede ser 16, 32 o 64.

#include <immintrin.h>

unsigned val;
_rdrand32_step(&val);

Si ve un error de compilación, significa que no activó el indicador -mrdrnd o que su compilador / procesador no es compatible con esta herramienta. Puede ser el generador de números aleatorios más rápido, pero hay preguntas sobre su fuerza criptográfica, así que piénselo.

Finalizando

La clase std :: minstd_rand de la biblioteca aleatoria STL es más rápida que la rand ordinaria () y puede convertirse en un reemplazo alternativo si no está particularmente preocupado por la duración del período en minstd. Puede haber diferencias en cómo funcionan estas funciones en Windows y Unix.

Infa sobre el tema

Un artículo sobre C ++ 11 aleatorio y algunas características de trabajar con él: Generación de números aleatorios en C ++ moderno
¿Cuáles son los generadores en STL al azar? exilio
Artículo de Wiki sobre XorShift con diferentes implementaciones: tyk
Git emulator z26. Código aleatorio en el archivo c_pitfall2.c: git
Generador aleatorio Dumchik: git

PD Mi primer artículo. Escribe lo que es superfluo, qué agregar / reducir

Algoritmos Aleatorios