ist dort als zufällig zugänglich Pseudo-Zufallszahlengenerator so etwas? (Vorzugsweise Open-Source)

https://stackoverflow.com/questions/3019169

26-09-2019
|

Frage

Zunächst einmal ist es so etwas wie ein Direktzugriffszufallszahlengenerator, wo man konnte nicht nur sequentiell Zufallszahl erzeugen, wie wir alle gewohnt sind, unter der Annahme, rand100 () immer ein Wert von 0 bis 100 erzeugt:

for (int i=0;i<5;i++)
   print rand100()

output: 
14
75
36
22
67

, sondern auch Zugriff auf zufällig einen beliebigen Wert wie:

rand100 (0) Would Ausgang 14, solange Sie den Samen nicht ändern

rand100 (3) würde immer Ausgang 22

rand100 (4) würde immer Ausgang 67

und so weiter ...

Ich habe festgestellt, eigentlich einen Open-Source-Generator-Algorithmus, der dies tut, aber man kann nicht den Samen ändern. Ich weiß, dass Pseudozufälligkeit ein komplexes Feld ist; Ich würde nicht wissen, wie es zu ändern, dass die Funktionalität hinzuzufügen.

Gibt es einen seedable random access Zufallszahlengenerator, vorzugsweise Open Source? oder gibt es einen besseren Begriff dafür kann ich für weitere Informationen google?

Wenn nicht, Teil 2 meiner Frage wäre, gibt es einen zuverlässig zufälligen Open-Source herkömmlichen seedable Pseudo-Zufallszahlengenerator so konnte ich Portierung auf mehrere Plattformen / Sprachen, während eine konsistente Folge von Werten für jede Plattform für einen bestimmten Samen Halt ?

Lösung

Die PCG Familie von Pseudozufallszahlengeneratoren springen kann vorwärts und rückwärts in logarithmischer Zeit (dh springen nach vorn 1000 Nummern erfordert O (log (1000)) Operationen), die wahrscheinlich gut genug ist, mit wahlfreiem Zugriff zu betrachten. Die Referenz C und C ++ Implementierungen sowohl diese Funktion unterstützen.

Die Tabelle auf der Titelseite der PCG-Website zeigt an, dass eine Reihe von anderen Generatoren Sprung-ahead unterstützen kann, aber ich habe es nicht in allen Implementierungen gesehen.

Andere Tipps

Ich habe nicht von so etwas gehört, aber es scheint mir, Sie eine anständige Hash verwenden nehmen und eine Wrapper-Funktion schreiben, die einen Startwert und Ihren ‚Index‘ nimmt und führt sie durch die Hash-Funktion. Ich bin mir nicht sicher, ob der Zufälligkeit der ausgegebenen Bits durch verschiedene kryptographische Hash-Funktionen, aber ich glaube, dass jemand einen Blick auf das genommen hat.

Blum Blum Shub ist ein Pseudo-Zufallszahlengenerator mit einem Samen und Direktzugriff auf einen beliebigen Wert es erzeugt.

Danke für alle Antworten, und auch, für jeden, der auf diese fragen, eine ähnliche Frage passieren könnte, fand ich eine Lösung, die nicht genau das, was ich gefragt, sondern passt die Rechnung für meine Zwecke.

Es ist ein Perlin Noise Klasse, die hier . Ich bin mir nicht sicher, wie rechnerisch komplex dies zu einem herkömmlichen Zufallszahlengenerator relativ ist, was wichtig ist, da eine der geplanten Plattformen Android. Auch ist Perlin Noise nicht das Gleiche wie Pseudozufälligkeit, aber von dem, was ich sagen kann, eine hohe Oktave und / oder Frequenzwert sollte geeignete Zufälligkeit für Nicht-Verschlüsselungs Zwecke zur Verfügung stellen, in denen das statistische Maß an echte Zufälligkeit ist nicht so wichtig als bloße Erscheinung des Zufalls.

Diese Lösung ermöglicht Säen und ermöglicht auch einen zufälligen Satz von jedem Punkt Abtasten, mit anderen Worten, ein Direktzugriffs Zufälligkeit.

hier ist ein Beispiel Reihe von regelmäßigen c ++ Zufälligkeit (rand% 200) in der linken Spalte für den Vergleich und Perlin Noise (mit dem Äquivalent von% 200) auf der rechten Seite:

wurden beide ausgesät auf 0

die Parameter für die Perlin Noise waren

octaves = 8
amplitude = 100 
frequency = 9999
width/height = 10000,100

die sequentielle Abtastung, um für den perlin Lärm war einfach

for (int i=0;i<24;i++)
    floor(Get(i,i)+100);
//amplitude 100 generates noise between -100 and 100, 
//so adding 100 generates between 0 and 200

