Get best of the week

Zufällige Algorithmen

In diesem Artikel sehen Sie die unterschiedlichsten Fahrradalgorithmen zum Generieren von Zufallszahlen.

Über welchen Artikel


Informationen zu Algorithmen, die Pseudozufallszahlen generieren, die sich in der Qualität des Ergebnisses und der Ausführungsgeschwindigkeit unterscheiden. Der Artikel ist nützlich für diejenigen, die eine leistungsstarke Zahlengenerierung in ihren Programmen erhalten möchten, oder für Entwickler von Software für Mikrocontroller und alte Plattformen wie ZX Spectrum oder MSX.

C ++ Rand


Das erste, was ein unerfahrener C ++ - Programmierer über das Erhalten eines zufälligen Hauses lernt, ist die Rand-Funktion, die eine Zufallszahl zwischen 0 und RAND_MAX generiert. Die RAND_MAX-Konstante ist in der Datei stdlib.h beschrieben und lautet 32'767. Dies ist beispielsweise unter Linux möglicherweise nicht der Fall ( siehe Kommentar ). Wenn rand () in Ihrem Compiler Zahlen innerhalb von 32'767 (0x7FFF) generiert und Sie eine Zufallszahl von großer Größe erhalten möchten, kann der folgende Code als Lösung für dieses Problem angesehen werden:

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


Die Implementierung der Rand-Funktion in altem C war einfach und sah folgendermaßen aus:

static unsigned long int next = 1;

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

Diese Implementierung hatte keine sehr gute Zahlenverteilung und ist jetzt in C ++ verbessert. Außerdem bietet die Standard-C ++ - Bibliothek zusätzliche Möglichkeiten zum Abrufen einer Zufallszahl, die im Folgenden erläutert werden.

C ++ 11 STL zufällig


Diese Art von Zufälligkeit trat in C ++ 11 auf und besteht aus den folgenden Klassen: minstd_rand, mt19937, ranlux, knuth_b und ihren verschiedenen Variationen.

Um zu verhindern, dass sich die Folge von Zufallszahlen bei jedem Programmstart wiederholt, wird die „Körnung“ des Pseudozufallsgenerators in Form der aktuellen Zeit oder bei einigen Retro-Spielen (und nicht nur) der Intervalle zwischen den Tastenanschlägen von Tastatur / Joystick eingestellt. Die Zufallsbibliothek schlägt vor, std :: random_device zu verwenden, um die Körnung besser als die Zeit (NULL) zu erhalten. Im Fall des MinGW-Compilers unter Windows funktioniert die Funktion jedoch praktisch nicht wie gewünscht. Bisher…

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

Einige der Algorithmen in STL random funktionieren möglicherweise schneller als rand (), ergeben jedoch eine Folge von Zufallszahlen mit geringerer Qualität.

PRNG - Pseudozufallszahlengenerator


Sie können diesen Namen als Synonym für die lineare kongruente Methode betrachten. PRNG-Algorithmen ähneln der Rand-Implementierung in C und unterscheiden sich nur in Konstanten.

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

PRNG-Algorithmen sind schnell und einfach in vielen Sprachen zu implementieren, haben jedoch keinen großen Zeitraum.

Xorshift


Der Algorithmus weist viele Variationen auf, die sich durch die Periode und die verwendeten Register voneinander unterscheiden. Details und Varianten von XorShift können auf Wikipedia oder Habré eingesehen werden. Ich werde eine der Optionen mit einer Folge von 2 im 128. Grad geben.

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

Dieser Generator ist insofern sehr gut, als es überhaupt keine Divisions- und Multiplikationsoperationen gibt - dies kann bei Prozessoren und Mikrocontrollern nützlich sein, bei denen es keine Assembler-Divisions- / Multiplikationsanweisungen gibt (PIC16, Z80, 6502).

8-Bit-Zufall im z26-Emulator


Z26 ist ein Emulator eines alten Atari2600-Präfixes, in dessen Code Sie zufällig orientierte Elemente finden, um mit 1-Byte-Registern zu arbeiten.

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

Einmal musste ich diesen Algorithmus für z80 implementieren:

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


Kompakter Zufall für Z80 von Joe Wingbermühle


Wenn Sie daran interessiert sind, Programme für Autos mit Zilog zu schreiben, dann stelle ich Ihnen einen Algorithmus von Joe Wingbermühle vor (funktioniert nur mit 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

Zufälliger Hausgenerator in DOOM


Im Quellcode des Spiels Doom gibt es eine so interessante Datei namens m_random.c (siehe Code) , die die Funktion der Zufälligkeit „Tabelle“ beschreibt, dh es gibt überhaupt keine Formeln und Magie mit Bitverschiebungen.

Ich werde einen kompakteren Code geben, der die Funktionsweise dieser Funktion deutlich zeigt.

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 für 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


Natürlich ist dies nicht zufällig und die Reihenfolge der Zufallszahlen ist selbst auf der Ebene der Intuition während des Spiels leicht vorherzusagen, aber alles funktioniert extrem schnell. Wenn die kryptografische Stärke für Sie nicht besonders wichtig ist und Sie etwas möchten, das schnell „Typ-Random“ generiert, ist diese Funktion genau das Richtige für Sie. Übrigens sieht in Quake3 zufällig einfach aus - rand () & 0x7FFF.

RDRAND


Einige moderne Prozessoren sind in der Lage, Zufallszahlen mit einem einzigen Assembler-Befehl - RDRAND - zu generieren. Um diese Funktion in C ++ zu verwenden, können Sie die erforderlichen Anweisungen manuell mit Assembler-Einfügungen schreiben oder die Datei immintrin.h in GCC verbinden und eine der Variationen der Funktion _rdrandXX_step auswählen, wobei XX die Anzahl der Bits im Register bedeutet und 16, 32 oder 64 sein kann.

#include <immintrin.h>

unsigned val;
_rdrand32_step(&val);

Wenn ein Kompilierungsfehler angezeigt wird, bedeutet dies, dass Sie das Flag -mrdrnd nicht aktiviert haben oder Ihr Compiler / Prozessor dieses Tool nicht unterstützt. Es ist vielleicht der schnellste Zufallszahlengenerator, aber es gibt Fragen zu seiner kryptografischen Stärke. Denken Sie also darüber nach.

Ende


Die std :: minstd_rand-Klasse aus der STL-Zufallsbibliothek arbeitet schneller als gewöhnliches rand () und kann zu einem alternativen Ersatz werden, wenn Sie sich nicht besonders Gedanken über die Länge des Zeitraums in minstd machen. Es kann Unterschiede in der Funktionsweise dieser Funktionen unter Windows und Unix geben.

Infa zum Thema


  • Ein Artikel über C ++ 11 random und einige Funktionen der Arbeit damit: Zufallszahlengenerierung in modernem C ++
  • Was sind die Generatoren in STL zufällig? Exil
  • Wiki-Artikel über XorShift mit verschiedenen Implementierungen: tyk
  • Git Emulator z26. Zufälliger Code in der Datei c_pitfall2.c: git
  • Dumchik Zufallsgenerator: git

PS Mein erster Artikel. Schreiben Sie, was überflüssig ist, was hinzugefügt / reduziert werden soll

More articles:


All Articles