Zufallszahlen
Immer wieder benötigt der Programmierer zufällig erzeugte Zahlen, sei es um Simulationen einer sich chaotisch verhaltenden Umwelt durchzuführen oder einem Spiel eine unvorhersehbare Wendung zu geben. Dafür stellt C einen eingebauten Zufallszahlengenerator zur Verfügung.
Eine Zufallszahl wird durch den Aufruf der Standard-C Funktion rand() erzeugt. Die Funktion liefert im Gegensatz zu «normalen» Funktionen bei jedem Aufruf eine andere Zahl zurück. Diese Zahl wird allerdings mitnichten «zufällig» erzeugt. So etwas würde den Einsatz von Hardware, wie zum Beispiel die Abtastung eines Rauschsignals oder der kosmischen Hintergrundstrahlung erfordern. Vielmehr arbeitet der in C eingebaute Zufallsgenerator nach genau vorgeschriebenen Regeln, die erzeugte Zahlenfolge ist damit «zufällig» nur in dem Sinne, dass sie statistischen Tests auf Gleichverteilung genügt. Unter bestimmten Voraussetzungen kann sie jedoch durchaus in Simulationsprogrammen oder Spielen verwendet werden, um dort eine Zufalls- oder Unsicherheitskomponente zu erzeugen.
Die rand() Funktion arbeitet intern nach der Formel
x = (a * x + c) % m
wobei x die erzeugte Zufallszahl ist (die also zwischen den Aufrufen von rand() in der C-Library zwischengespeichert werden muss) und a, c, m sorgfältig ausgewählte Konstanten sind (die rand() Funktion unter BSD-Unix verwendet hier zum Beispiel a = 1103515245, c = 12345 und m = 231). Daraus ergeben sich einige Schlussfolgerungen:
- Die Zufallszahlenfolge wiederholt sich nach einer gewissen Anzahl von Aufrufen von rand(). Man nennt diesen Wert die Periode des Zufallszahlengenerators (im obigen Beispiel des BSD Generators ist die Periode gleich 231).
- Die erzeugte Zahlenfolge hängt vom initialen Wert von x ab. Dieser Wert wird als Seed bezeichnet und mittels der Funktion srand( int x) gesetzt. Wird srand() nicht verwendet, so wird in der Regel bei jedem Programmdurchlauf dieselbe Zufallszahlenfolge erzeugt. Um dies zu vermeiden, wird der Seed oftmals mit der Systemzeit initialisiert:
srand( time(0));
am Anfang des Programmes bewirkt, dass bei jedem Programmdurchlauf eine andere Zahlenfolge von rand() erzeugt wird. - Der von rand() zurückgelieferte Wert liegt im Wertebereich 0 <= x < m. m ist in C durch die Konstante RAND_MAX definiert. Was aber, wenn Zufallszahlen in einem kleineren Bereich benötigt werden? Oft sieht man dann, dass einfach nur die niederwertigsten Bits des Ergebnisses von rand() verwendet werden, zum Beispiel durch Einsatz des Modulo-Operators. Diese Praxis ist gefährlich, da das Ergebnis nun keine statistisch gesicherte gleichverteilte Zufallszahlenfolge mehr ist. Vielmehr sollte man hier auf Division und Rundung zurückgreifen. Eine universell verwendbare Funktion, die einen zufälligen Integer-Wert x im Bereich a <= x <= e zurückliefert ist hier:
/* get integer random number in range a <= x <= e */ int irand( int a, int e) { double r = e - a + 1; return a + (int)(r * rand()/(RAND_MAX+1.0)); }
Damit kann zum Beispiel eine weitere Funktion geschrieben werden, die im Durchschnitt zur perc Prozent ihrer Aufrufe 1 (TRUE) und sonst 0 (FALSE) zurückliefert:
/* return true perc % of the time */ int percrand( int perc) { return perc >= irand(1, 100); }
Der in der Standard-C-Library vorhandene Zufallszahlengenerator ist für eine Reihe von Aufgaben sicher gut geeignet. Für weitergehende Anforderungen, wie zum Beispiel den Einsatz von Zufallszahlen in der Statistik und Numerik («Monte-Carlo-Methoden») kann es sinnvoll sein, sich eines anderen Algorithmus zu bedienen. Die GNU scientific library bietet eine Reihe von verschiedenen Implementierungen von Random-Generatoren. Für weitere Informationen und eine Liste von verfügbaren Ressourcen im Web zu diesem Thema sei die Website von pLab empfohlen.
Zum Abschluss noch ein kleines Beispielprogramm, welches unter Verwendung der oben vorgestellten Zufallsfunktion irand() moderne Kunst ;-) erzeugt und diese auf der Textkonsole ausgibt (das Artikelbild links oben wurde mit diesem Programm gemalt):
#include <stdio.h> #include <stdlib.h> #include <time.h> #ifdef __BORLANDC__ #include <conio.h> #endif /* definition of function irand - see above */ /* ... */ /* create a figure with random apperance */ void randomFigure( char a[79][24]) { int nParts, i; char app; int x, y; /* number of parts */ nParts = irand(1, 100); /* apperance of the parts */ app = (char)irand( 0, 15); /* starting position */ x = irand( 0, 78); y = irand( 0, 23); a[x][y] = app; for (i = 0; i < nParts; ++i) { /* get next position */ x += irand( -1, 1); y += irand( -1, 1); if (x > 78) x = 78; if (x < 0) x = 0; if (y > 23) y = 23; if (y < 0) y = 0; a[x][y] = app; } } int main( int argc, char **argv) { int i, j; char a[79][24]; /* set the random seed */ srand( time(0)); /* clear painting */ for (j = 0; j < 24; ++j) { for (i = 0; i < 79; ++i) { a[i][j] = 0; } } /* create some random figures */ for (i = 0; i < irand( 10, 60); ++i) { randomFigure( a); } /* draw the painting */ for (j = 0; j < 24; ++j) { for (i = 0; i < 79; ++i) { #ifdef __BORLANDC__ textcolor( a[i][j]); cprintf( "%c", 0xdb); #else printf( "%c", 32 + a[i][j]); #endif } printf( "\n"); } }