Wie der Zufall so will.

Ab und zu stößt man auf etwas und fragt sich “Wie kommt das eigentlich zu stande?”. So ging es mir die Woche mit $RANDOM. Die globale Variable der bash liefert einen Wert zufälligen Wert zwischen 0 und 32767 zurück. Dieser lustige kleine Integer erzeugende Kamerad ist mir jetzt nicht umbedingt neu. 2009 schrieb ich bei Codecocktail mal einen Blogpost darüber. Anders als damals interessierte mich aber was hinter der Value steht und wie sie zustande kommt.

Randomness in Bash

Ich lud mir den Source der bash herunter und laß erstmal etwas. Sollte man eigentlich öfters mal tun, weil man auch über andere unbekannte Dinge wie z.B. $LINENO stößt. Außerdem interessante Comments:

/* From “Random number generators: good ones are hard to find”, Park and Miller, Communications of the ACM, vol. 31, no. 10, October 1988, p. 1195. filtered through FreeBSD */

Das Paper (das nebenbei gesagt älter ist als ich) lässt schon bisschen erahnen wohin die Reise geht. Außerdem erfährt man, dass der Random Number Generator von Turbo Pascal wohl nicht so der Wahnsinn ist. Schade eigentlich.

Creative Commons Attribution-NonCommercial 2.5 License xkcd.com/221

Im Source etwas umgeschaut findet man aber schnell das was man sucht. Mit etwas Bitwise XOR Spass einen Seed auf Zeit- und PID-Basis erstellt, durch den minimalen Standard aus dem Paper gejagt und schon wars das eigentlich.

sbrand (tv.tv_sec ^ tv.tv_usec ^ getpid ());

Taugt das was?

Ich wollts dann schon noch etwas genauer wissen. Mit einem Einzeiler

S=100000000 ; time while [ $S -gt 0 ]; do echo $RANDOM >> random.txt ; ((S--)) ; done

habe ich dann (innerhalb 90 Minuten) 100 Millionen Zahlen generiert. Mein Thinkpad war von dem ganzen Gerechne (immerhin 18500 Values pro Sekunde) allerdings nicht so begeistert:

[45106.836033] intel ips: MCP limit exceeded: Avg temp 9513, limit 9000
[45106.836036] intel ips: MCP limit exceeded: Avg power 41641, limit 35000

Wahrscheinlich habe ich es etwas übertrieben. Was solls. Auf die Sample Size kommts schliesslich an!

Die 540MB große Datei hab ich dann etwas sortiert und in einen Graphen gestopft. Die Null-Hypothese dabei: Einer der Werte ist statistisch signifikant höher als alle anderen. Weil für Google Charts 32k Values wohl etwas zu viel ist, ein Graph mit gnuplot

Den vielen Values gedankt sei auch die Unübersichtlichkeit des Graphen. Deshalb noch ein kleinwenig mehr Statistikpr0n. Im Durchschnitt wird jede der Zahlen bei 100 Mio. Durchgängen ca. 3050 mal genannt. Wesentlich interessanter dabei ist aber die Abweichung vom Durchschnitt (siehe auch Standard Deviation). Bei der Bestimmung derer hilft eine kleine awk Zeile.

awk '{sum+=$1; sumsq+=$1*$1} END {print sqrt(sumsq/NR - (sum/NR)**2)}' sorted.txt

Bei meinen File wich also jeder der Werte durchschnittlich 53.6643 von der Durchschnittshäufigkeit ab. Wenn man das weiß, hat man schonmal ein ziemlich gutes Gefühl für das Auftreten der Integers.

Unterm Strich empfinde ich $RANDOM als eine mehr als zufriedenstellende Variante eines Random Number Generators. Vielleicht war aber auch einfach nur ein guter Tag (wörtlich!) für das zufällige generieren von Zahlen.

Comments (9)

Patrick Kohan on 2012-12-28T21:47:08

sehr guter Artikel, hatten das mal behandelt in der Vorlesung Betriebssysteme, mein Vorschlag ist /dev/random oder /dev/urandom auszulesen ;-)

dAnjou on 2012-12-28T23:13:29

Du hast leider nicht nur den alt-Text des XKCD-Comics vergessen, sondern auch gleich noch die Lizenz verletzt: http://xkcd.com/license.html

noqqe on 2012-12-29T08:03:09

Vielen Dank :) Jupp. Hast ne gute Zeile parat gleich nur Numerische Sachen auszugeben?

noqqe on 2012-12-29T08:15:07

Ah. Title != Alt Text. Von Dilbert gab es auch einen Comic der sehr gut gepasst hätte, aber da konnt ich überhaupt nicht durchblicken ob man das jetzt darf oder nicht. In dem FAQ geht es meistens um "use in presentations" usw. Ziemlich komisch. Habs jetzt mal noch einen ALT Text hinzugefügt.

sgolb on 2012-12-29T11:03:20

Je nach Bedarf angepasst, so was: od -An -N2 -i /dev/random

Thomas Gericke on 2012-12-29T11:57:08

Lorag on 2012-12-29T13:50:52

$RANDOM liefert doch aber trotzdem keine Zufallszahlen, auch wenn die statischen Eigenschaften der Werte in Ordnung sind.

noqqe on 2012-12-29T19:10:15

Ich weiss nicht was du damit versuchst zu sagen. Genauer?

Lorag on 2012-12-30T16:23:20

Zufallszahlen zu erzeugen ist für Computer normalerweise sehr schwierig, meist bedarf es dazu spezieller Hardware. Für die meisten Anwendungen behilft man sich daher mit Zahlen, deren Generierung auf einem nicht einsehbaren Ausgangsmuster beruht und deren gleichmäßige Häufigkeitsverteilung und niedrige Korrelation dem echter Zufallszahlenreihen gleichen. Wenn man sich die Zahl π als Zahlenreihe denkt und der Computer auf Tastendruck anfangen würde durch die Ziffern zu gehen, würde man, wenn der Computer auf einen zweiten Tastendruck stoppt, eine „zufällige“ Ziffer zwischen 1 und 9 bekommen. Tatsächlich ist diese Zahl aber nicht zufällig, sondern nur undurchschaubar. Wer den exakten Abstand zwischen beiden Tastendrücken kennt und dazu die Geschwindigkeit, mit der der PC rechnet, kann die Zahl bestimmen. Genauso, wie ich das Sample von $RANDOM bestimmen kann, wenn ich den seed kenne – oder in diesem Fall Zeit und PID. Deshalb spricht man dabei von Pseudozufallszahlen. $RANDOM ist ein deterministischer Pseudozufallszahlengenerator. Wenn du RANDOM für jeden Durchlauf des Skripts den gleichen Seed gibst, bekommst du exakt dieselben Zufallswerte. Das macht auch nichts, solange man jedes Mal reseedet und den Generator nur für triviale Anwendungen benötigt. Eine andere Lösung braucht man allerdings, wenn man etwa kryptologisch sichere Zufallszahlen haben will. Da stehen meistens auch keine nicht deterministischen Generatoren zur Verfügung, weshalb viele Mathematiker an Lösungen gearbeitet haben, die trotzdem kryptologisch sicher sind. Unter dem Strich komme ich allerdings zu demselben Ergebnis $RANDOM ist für das meiste mehr als ausreichend und hat vor allem den Vorteil, schnell zu sein.