Kennt sich hier jemand mit Zufallszahlen aus?

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.

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.

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.

https://linux.die.net/man/1/dieharder

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

42

Gustl B. schrieb:
> Und hier der obligatorische Dilbert:
> https://dilbert.com/strip/2001-10-25
>
> Alles Gute, alles Liebe (-:

Bist schon der zweite (-: