Vlákno názorů k článku ENT - Program pro testování sekvencí pseudonáhodných čísel od abyssal - Skusal som to na Linuxe (2.4.18, glibc 2.3.4)...

Skusal som to na Linuxe (2.4.18, glibc 2.3.4) aj na pod Cygwinom a vsade som dostal uplne iny vysledok ako je popisovany v clanku (oba testy 500000 resp 500001 bytov):

-pod Linuxom (500000 krat rand()%256, niektore implementacie rand() maju dolne bity menej nahodne, ale podla manualu v zmienenej glibc by to malo vyjst rovnako ked sa beru horne a dolne bity):
Entropy = 7.999610 bits per byte.

Optimum compression would reduce the size
of this 500000 byte file by 0 percent.

Chi square distribution for 500000 samples is 270.02, and randomly
would exceed this value 25.00 percent of the times.

Arithmetic mean value of data bytes is 127.4948 (127.5 = random).
Monte Carlo value for Pi is 3.134604538 (error 0.22 percent).
Serial correlation coefficient is -0.000333 (totally uncorrelated = 0.0).

-pod Cygwin (500001 krat perlom print pack("C", int(rand()*256))):
Entropy = 7.999630 bits per byte.

Optimum compression would reduce the size
of this 500001 byte file by 0 percent.

Chi square distribution for 500001 samples is 256.14, and randomly
would exceed this value 50.00 percent of the times.

Arithmetic mean value of data bytes is 127.5045 (127.5 = random).
Monte Carlo value for Pi is 3.137628551 (error 0.13 percent).
Serial correlation coefficient is -0.000694 (totally uncorrelated = 0.0).

Pokial viem, implementacia rand() je linearny kongruencny generator (LCG). V pravdepodobnosti a statistike som sice celkom lavy, ale ak sa dobre pamatam, tak hodnoty vygenerovane LCG sa rozdelenim blizia uniformnemu rozdeleniu a v tomto zmysle by mali mat celkom dobre statisticke vlastnosti, v skutocnosti jediny problem LCG je, ze su z niekolkych hodnot predikovatelne, teda nie su vhodne ako kryptograficke RNG.

Stala sa teda niekedy zasadna zmena implementacie rand() v glibc alebo preco som dostal ine vysledky?

Pozn. pre autora: mozno by sa hodilo este zmienit diehard testy, celkom by ma zaujimal nejaky podrobnejsi popis...

Linearni kongruencni generator je dost primitivni a dobre statisticke vlastnosti nema. Glibc pouziva jiny algoritmus (viz man rand, man random).

Viem, ze LCG je uplne primitivny. V Googli som nasiel, ze ANSI C rand() je LCG. Pozrel som sa podrobnejsie do manualu random, ale neviem nikde najst co je to "additive feedback random number generator". Je to nieco podobne ako non-linear feedback shift register?

Co znamena "mat dobre statisticke vlastnosti"? Napr. predikovatelnost generatora je dost blba vlastnost pri pouziti v kryptografickych aplikaciach, ale v inych vadit nemusi (napr. v grafike). Je aspon pravda, ze hodnoty vygenerovane LCG sa blizia k uniformnemu rozdeleniu?

Některé statistické vlasnosti se mohou projevit docela dobře i v grafice -- např. korelační: Kreslíte náhodné body v prostoru vyšší dimenze než 1 (rovina, 3d bod, bod + hodnota, bod + normála, bod + vektor, etc.) a zjistíte, že nejsou rozložené rovnoměrně (jak byste čekal), tvoří nějaké nadplochy a pod.

Uniformní LCG jsou z toho, jak fungují.