Argumentabhängiges PRNG

Question

Ich interessiere mich für eine Funktion rand(x, y, seed) das basierend auf seinen Argumenten (Pseudo-) Zufallszahlen mit den folgenden Eigenschaften zurückgibt:

1. Der zurückgegebene Wert sollte von seinen 3 Argumenten abhängen und nicht abhängig von der Anzahl der Male rand wurde bisher genannt.Nehmen wir zum Beispiel diese Aufrufe in dieser Reihenfolge an:

   rand(0, 0, 123) = 1
   rand(0, 1, 123) = 2
   rand(0, 2, 123) = 3
   

   Dann anrufen rand mit den gleichen Argumenten, aber in einer anderen Reihenfolge, sollten wir die gleichen Werte erhalten.Beispielsweise:

   rand(0, 1, 123) = 2
   rand(0, 2, 123) = 3
   rand(0, 0, 123) = 1
   

2. Die Funktion sollte die üblichen Eigenschaften eines guten (anständigen, ich brauche eigentlich nichts Besonderes) PRNG haben:großer Zeitraum, gleichmäßige Verteilung usw.Die Rückgabe positiver Ganzzahlen, die in ein vorzeichenbehaftetes int passen, ist in Ordnung.Es kann auch höher gehen, wenn Sie wollen.

3. Angenommen, diese Zahlen werden zum Generieren einer Matrix verwendet.Dann sollte das Ändern des Seeds sicherstellen, dass die generierte Matrix so anders wie möglich aussieht als Matrizen, die von anderen Seeds generiert wurden.Dies sollte für eine möglichst große Anzahl von Samen geschehen:Ich möchte nicht, dass sich Matrizen wiederholen.

Wenn es hilft, sind meine Seeds immer der Unix-Zeitstempel in Millisekunden (kann auch in Sekunden sein, wenn das irgendwie einfacher ist).Alle Argumente können bis zu 32 Bit vorzeichenbehaftet sein, aber das Arbeiten mit 64-Bit-Werten innerhalb der Funktion ist kein Problem.

Welche Funktion könnte ich dafür verwenden?

Woran ich gedacht habe:

Perlinrauschen scheint einiges von dem zu tun, was ich will, aber ich habe keine Ahnung, wie geeignet es wirklich als PRNG ist, insbesondere in Bezug auf die Verteilung.Ich bin mir auch nicht sicher, wie effizient es ist, da mein (x, y) die Parameter sind ziemlich zufällig und ich kann sie nicht für alle vorberechnen.

Ich habe mir auch die folgende Funktion angesehen:

p = 1400328593
rand(x, y, seed) = (x * x * seed + y * seed * seed + seed * x * y + seed) mod p
                 = (seed * (x * x + y * seed + x * y + 1)) mod p

Dieser scheinen um ausreichend gute Zahlen zu generieren.Basierend auf meinen (sehr schwachen) Tests scheinen sie auch sehr gut verteilt zu sein.Das Testen der Periode ist jedoch schwieriger, das habe ich nicht getan.

Update:

Hier ist die Ausgabe von Hno für die obige Funktion mit time(NULL) in C als Startwert und Werte generiert für (x, y) in {0 ... 999} x {0 ... 999}:

Entropie = 3,312850 Bits pro Byte.

Eine optimale Komprimierung würde die Größe dieser 9207076-Byte-Datei um Folgendes reduzieren 58 Prozent.

Die Chi-Quadrat-Verteilung für 9207076 Stichproben beträgt 229710872,43 und zufällig würde dieser Wert weniger als 0,01 Prozent der Male überschritten.

Der arithmetische Mittelwert der Datenbytes beträgt 52,3354 (127,5 = zufällig).Monte Carlo-Wert für Pi ist 4,000000000 (Fehler 27,32 Prozent).Seriell der Korrelationskoeffizient beträgt 0,036131 (völlig unkorreliert = 0,0).

Ist das in der Praxis gut genug (theoretisch deuten die obigen Tests darauf hin, dass es überhaupt nicht gut ist), oder gibt es etwas Bekanntes, das ich verwenden sollte?

Answer 1

Es hört sich so an, als ob Sie eine Hash-Funktion wollen.Wählen Sie ein sicheres wie SHA1, wenn es nicht zu ineffizient ist, da es garantiert gute Verteilungseigenschaften aufweist;andernfalls können Sie eine gängige Hash-Funktion wie FNV verwenden.Verwenden Sie einfach Ihren Startwert und Ihre Koordinaten als Eingabedaten und den Hash als Zufallswert.

Answer 2

Sie könnten versuchen zu verwenden Blum Blum Shub.Es hat die Eigenschaft, dass Sie den n-ten Wert der Reihe direkt berechnen können, was für Ihre Situation angemessen erscheint.Es benötigt drei Parameter, p, q und x0.p und q sind prim und x0 ist relativ prim zu p und q.Ihre Argumente x und y könnten also verwendet werden, um die x-te und y-te Primzahl zu finden, dann wären sie für p und q geeignet, und dann könnten Sie Ihren dritten Parameter verwenden, um einen geeigneten Wert für x0 zu finden.Dies ist etwas mühsam und Blum Blum Shub ist langsam, da es sich um ein kryptografisches Zufallsgenerator handelt, aber wenn Sie nicht wirklich Geschwindigkeit benötigen, würde es funktionieren und wäre nicht besonders schwierig zu implementieren.

Eine andere Möglichkeit, dies zu tun, wäre, einen Zufallsgenerator wie zu nehmen CMWC und füllen Sie die i-te Position des Generators mit etwas wie x + y ^ i + seed ^ (2i), lassen Sie den Generator eine Weile laufen (möglicherweise eine Anzahl von Malen, die der Anzahl der gespeicherten Werte entspricht) und ziehen Sie dann einen Wert heraus daraus.

Wenn Sie ein CMWC verwenden möchten, können Sie sich eine Implementierung ansehen, die ich auf Github habe hier, und Werte für den Aufbau des Generators mit bekannten Perioden hier.