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.
Antworten
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Bitschubsen für Fortgeschrittene, Teil I

Beitrag von 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!
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Biolunar
Establishment
Beiträge: 154
Registriert: 27.06.2005, 17:42
Alter Benutzername: dLoB

Re: Bitschubsen für Fortgeschrittene, Teil I

Beitrag von Biolunar »

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.
Spiele Programmierer
Establishment
Beiträge: 426
Registriert: 23.01.2013, 15:55

Re: Bitschubsen für Fortgeschrittene, Teil I

Beitrag von 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
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: Bitschubsen für Fortgeschrittene, Teil I

Beitrag von Schrompf »

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: 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!
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
smurfer
Establishment
Beiträge: 195
Registriert: 25.02.2002, 14:55

Re: Bitschubsen für Fortgeschrittene, Teil I

Beitrag von 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
Antworten