Bitschubsen für Fortgeschrittene, Teil I

[Schrompf]

Grüße!

Ich brauche einen parallelen deterministischen Zufall - absurd turboschnell, nach Möglichkeit zustandsfrei, und halt z.B. 8x parallel.

Hintergrund: ich pflanze Grüne Voxel rund um Äste meines Baumgenerators. Bisher habe ich für jeden Voxel auf die geometrische Hülle geprüft und dann einen Zufall berechnet und gegen einen steigenden Grenzwert verglichen, damit das Blattwerk nach außen hin dünner wird. So sah das im Code aus:

Code: Alles auswählen

uint32_t noise = (nvp.x * 821 ^ nvp.y * 971 ^ nvp.z * 1031) % 137;
uint32_t refnoise = Funktion_In_Abhängigkeit_Vom_Abstand;
if( noise > refnoise )
  SetzeVoxel();

Der geneigte Leser entdeckt hier Krishtys geilen Instant-Zufall, der auch wirklich phantastisch funktioniert und absolut deterministisch einen optisch glaubwürdigen Zufall ausspuckt. Ich suche jetzt nach Ideen, wie ich einen uint64_t mit Zufallswerten füllen kann, so dass ich daran 8x parallel gegen einen Grenzwert vergleichen kann. Wie das Vergleichen gehen kann, habe ich schon rumliegen. Aber wie produziere ich einen deterministischen Zufall mit 64bit? Die Eingabe-Werte, also die Koordinaten, gehen üblicherweise von 0 bis 2047. Um 64Bit damit zu füllen, müsste ich also Primzahlen größer als 2^53 finden. Die kann man nicht mehr einfach so googeln.

Danke im Voraus!

[Biolunar]

Hey,

[…] deterministischen Zufall […] zustandsfrei […]

Das wird so nicht gehen ;) Also entweder, oder. In deinem Code hast du ja auch Zustand: x, y und z.

Du könntest mal die Generatoren von http://www.pcg-random.org/ ausprobieren. Angeblich erzeugen die sehr guten Zufall und sind sehr schnell, da es im Grunde nur LCGs sind.

[Spiele Programmierer]

Um schnell geeignete Primzahlen zu bekommen ist diese Seite ganz praktisch: https://asecuritysite.com/encryption/random3?val=64

Als Alternative könntest du die 3 Koordinaten erst zusammenbauen und dann gemeinsam durch einen Hash schicken.

Code: Alles auswählen

uint64_t seed = nvp.z ^ ((uint64_t)nvp.x << 40) ^ ((uint64_t)nvp.y << 20);
uint64_t randomValue = seed * 13454223343671262343; // Random prime

Wenn die Qualität davon nicht ausreicht, kannst du den zweiten Schritt auch mit etwas Besserem ersetzen.
Ein paar Vorschläge:
https://gist.github.com/badboy/6267743
http://burtleburtle.net/bob/hash/integer.html

[Schrompf]

Das wird so nicht gehen ;) Also entweder, oder. In deinem Code hast du ja auch Zustand: x, y und z.

Da kann man sich streiten, schätze ich. Es gibt keinen Zustand zwischen den einzelnen Instanzen des Zufalls, aber natürlich Eingabeparameter. Und so soll es auch bleiben. Wobei ein kleiner Zustand wahrscheinlich kein Drama wäre, da der ja deterministisch durchgetragen werden würde, wenn alles andere auch deterministisch ist.

Danke für den Link!

Um schnell geeignete Primzahlen zu bekommen ist diese Seite ganz praktisch: https://asecuritysite.com/encryption/random3?val=64

Sehr nützlich, vielen Dank!

Als Alternative könntest du die 3 Koordinaten erst zusammenbauen und dann gemeinsam durch einen Hash schicken.

Code: Alles auswählen

uint64_t seed = nvp.z ^ ((uint64_t)nvp.x << 40) ^ ((uint64_t)nvp.y << 20);
uint64_t randomValue = seed * 13454223343671262343; // Random prime

Wenn die Qualität davon nicht ausreicht, kannst du den zweiten Schritt auch mit etwas Besserem ersetzen.
Ein paar Vorschläge:
https://gist.github.com/badboy/6267743
http://burtleburtle.net/bob/hash/integer.html

Ja, hatte ich auch überlegt. Drei Parameter mal 10 bis 12 Bits reichen allein leider nicht, um 64bit zu füllen, aber wenn man die in den unteren ~20bit konzentriert und dann mit ner dicken Primzahl multipliziert, wie Du skizziert hast, sollte man ein gesundes Bitgewurschtel auf allen 64 Kanälen kriegen. Vielen Dank!

[smurfer]

Falls Dir Hash-Funktionen weiterhelfen, schau mal auf die Liste bei Wikipedia: https://en.wikipedia.org/wiki/List_of_h ... _functions
Sehr gut soll xxHash sein: https://github.com/Cyan4973/xxHash