Pseudo-Zufalls-Generator in Assemblersprache

StackOverflow https://stackoverflow.com/questions/90184

  •  01-07-2019
  •  | 
  •  

Frage

Ich brauche einen Pseudo-Zufallszahlengenerator Algorithmus für ein Assembler-Programm in einem Kurs zugewiesen, und ich würde einen einfachen Algorithmus bevorzugen. Allerdings kann ich nicht eine externe Bibliothek.

Was ist ein guter, einfache Pseudo-Zufallszahlengenerator-Algorithmus für die Montag?

War es hilfreich?

Lösung

Einfach ist nur zwei große relative Primzahlen a und b zu wählen, dann halten Sie die Zufallszahl durch eine Multiplikation und das Hinzufügen von b. Verwenden Sie den Modulo-Operator die niedrigen Bits als Zufallszahl zu halten und den vollen Wert für die nächste Iteration zu halten.

Dieser Algorithmus bekannt als die Kongruenzgenerator .

Andere Tipps

Volume 2 von The Art of Computer Programming hat eine Menge Informationen über Pseudo-Zufallsgenerator . Die Algorithmen werden in Assembler gezeigt, so dass Sie selbst sehen können, die einfachste in Assembler sind.

Wenn Sie an einer externen Bibliothek oder Objektdatei verknüpfen können, aber das wäre die beste Wahl sein. Dann könnten Sie verlinken auf, zum Beispiel Mersenne Twister .

Beachten Sie, dass die meisten Pseudo-Zufallszahlengeneratoren sind nicht sicher für Kryptographie, wenn Sie also Erzeugung von Zufallszahlen benötigen zu sichern, müssen Sie über die grundlegenden Algorithmen suchen (und wahrscheinlich tippen sollte in OS-spezifischen Krypto-APIs ).

Einfacher Code für die Prüfung, nicht mit Crypto verwenden

Von Testing Software, Seite 138

Mit 32-Bit-Mathematik, Sie den Betrieb MOD 2^32 nicht brauchen 

RNG = (69069*RNG + 69069) MOD 2^32

Nun - Da ich keinen Hinweis auf die guten alten lineare Schieberegister gesehen habe poste ich einig SSE intrinsische Basis C-Kodex. Just for completenes. Ich schrieb ein paar Monaten das Ding vor wieder meine SSE-Fähigkeiten zu schärfen. 

#include <emmintrin.h>

static __m128i LFSR;

void InitRandom (int Seed)
{
  LFSR = _mm_cvtsi32_si128 (Seed);
}

int GetRandom (int NumBits)
{
  __m128i seed = LFSR;
  __m128i one  = _mm_cvtsi32_si128(1);
  __m128i mask; 
  int i;

  for (i=0; i<NumBits; i++)
  {

    // generate xor of adjecting bits
    __m128i temp = _mm_xor_si128(seed, _mm_srli_epi64(seed,1));

    // generate xor of feedback bits 5,6 and 62,61
    __m128i NewBit = _mm_xor_si128( _mm_srli_epi64(temp,5),
                                    _mm_srli_epi64(temp,61));

    // Mask out single bit: 
    NewBit = _mm_and_si128 (NewBit, one);

    // Shift & insert new result bit:
    seed = _mm_or_si128 (NewBit, _mm_add_epi64 (seed,seed));
  }

  // Write back seed...
  LFSR = seed;

  // generate mask of NumBit ones.
  mask = _mm_srli_epi64 (_mm_cmpeq_epi8(seed, seed), 64-NumBits);

  // return random number:
  return _mm_cvtsi128_si32 (_mm_and_si128(seed,mask));
}

Die Umsetzung dieser Code in Assembler ist trivial. Ersetzen Sie einfach die Spezifika mit den realen SSE-Befehlen und fügen Sie eine Schleife um ihn herum.

Btw - die Sequenz dieser Code genreates wiederholt nach 4.61169E + 18 Zahlen. Das ist viel mehr, als Sie über die Prime-Methode und 32-Bit-Arithmetik zu bekommen. Wenn entrollte es ist auch schneller.

