Pi mit Monte-Carlo-Simulation und Leibnitz-Formel berechnen

Die Kreiszahl π≈3,14159 ist jedem bekannt, aber wie berechnet man sie? Viele Mathematiker haben sich damit beschäftigt und sehr viele interessante und mächtige Algorithmen entwickelt, so das mittlerweile über 5 Billionen Nachkommastellen von Pi bekannt sind.

Am einfachsten bestimmt man die Kreiszahl nach ihrer Definition. Man nimmt also einen Kreis, misst seinen Durchmesser und seinen Umfang und berechnet das Verhältnis Durchmesser/Umfang, welches der Kreiszahl entspricht. Das kann auch jeder Zuhause sehr schnell mit einen Faden, einen Lineal und einem kreisförmigen Gegenstand überprüfen :).
Besonders genau ist diese Methode aber nicht – man braucht eine mathematische Herangehensweise.

Eine andere interessante Methode ist die Leibniz-Reihe die folgendermaßen lautet.

\sum_{n=0}^\infty \frac{(-1)^n}{2n+1} = 1 -\frac{1}{3} + \frac{1}{5} -\frac{1}{7} + ... = \frac{\pi}{4}

Je mehr Glieder man berechnet, desto mehr nähert sich der berechnete Wert π/4 an.
Ich habe eine Funktion in C++ geschrieben, die Pi nach dieser Methode berechnet.

// berechnet Pi nach Leibniz-Formel
double piWithPowerSeries(unsigned int steps)
{
	// pi/4
	double piQuarter = 0.0;

	for(unsigned n = 0; n < steps; n++)
	{
		piQuarter = piQuarter + pow(-1.0, static_cast<int>(n)) / (2*n +1);
	}

	// pi/4 * 4 = pi
	return piQuarter*4;
}

Die Berechneten Werte sehen dann folgendermaßen aus.

Pi berechnet nach Leibniz-Formel

Pi berechnet nach Leibniz-Formel

Eine andere und meiner Meinung nach intuitive Methode ist die Monte-Carlo-Simulation.
Die Idee dahinter ist ziemlich simpel. Man lege einen Kreis oder noch simpler einen Viertelkreis in einen Quadrat, so dass der Durchmesser des Kreises gerade der Seitenlängen des Quadrats entspricht.

Viertelkreis in einem Quadrat.

Viertelkreis in einem Quadrat.

Jetzt verteilt man in dem ganzen Quadrat zufällig Koordinatenpunkte.

Ein Tausend zufällig verteilte Punkte.

Ein Tausend zufällig verteilte Punkte.

Hat man die Punkte verteilt, so zählt man wie viele von ihnen im Kreis liegen. Für große Anzahl der Punkte geht die Häufigkeitsvertelung der Punkte in die Wahrscheinlichkeit über. Mit anderen Worten: die Anzahl der Punkte im Kreis im Verhältnis zu der Gesamtzahl gibt die Wahrscheinlichkeit an, dass der nächste zufällig gesetzte Punkt auch im Kreis landet und somit entspricht diese Wahrscheinlichkeit auch dem Verhältnis der Kreisfläche zur Gesamtfläche.

\frac{Punkte\ im\ Kreis}{Punkt\ im\ Quadrat} \approx \frac{Kreisflaeche}{Quadratflaeche} = \frac{\pi r^2}{(2 r)^2} = \frac{\pi}{4}

Ziemlich cool oder? ;)

Zur diesen Methode habe ich auch eine C++ Funktion geschrieben.

// erzeugt (Pseudo-)Zufallswerte zwischen 0.0 und 1.0 
double getRand()
{
	return static_cast<double>(rand())/static_cast<double>(RAND_MAX);
}

// berechnet Pi mit Monte-Carlo-Simulation
double piWithMCS(unsigned int steps)
{
	// Zufallsgenerator initialisieren
	srand(time(0));

	// Anzahl der Punkte in einem Viertel eines Einheitskreises
	double in = 0.0;
	
	for(unsigned n = 0; n < steps; n++)
	{
		// Zufälligen Punkt generieren
		double x = getRand();
		double y = getRand();

		// schauen ob der Punkt im Kreis liegt
		if(x*x + y*y <= 1.0)
			in++;
	}

	return 4*(in/steps);
}

Das Ergebnis sieht dann so aus.

Berechnung von Pi mit Monte-Carlo-Verfahren.

Berechnung von Pi mit Monte-Carlo-Verfahren.

Der Wert konvergiert nicht so schnell gegen Pi, wie mit der Leibniz-Formel, aber er konvergiert.

Ich finde es schon irgendwie faszinierend, dass das einfache Auswerten von Zufallswerten sich auf so eine Art und Weise nutzen lässt.
Wer Lust und Zeit hat, kann ja versuchen das Ergebnis auch mit einem Spielwürfel zu bestimmen ;)

Hier ist noch mal der komplette Quelltext als Cpp-Datei: Pi-Berechnung 1,77 kB -


2 Kommentare zu “Pi mit Monte-Carlo-Simulation und Leibnitz-Formel berechnen”

  1. M. Hammer-Kruseam 12. August 2011 um 18:19 Uhr

    Da gibt es auch die Buffonsche Nadelmethode, die läßt sich ebenso schön mit einem Programm simulieren:

    Lasse eine Nadel gegebener Länge zufällig auf ein Muster aus äquidistanten Linien fallen. Die Wahrscheinlichkeit dafür, daß die Nadel eine Linie trifft, ist dann eine Funktion von Pi, Nadellänge und Linienabstand.

    Gruß, mike

  2. Maximam 12. August 2011 um 18:47 Uhr

    Davon habe ich noch nie was gehört.

    Habs gefunden: http://en.wikipedia.org/wiki/Buffon%27s_needle
    Ist ja im Prinzip auch eine Art MCS.

Trackback URI | Kommentare als RSS

Einen Kommentar schreiben

XHTML: Du kannst folgende Tags verwenden: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <sub> <sup>

Hinweis: Ich behalte mir das Recht vor solche Kommentare, die Beleidigungen oder rechtswidrige Inhalte beinhalten erst nach einer Editierung freizugeben oder kommentarlos zu löschen. Ähnliches gilt auch für Kommentare die offensichtlich nur der Suchmaschinenoptimierung dienen.