Zufallsfunktion in C/C++ gesucht

Jan-Michael

Jan-Michael

Aktives Mitglied
Thread Starter
Dabei seit
28.02.2005
Beiträge
397
Reaktionspunkte
0
Erstmal hallo an alle Macuser!!

Die letzten Tage habe ich an meinem Mac verzweifelt versucht in C/C++ eine Zufallsfunktion zu implementieren. Nachdem ich zuerst versucht habe mein Problem(Berechnung von Flächeninhalten mit Stochastik) in C mit dem folgenden Listing zu lösen:

#include <stdio.h>
#include<time.h>
#include<unistd.h>
#include<stdlib.h>

int main() {

double x_double=0, y_double=0;
double punkt=0, innen=0;
double c=175, d=175, r=125;

srand((unsigned)time(NULL) + getpid());

for(int i=0; i<6000; i++) {
x_double=50+(rand()%300);
y_double=50+(rand()%300);

if(y_double<(double)(sqrt((-x_double*x_double)+2*c*x_double-(c*c)+(r*r))+d) && y_double>(double)(d-sqrt((-x_double*x_double)+2*c*x_double-(c*c)+(r*r)))) {
innen++;
}
punkt++;
}

printf("Insgesamt: " + punkt + " Punkte" + "\n");
printf("Davon " + innen + " innerhalb des Kreises" + "\n");
printf(" " + (punkt-innen) + " au§erhalb des Kreises" + "\n");
printf( "Das Quadrat hat eine Fläche von 300PX*300PX = " + (300*300) + " Pixeln" + "\n");
printf("Nach der obigen Verteilung hat der Kreis eine Fl·che von " + (((300*300)/punkt)*innen) + " Pixeln" + "\n");
}

musste ich jedoch später feststellen, dass die C-Funktionen srand() und rand() nicht den gewünschten Erfolg brachten(nur Pseudozufallsfunktion wie ich in Kernigan und Richies C-Dokumentation nachgelesen habe, die nur unzureichen Zufall berechnen können), den ich mir eigendlich erhoffte hatte. Das Programm gibt an, dass die Fläche des zu berechnenden Kreises(siehe nach y aufgelöste Kreisgleichung innerhalb der if()-Bedingung) halb so groß ist, wie die des umschließenden Quadrates(siehe Einschränkung der Funktion rand() auf eine Fläche 250*250 Pixel). Eine Portierung in Java, in der ich die Funktion Math.random() verwendet habe gibt das Richtige Ergebnis(soweit bei Stochastik von Richtig oder Falsch geredet werden kann) aus. Wie kann ich das Problem in C/C++ lösen? Bitte schreibt mir Vorschläge zu Zufallsfunktionen/anderen Möglichkeiten Zufall in C oder C++ zu berechnen.

PS: Für C++ habe ich keine Zufallsfunktion gefunden, die in der C++ Bibliothek definiert ist. Vielleicht ist das die Funktion, die ich Suche.
 
Zuletzt bearbeitet:
man random
apropos random

solltest du dir mal ankucken
 
Das Verfahren hinter rand() hat den Haken dass in den niederwertigen Bits in Relation gesehen häufig Muster auftreten. Mit dem Modulo-Operator sind es aber gerade diese niederwertigen Bits, die Du als Basis für Deine Zufallswerte benutzt. Vielleicht bringt es Dir schon etwas, wenn Du das Ergebnis von rand() erstmal durch einen geeigneten Wert dividierst (d.h. Bits nach rechts schiebst).
 
hallo, machst du das eigentlich mit den xtools ?? ich frag nur weil mir dei bibliotheken so bekannt vorkommen vom borland builder 5.0 in der x86'er welt
 
Hallo Jan-Michael,

Du versuchst mittels stochastischem Sampling den Flächeninhalt eines Kreises näherungsweise zu bestimmen, doch leider ist Dir in der Verwendung von rand() ein Fehler unterlaufen: Die ausmaskierten Bits sind nicht gleichverteilt, wie dannycool schon bemerkt hat. Um eine vernünftige Samplemenge zu generieren, berechne gleichverteilte (Pseudo-)Zufallszahlen auf dem Intervall [0,1] und bilde diese auf das Quadrat ab. Siehe dazu den Code.

Code:
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NUM_SAMPLES    99999999
#define SEITENLAENGE	2.0

int main()
{
	long innen = 0, i = 0 ;
	const double halbe_seite = SEITENLAENGE / 2.0, flaeche = SEITENLAENGE * SEITENLAENGE;
	double verhaeltnis;
	
	srand(time(NULL));

	for ( ; i < NUM_SAMPLES ; i++)
	{
		double x = (double) rand() / (double) RAND_MAX;
		double y = (double) rand() / (double) RAND_MAX;

		double x_sample = x * SEITENLAENGE;
		double y_sample = y * SEITENLAENGE;

		x_sample -= halbe_seite;
		y_sample -= halbe_seite;

		if ( sqrt ( x_sample * x_sample + y_sample * y_sample ) < halbe_seite)
			innen++;
	}

	verhaeltnis = (double) innen / (double) NUM_SAMPLES;

	printf("%20s: %d\n%20s: %d\n%20s: %d\n%20s: %3.8f\n%20s: %3.8f\n",
		"samples", NUM_SAMPLES,
		"innen", innen,
		"aussen", NUM_SAMPLES - innen,
		"Verhaeltnis", verhaeltnis,
		"Kreisflaeche", flaeche* verhaeltnis); 
	return 0;
}

Echte Zufallszahlen (ZZ) kann man auf einem Rechner i.d.R. nicht erzeugen.
Funktionen wie rand() können lediglich Zahlenfolgen generieren, die sich ein wenig wie echte ZZ verhalten, weil sie gleichmäßig über ein Intervall verteilt scheinen. Aber wie Du leicht siehst, erzeugt z.B. rand() auf einem 32-bit Rechner maximal Zahlen im Intervall von 0 bis 2^32 -1. Bildet man diese auf [0,1] ab, ist es ausgeschlossen, daß alle Werte im Intervall "getroffen" werden, was bei echten ZZ natürlich möglich und wünschenswert wäre.
Außerdem weisen Funktionen zur Erzeugung von Pseudo-Zufallszahlen i.d.R. Mängel in der Veteilung auf: Es kann z.B. vorkommen, daß die erzeugten Zahlen in irgendwelchen Unterräumen liegen, wenn man sie paarweise als Vektoren betrachtet: Da können Streifenmuster oder Ebenenschichten enststehen, wenn man die Zahlen plottet.
Viele ZZ-"Generatoren" (z.B. Implementierungen von rand() ) sind sog. "Lineare Kongruenzgeneratoren": Diese erzeugen "ZZ" nach einer Funktion der Form Z(i) = a * Z(i-1) + c mod(m), mit a,c,m als konstanten ganzen Zahlen. Diese Generatoren wiederholen die Zahlenfolgen nach einer gewissen Periode, deren Länge stark von der Wahl des a abhängt.
Im Codebeispiel siehst Du, daß Pi nicht sonderlich toll approximiert wird. Hier zeigen sich schon die Schwächen von 32bit und des rand() (, aber auch des ganzen Verfahrens). Du kannst das Ergebnis verbessern, indem Du z.B. die Anzahl der Samples erhöhst und/oder mehrere Läufe durchführst und über die Resultate mittelst...
Falls Du ernsthafte stochastische Simulation betreiben willst und Dich für das Thema ZZ interessierst hier etwas Literatur:

- Press, Teukolsky, Vetterling, Flannery: "Numerical Recipes", Kapitel 7

- D. E. Knuth: "The Art Of Comupter Programming" Vol. II

- Law & Kelton: "Simulation Modeling and Analysis" Kapitel 7

Es ist sehr schwer, gute ZZ-Generatoren zu implementieren. Schau mal ansonsten mal hier:

- Der "Mersenne-Twister" ist ein Bespiel für einen Generator mit sehr langer Periode:
(http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html)

- GNU Scientific Library:
(http://www.gnu.org/software/gsl/)

- die Generatoren aus Law & Kelton in C:
http://www.mhhe.com/engcs/industrial/lawkelton/student/code.mhtml

Viel Erfolg!

Kay
 
Zuletzt bearbeitet:
kiu schrieb:
hallo, machst du das eigentlich mit den xtools ?? ich frag nur weil mir dei bibliotheken so bekannt vorkommen vom borland builder 5.0 in der x86'er welt
Wieso, ist doch die normale stdlibc?
 
Ich würde einen Schritt weiter gehen und das als Unix-Code bezeichnen (unistd.h, getpid,...)
 
Erstmal danke für die Antworten. Ihr habt mich echt weitergebracht. Vor allem das letzte Listing von Kay war echt toll. Danke übrigens für die Internet-Seiten und die Literaturhinweise. Ich werd' sie mir auf jeden fall nochmal anschauen. Vor allem "The Art Of Computer Programming" interesseiert mich sehr, da ich mir neben Beispielen für ZZs eine Breite Anzahl an Anwendungsbeispielen erhoffe, die man auch im täglichen Gebrauch verwenden kann.

@kiu: Die xtools verwende ich noch nicht. Da ich unter OS X 10.2.8 arbeite stehet mir im Moment von Apple nur der Project Builder (also die Vorgängerversion der xtools) zur Verfügung. Daneben compiliere ich meine Programme auch mit dem VCToolKit bzw. VC-Compiler von Microsoft unter VirtualPC. Dies hat den Vorteil, dass man seine Programme einem breiteren Publikum zur Verfügung stellen kann, ohne selber eine x86-Maschine parallel zum Mac benutzen zu müssen.
 
Dannycool: Da hast du recht. unistd.h gehört zu den Unix/POSIX-Bibliotheken, aber er sprach ja von drei Headern, wobei drei von denen zur Standardbibliothek gehören, die auch der Borland C-Builder verwenden könnte ;)
 
Zuletzt bearbeitet:
@Jan-Michael:

Die Buchtipps von mir sind eher zum Nachschlagen gedacht, besonders das 3-bändige Werk "Art of Computer Programming" von Knuth ist so etwas wie die "Bibel" der Informatik. Schau lieber mal nach, ob Du beim Buchhändler Deines Vertrauens eins dieser Bücher findest:

- R. Sedgewick: "Algorithmen" (den gibt es auch in Deutsch und in "C" ;) )

- Cormen, Leiserson, Rivest: "Introduction to Algorithms" (<- IMHO einen Tick anspruchsvoller)

Es gibt sicher Dutzende deutschsprachige (und preiswertere) Titel, aber leider kenn´ ich keinen :(

Gruß,

Kay
 
Zurück
Oben Unten