@jjrv
Was Sie beschreiben, ist eigentlich ein linearer congrential Generator. Die Zufallsbits sind die höchsten Bits. Um eine Zahl von 0..N-1 kann man den vollen Wert von N multiplizieren (32 Bits von 32 Bits geben 64 Bits) und verwenden Sie die hohen 32 Bits.

 Sie sollten nur nicht beliebig viele nutzen für a (der Multiplikator für von einem vollen Wert zum nächsten voran), die in Knuth empfohlenen Zahlen (Tabelle 1 Abschnitt 3.3.4 TAOCP vol 2 1981) ist 1812433253 , 1566083941, 69069 und 1664525.

Sie können einfach jede ungerade Zahl für Pick b . (Der Zusatz).

Warum nicht eine externe Bibliothek verwenden ??? Das Rad ein paar hundert Mal erfunden wurde, also warum es wieder tun?

Wenn Sie ein RNG selbst implementieren müssen, brauchen Sie Zahlen auf Anfrage produzieren - das heißt implementieren Sie eine Funktion rand () - oder benötigen Sie Ströme von Zufallszahlen erzeugen - z.B. für Speichertests?

Sie benötigen einen RNG, die Krypto-Stärke ist? Wie lange muss es gehen, bevor sie wiederholt? Haben Sie unbedingt müssen, positiv gleichmäßige Verteilung aller Bits garantieren?

Hier ist einfach Hack, den ich vor einigen Jahren verwendet. Ich war in Embedded arbeiten, und ich brauchte RAM beim Einschalten bis zu testen, und ich wollte wirklich klein, schnell Code und sehr wenig Staat, und ich tat dies:

  • Starten Sie mit einer beliebigen 4-Byte-Konstante für Ihre Samen.
  • Berechnen Sie die 32-Bit-CRC dieser 4 Bytes. Das gibt Ihnen die nächsten 4 Bytes
  • diese 4 Bytes in den CRC-32-Algorithmus Feed-back, als ob sie angehängt worden waren. Die CRC32 dieses 8 Bytes ist der nächste Wert.
  • so lange wiederholen, wie Sie wollen.

Das dauert sehr wenig Code (auch wenn Sie eine Tabelle für die crc32 Funktion benötigen) und hat sehr wenig Zustand, aber der pseudozufällige Ausgangsstrom hat eine sehr lange Zykluszeit, bevor sie wiederholt. Auch ist es nicht SSE erfordern auf den Prozessor. Und vorausgesetzt, Sie die CRC-32-Funktion zur Hand haben, ist es trivial zu implementieren.

Mit masm615 zu Compiler: 

delay_function macro
    mov cx,0ffffh
.repeat
    push cx
    mov cx,0f00h
    .repeat
        dec  cx
        .until cx==0
    pop cx
    dec cx
    .until cx==0
endm

random_num macro
   mov  cx,64    ;assum we want to get 64 random numbers
   mov  si,0

get_num:    
   push cx
   delay_function    ;since cpu clock is fast,so we use delay_function
   mov  ah,2ch  
   int  21h
   mov  ax,dx     ;get clock 1/100 sec
   div  num       ;assume we want to get a number from 0~num-1
   mov  arry[si],ah   ;save to array you set
   inc  si
   pop  cx
   loop get_num   ;here we finish the get_random number

Auch können Sie wahrscheinlich emulieren Register mit XOR-Summe Elemente zwischen den einzelnen Bits Verschiebung, die Sie geben Pseudo-Zufallszahlenfolge.

Lineare Kongruenz (X = AX + C mod M) PRNG ist vielleicht ein guter sein für einen Assembler Kurs zuzuordnen, wie Sie Ihre Schüler mit Übertragsbits für Zwischen AX Ergebnisse zu beschäftigen haben mehr als 2 ^ 31 und einen Modul berechnet wird. Wenn Sie die Schüler sind, sind sie relativ einfach in Assembler zu implementieren und kann das sein, was der Vortragende im Sinn hatte.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top