Wenn ich von einem Mann eine wirklich gute Blog-Post zu lesen, die auf der Arbeit bei Google verwendet, die eine Frage sehr ähnlich wie bei Ihnen beantwortet.

Kurz gesagt, war die Antwort ein Blockchiffre mit einer Zufallszahl als Verschlüsselungsschlüssel zu verwenden, und dem Index der Nummer, die Sie in der Reihenfolge mögen, da die Daten verschlüsselt werden. Er erwähnte eine Chiffre, die auf Blöcke jeder Größe (in Bit) arbeiten können, was sehr praktisch ist - ich muss für das Blog suchen würde den Namen der Chiffre zu finden

Zum Beispiel: Angenommen, Sie eine zufällige Schlurfen von ganzen Zahlen von 0 bis (2 ^ 32) -1 wollen. Sie kann erreicht werden, dass eine Blockchiffre, die unter Verwendung von 4 Byte Eingabe nimmt, und kehrt 4 Bytes verschlüsselt. Iterieren der Serie, erster „encrypt“ ein Block von Wert 0, dann 1, dann 2, usw. Wenn Sie nur das 1000000. Element in der Shuffled Sequenz mögen, können Sie verschlüsseln nur die Nummer 1000000.

Die „Zufallsfolgen“ Sie werden eine Chiffre erhalten verwenden, sind anders, als würden Sie eine Hash-Funktion erhalten unter Verwendung von (als @MichaelBurr vorgeschlagen). Unter Verwendung einer Chiffre, können Sie eine zufällige Permutation von einer Reihe von ganzen Zahlen erhalten, und in dieser Permutation in konstanter Zeit ein beliebiges Element kosten. Mit anderen Worten, wiederholen sich die „Zufallszahlen“ nicht. Wenn Sie eine Hash-Funktion zu verwenden, können die Zahlen in der Reihenfolge wiederholen.

Nachdem ich das alles gesagt, @ MichaelBurr-Lösung besser geeignet für Ihre Situation ist, und ich würde Ihnen empfehlen, es zu benutzen.

Eine Möglichkeit, dies zu erreichen, ist eine größere Menge an Zufallsdaten von einem kleineren Satz zu synthetisieren. Eine Möglichkeit, dies zu tun ist, drei Arrays von zuvor erzeugten Zufallsdaten haben. Jedes Array sollte Primzahl von entires hat.

Um unsere Zufallszahlen produzieren wir jedes dieser einmaligen Pads vorstellen inifintely und abgetastet schrittweise geschleift werden; kombinieren wir die Daten in jedem von ihnen xor verwendet wird.

#define PRIME1 7001
#define PRIME2 7013
#define PRIME3 7019

static int pad1[PRIME1];
static int pad2[PRIME2];
static int pad3[PRIME3];

static void random_no_init (void)
{
  static int initialized = 0;
  int i;
  if (initialized)
    return;
  for (i = 0; i < PRIME1; i++) pad1[i] = random ();
  for (i = 0; i < PRIME2; i++) pad2[i] = random ();
  for (i = 0; i < PRIME3; i++) pad3[i] = random ();

  initialized = 1;
}

int random_no (int no)
{
   random_no_init ();
   return pad1[no % PRIME1] ^ pad2[no % PRIME2] ^ pad3[no % PRIME3];
}

Das obige Codebeispiel zeigt ein einfaches Beispiel, dass die Renditen 344618953247 zufällig zugänglich entires. Um reproduzierbare Ergebnisse zwischen den Läufen zu gewährleisten, sollten Sie einen Zufallszahlengenerator mit einem Samen liefern. Ein komplexeres System auf dem gleichen Prinzip mit Saatgut Variation Kommissionierung verschiedenen Primzahlen basiert gebaut kann unter http://git.gnome.org/browse/gegl/tree/gegl/gegl-random.c

Alle Generatoren Ich bin mir dessen bewusst sind iterativ. Also, jeder ‚random access‘ bedeuten würde alle die Werte aus der ersten in die für Sie fragen zu berechnen.

Die nächstgelegene Sie kommen könnte, ist eine feste Samen zu nehmen, Hash, und dann den Indexwert hash, mit etwas, das mischt wirklich begeistert.

erzeugen oder eine lange Liste von ihnen und speichern.

einen Blick auf dieses Patent: Random-Access psuedo Zufallszahlengenerator https://patents.google.com/patent/US4791594

Es verwendet ein mehrstufiges Bit Scrambling Schema eine Anzahl Pseudo-Sequenz zu erzeugen, die der Lage ist, wahlfrei zugegriffen werden.

Die Idee ist, die Eingabe-Adresse als Steuerbits zu verwürfeln mehr Samen Zahlen zu verwenden, und dann die Ergebnisse XOR eine Ausgabe zu erzeugen, dann einen zweiten Durchlauf der Verwürfelung des Ergebnis aus dem vorherigen Durchlauf erzeugt.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow