Bitschubsen für Fortgeschrittene, Teil I

Design Patterns, Erklärungen zu Algorithmen, Optimierung, Softwarearchitektur
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.

Bitschubsen für Fortgeschrittene, Teil I

Beitragvon Schrompf » 13.10.2017, 23:32

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: Ansicht erweitern :: 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!
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.
Benutzeravatar
Schrompf
Thomas Ziegenhagen
Moderator
 
Beiträge: 3614
Registriert: 26.02.2009, 00:44
Wohnort: Dresden
Benutzertext: Lernt nur selten dazu

Re: Bitschubsen für Fortgeschrittene, Teil I

Beitragvon Biolunar » 14.10.2017, 00:58

Hey,

Schrompf hat geschrieben:[…] 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.
Biolunar
Establishment
 
Beiträge: 123
Registriert: 27.06.2005, 17:42
Alter Benutzername: dLoB

Re: Bitschubsen für Fortgeschrittene, Teil I

Beitragvon Spiele Programmierer » 14.10.2017, 02:09

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: Ansicht erweitern :: 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
Spiele Programmierer
Establishment
 
Beiträge: 341
Registriert: 23.01.2013, 16:55

Re: Bitschubsen für Fortgeschrittene, Teil I

Beitragvon Schrompf » 14.10.2017, 14:42

Biolunar hat geschrieben: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!

Spiele Programmierer hat geschrieben: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: Ansicht erweitern :: 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!
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.
Benutzeravatar
Schrompf
Thomas Ziegenhagen
Moderator
 
Beiträge: 3614
Registriert: 26.02.2009, 00:44
Wohnort: Dresden
Benutzertext: Lernt nur selten dazu

Re: Bitschubsen für Fortgeschrittene, Teil I

Beitragvon smurfer » 14.10.2017, 20:42

Falls Dir Hash-Funktionen weiterhelfen, schau mal auf die Liste bei Wikipedia: https://en.wikipedia.org/wiki/List_of_hash_functions#Non-cryptographic_hash_functions
Sehr gut soll xxHash sein: https://github.com/Cyan4973/xxHash
smurfer
 
Beiträge: 57
Registriert: 25.02.2002, 15:55


Zurück zu Algorithmen und Datenstrukturen

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 2 Gäste