Forum: PC-Programmierung Kennt sich hier jemand mit Zufallszahlen aus?


You were forwarded to this site from EmbDev.net. Back to EmbDev.net
von udok (Gast)



Lesenswert?

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?

von foobar (Gast)


Lesenswert?

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.

von Hans H. (loetkolben)


Lesenswert?

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.

von Peter M. (r2d3)


Lesenswert?

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.

von udok (Gast)


Lesenswert?

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.

von meckerziege (Gast)


Lesenswert?

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.

von udok (Gast)


Lesenswert?

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

von udok (Gast)


Lesenswert?

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
}

von meckerziege (Gast)


Lesenswert?

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.

von jemand (Gast)


Lesenswert?

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.

von KIUser (Gast)


Lesenswert?

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.

von MaWin (Gast)


Lesenswert?

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.)

von udok (Gast)



Lesenswert?

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.

von udok (Gast)


Lesenswert?

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.

von udok (Gast)


Lesenswert?

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.

von Irgend W. (Firma: egal) (irgendwer)


Lesenswert?

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

von Einer (Gast)


Lesenswert?

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.

von Spatzkanone (Gast)


Lesenswert?

udok schrieb:
> kommt mir vor, dass da eine "Struktur" drinnen ist

Oje, nicht schon wieder die verborgene Variable.

Drogenwechsel?

von bashooka (Gast)


Lesenswert?

Die 90er haben angerufen und wollen ihre Magisches Auge-Bücher wieder 
zurückhaben.

Im ersten Bild sehe ich ganz klar einen riesigen Schwengel.

von Nop (Gast)


Lesenswert?

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%.

von tja (Gast)


Lesenswert?

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.

von DPA (Gast)


Lesenswert?

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.

von MaWin (Gast)


Lesenswert?


von Nop (Gast)


Lesenswert?

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.

von MaWin (Gast)


Lesenswert?

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

von Gustl B. (-gb-)


Lesenswert?

Und hier der obligatorische Dilbert:
https://dilbert.com/strip/2001-10-25

Alles Gute, alles Liebe (-:

von Lok (Gast)


Lesenswert?

42

von udok (Gast)


Lesenswert?

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
Noch kein Account? Hier anmelden.