Es gibt einige neue 64 Bit Zufallszahlengeneratoren, und die Autoren beflegeln sich so fleissig, das sie hier bei uC auftreten könnten. Siehe z.B: Vigna https://prng.di.unimi.it/ und Neil https://www.pcg-random.org/ https://pcg.di.unimi.it/pcg.php Jeder behauptet, seiner ist der beste. Wo sich alle einig sind, ist dass die klassischen libc Generatoren Schrott sind. Die statistischen Testprogramme TestU01 und PractRand laufen auch alle brav durch. Trotzdem bin ich skeptisch. Ich habe schnell aus den Werten dreier Generatoren (Java 8 splitmix, xoroshiro128plusplus und MSVC rand) je drei Bilder mit unterschiedlichem seed Wert erzeugt (x=rand(), y=rand(), red=rand(), green=rand(), blue=rand()). Ich war dann doch überrascht, das die Bilder nicht gleich ausschauen, und so stark vom Seed abhängen. Zufallszahlen sind schliesslich nur Zufallszahlen, oder? Eigentlich möchte ich gerne einen "Spektral Test" machen, bei dem RANDU völlig versagt, aber ich habe auf die schnelle keien SW dafür gefunden... Hat hier jemand Erfahrung mit Zufallszahlengeneratoren, insbesondere für Monte Carlo Simulationen? Was kann man da wirklich nehmen, und wie kann man sicherstellen, dass die einzelnen Durchläufe statistisch unabhängig sind?
Da alle drei Generatoren bei deinen drei unterschiedlichen Seeds das gleiche Verhalten zeigen (seed 0 = mittlere Dichte, seed 1234 = hell, seed dead = dunkel), vermute ich einen systematischen Fehler in deinem Testprogramm.
Ich glaube nicht daß man mit dem von dir beschriebenen Verfahren die Qualität der PRNG beurteilen kann. Per se ist "echter Zufall" per Algorithmus nicht möglich. Und das nacheinander Aufrufen von rand() für x, y, r, g, b liefert auch keine Anhaltspunkte für die Qualität der PRNG.
Hallo udok, udok schrieb: > Hat hier jemand Erfahrung mit Zufallszahlengeneratoren, insbesondere > für Monte Carlo Simulationen? Deine Frage ist zu unspezifisch gestellt. Genauso könnte man fragen: Welche Hash-Funktion ist die beste? Die Frage ist doch, zu welchem Zweck Du einen Zufallszahlengenerator einsetzen willst. Monte Carlo wird erst bei mehreren korrelierten Zufallszahlen spannend.
Die Foren-SW hat die angehängten Bilder leider ziemlich komprimiert, und die "Feinstruktur" ist damit verschwunden. Wenn ich mir die originalen Bilder in 1000x800 anschaue, kommt mir vor, dass da eine "Struktur" drinnen ist, aber wenn ich noch mal draufschaue, schaut es schon wieder anders aus... ist wahrscheinlich eine Täuschung. Bis auf die Bilder von der standard rand() Funktion. Die erzeugt ja nur 16 Bits, und ich habe RGB aus den ersten drei Bytes genommen. Daher der etwas orange Ton, die neuere Version nimmt drei separate Zufallszahlen, damit sind die Bilder im Prinzip sehr ähnlich, und lassen sich auch nicht mit 7z oder zip komprimieren.
Hans H. schrieb: > Ich glaube nicht daß man mit dem von dir beschriebenen Verfahren > die Qualität der PRNG beurteilen kann. > Per se ist "echter Zufall" per Algorithmus nicht möglich. Und das > nacheinander Aufrufen von rand() für x, y, r, g, b liefert auch keine > Anhaltspunkte für die Qualität der PRNG. Natürlich kannst du das. Aber ausschließlich in Richtung von: NICHT Random. Sobald du klare Muster siehst, ist es Mist. Und glaub mir, das reicht oftmals schon aus.
foobar schrieb: > Da alle drei Generatoren bei deinen drei unterschiedlichen Seeds das > gleiche Verhalten zeigen (seed 0 = mittlere Dichte, seed 1234 = hell, > seed dead = dunkel), vermute ich einen systematischen Fehler in deinem > Testprogramm. Und ja, da war wirklich noch ein Bug drinnen :-) Im Prinzip schauen die Bilder jetzt alle sehr ähnlich aus, bis auf die "Feinstruktur", wo aber wahrscheinlich der Kopf was reinzeichnet. Ist ähnlich, wie eine Landschaft im Nebel, von oben mit ganz leichten Andeutungen von irgendwas... Für heute aber genug, ich wünsche euch ein schönes Wochenende! Udo
Peter M. schrieb: > Deine Frage ist zu unspezifisch gestellt. > Genauso könnte man fragen: Welche Hash-Funktion ist die beste? > > Die Frage ist doch, zu welchem Zweck Du einen Zufallszahlengenerator > einsetzen willst. > Monte Carlo wird erst bei mehreren korrelierten Zufallszahlen spannend. Ok, da muss ich selber noch mal drüber nachdenken. Kennst du da brauchbare Literatur? Aber wegen dem Hash: Wenigstens da habe ich inzwischen eine Meinung :-) CRC32C mit Intel Hardware Unterstützung. Das ist nicht die Ethernet CRC32, wobei die auch sehr gut funktioniert, nur ist die SW CRC32 nicht sehr schnell. Die CRC32C ist in meinen Tests praktisch immer schneller oder zumindest gleichschnell wie alle getesteten Alternativen, und die Anzahl der Kollisionen ist sehr gering. Es ist auch ziemlich egal, ob man Strings, Binärdaten, Daten mit gleichem Prefix oder Suffix, oder Zufallsdaten hasht, sie funktioniert praktisch immer gut (was laut meinen Tests nur für einen Handvoll von Hash-Funktionen zutrifft). Wer Zeit hat, kann sie ja mal testen (und berichten):
1 | /*
|
2 | * Intel CRC32C Hash Function (88 Bytes)
|
3 | * ------------------------------------------------------------------------
|
4 | * One of the fastest general purpose hash functions with low collisions.
|
5 | * This computes the CRC-32C with the reflected Polynomial 0x11EDC6F41, and
|
6 | * not the CRC-32 used by Ethernet and zip.
|
7 | * Uses the Intel SSE 4.2 crc32 asm instruction.
|
8 | * Compile with cl -nologo -W3 -O2 -Ob1 -Oi -GS- -c hashtbl.c
|
9 | * Note that clang-cl needs the -arch:AVX2 flags and that
|
10 | * clang -O2 does automatic loop unrolling with unnecessary code bloat
|
11 | * (better with -O1).
|
12 | */
|
13 | UINT Hash_CRC32C_HW64(PCCH key, SIZE_T len) |
14 | {
|
15 | UINT crc = -1; |
16 | SIZE_T n = len / 8; |
17 | |
18 | if (n) { |
19 | UINT64 crc64 = crc; |
20 | do { |
21 | crc64 = _mm_crc32_u64(crc64, *(UINT64*)key); |
22 | key += 8; |
23 | } while (--n); |
24 | crc = (UINT)crc64; |
25 | }
|
26 | |
27 | if (len & 4) { |
28 | crc = _mm_crc32_u32(crc, *(DWORD*)key); |
29 | key += 4; |
30 | }
|
31 | |
32 | if (len & 2) { |
33 | crc = _mm_crc32_u16(crc, *(WORD*)key); |
34 | key += 2; |
35 | }
|
36 | |
37 | if (len & 1) |
38 | crc = _mm_crc32_u8(crc, *(BYTE*)key); |
39 | |
40 | return crc; |
41 | }
|
udok schrieb: > Aber wegen dem Hash: > Wenigstens da habe ich inzwischen eine Meinung :-) > CRC32C mit Intel Hardware Unterstützung. Lol. Get pwned. Leute, baut bitte keine crypto ohne das nötige Verständnis.
meckerziege schrieb: > udok schrieb: > >> Aber wegen dem Hash: >> Wenigstens da habe ich inzwischen eine Meinung :-) >> CRC32C mit Intel Hardware Unterstützung. > > Lol. Get pwned. > Leute, baut bitte keine crypto ohne das nötige Verständnis. Es gibt aber auch nicht nur in Crypto-Bereich hashes. CRC sieht eher nach Fehlererkennung oder Korrektur aus.
Ich verweise auf die Rauschbilder aus der KI Mustererkennung. Wo die KI Muster im Rauschen erkennen kann, die für das menschliche Auge völlig unkenntlich ist. Man kann solche Verfahren bestimmt auch dazu nutzen um automatisiert mögliche Muster in zufälligen Daten zu erkennen. Die Selbstorganisierenden Netze sollten solche Muster extrahieren können.
udok schrieb: > Die CRC32C ist in meinen Tests praktisch immer schneller oder zumindest > gleichschnell wie alle getesteten Alternativen, Hast du ChaCha8 getestet? Das ist rasend schnell, gut verteilt und auch relativ sicher (cryptographisch. Natürlich nicht so sicher wie ChaCha20.)
Ich habe die Bilder jetzt als PNG hochgeladen, in der Hoffnung, dass sie die Foren SW so besser überleben. Zu sehen ist das LSB. Ich kann zumindest die MSVC rand() Funktion ziemlich sicher erkennen.
Mist, die Foren SW hat sie auch wieder komprimiert. Aber ein bischen sieht man es noch: die MSVC rand() Bilder haben schräge Streifen. Aber jetzt wirklich gute Nacht.
MaWin schrieb: > Hast du ChaCha8 getestet? > Das ist rasend schnell, gut verteilt und auch relativ sicher > (cryptographisch. Natürlich nicht so sicher wie ChaCha20.) Habe ich nicht getestet. Danke für den Tipp. Ich brauche die Hash Funktion aber nicht für cryptographische Zwecke, sondern für eine normale Hash Tabelle zum suchen. Was da auch noch sehr gut war, ist Murmur2, FNV1 (aber langsam bei langen Strings), SBox (aber 1 kByte Tabelle), und die Hash Funktion von Paul Hsieh.
Wenn es eine Windows Kiste ist kannst du auch mal "CryptGenRandom" probieren. Ggf. kann man das auch erstmal benutzen um den "salt" zu erzeugen. - https://docs.microsoft.com/en-us/windows/win32/api/wincrypt/nf-wincrypt-cryptgenrandom Für Hash gibt es auch noch eine paar Extra Funktionen (habe ich aber noch nie verwendet): - https://docs.microsoft.com/en-us/windows/win32/api/wincrypt/nf-wincrypt-cryptgethashparam - https://docs.microsoft.com/en-us/windows/win32/api/wincrypt/nf-wincrypt-crypthashdata Seit c++11 gibt es auch noch "std::random_device", damit werden einige Mängel der früheren Varianten verbessert. - https://en.cppreference.com/w/cpp/numeric/random/random_device
udok schrieb: > Ich kann zumindest die MSVC rand() Funktion ziemlich sicher erkennen. Ja, die hat Strukturen. Ist ja auch kein Wunder, die rand()-Funktion hat keinerlei Garantien über die erzeugten Zufallszahlen. Der Rest ist doch alles in Ordnung. Die kannst Du nicht unterscheiden. Wenn Du glaubst, Muster zu sehen, ändere doch Dein Programm so, dass es Bilder mit zufälligen Namen erzeugt (in zufälliger Reihenfolge), und die Zuordnung in einer separaten Datei speichert. Lass Dir ein paar Dutzend Bilder erzeugen, und versuch sie zu sortieren anhand vermeintlicher Muster. Danach erst schaust Du, welches Bild welche Parameter hatte. Du musst einen Doppel-Blind-Test machen. Ansonsten bescheisst Dich Dein Unterbewusstsein.
udok schrieb: > kommt mir vor, dass da eine "Struktur" drinnen ist Oje, nicht schon wieder die verborgene Variable. Drogenwechsel?
Die 90er haben angerufen und wollen ihre Magisches Auge-Bücher wieder zurückhaben. Im ersten Bild sehe ich ganz klar einen riesigen Schwengel.
meckerziege schrieb: > Leute, baut bitte keine crypto ohne das nötige Verständnis. Für nicht-crypto eignet sich CRC32 speziell für embedded gut als Hashfunktion. Ab 2^16 Elementen hat man allerdings wegen des Geburtstagsparadoxons eine Kollisionswahrscheinlichkeit von satten 50%.
Wann sind Zahlen wirklich zufällig: Dazu gibt es Methoden das zu analysieren. Optisch ist natürlich ein Ansatz, eine KI auf Mustererkennung würde ich definitiv nicht loslassen. Die sieht ja auch nur das auf was es trainiert wurde. Aber mal Meister Google benutzen nach Stichworten wie: "analysis of random number" Ergebnis: https://www.random.org/analysis/ http://www.cacert.at/cgi-bin/rngresults uvm. Wenn der TO Programme zur verifizierung hat, darf er die dann gerne hier bereitstellen.
Es gibt 2 Varianten von Zufallsgeneratoren, die interessant sind: 1) Pseudozufällige. Man hat eine seed zahl, die die Zufallssequenz fest legt. Gut in Situationen, wo man etwas später nachvollziehen / reproduzieren können will. 2) "Echte" Zufallsgeneratoren. Für wenn etwas nicht reproduzierbar sein darf. Auf unixoiden Systemen liest man dafür besten einfach von /dev/urandom, alles andere ist murks.
DPA schrieb: > Es gibt 2 Varianten von Zufallsgeneratoren, die interessant sind: Man kann die auch mischen. Auf einem Mikrocontroller beispielsweise ein LFSR, in dessen Zustand man ein wenig ADC-Rauschen zur Laufzeit (also nicht nur beim Seed) einbringt.
bashooka schrieb: > Die 90er haben angerufen und wollen ihre Magisches Auge-Bücher > wieder zurückhaben. > Im ersten Bild sehe ich ganz klar einen riesigen Schwengel. Wirst schon drauf stehen :-D
Und hier der obligatorische Dilbert: https://dilbert.com/strip/2001-10-25 Alles Gute, alles Liebe (-:
Gustl B. schrieb: > Und hier der obligatorische Dilbert: > https://dilbert.com/strip/2001-10-25 > > Alles Gute, alles Liebe (-: Bist schon der zweite (-:
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.