Date Tags Python

Pi mittels Monte-Carlo-Simulation approximieren

Es gibt ein sehr anschauliches Beispiel für Monte-Carlo-Simulation zur Berechnung der Kreiszahl Pi.

Monte-Carlo-Simulation?

Verfahren aus der Stochastik, bei dem eine sehr große Zahl gleichartiger Zufallsexperimente die Basis darstellt. Es wird dabei versucht, mit Hilfe der Wahrscheinlichkeitstheorie analytisch nicht oder nur aufwendig lösbare Probleme numerisch zu lösen. Als Grundlage ist vor allem das Gesetz der großen Zahlen zu sehen. Die Zufallsexperimente können entweder – etwa durch Würfeln – real durchgeführt werden oder in Computerberechnungen über Erzeugung geeigneter Zufallszahlen. Monte-Carlo-Simulation in der Wikipedia

Die Berechnung der Kreiszahl Pi ist relativ aufwendig (siehe Bailey-Borwein-Plouffe-Formel), aber es gibt einen direkten Zusammenhang zur Fläche des Einheitskreises:

x2 + y2 = 1 ist der Einheitskreis,

und A = πr2 die Fläche (π im Falle des Einheitskreises, r=1).

Die Monte-Carlo-Simulation verbindet nun beide Formeln, indem zwei Zufallszahlen ermittelt werden (x und y) und diese entweder im Kreis oder außerhalb des Kreise landen.

Bei ausreichend vielen, ausreichend guten Zufallszahlen kann man dann direkt Pi ableiten. Hier mal als Visualisierung mit 12.000 zufälligen Punkten:

Monte Carlo Pi Visualisierung (12.000 Punkte)

Parallelprogrammierung mit Python

Das Problem hierbei ist ausreichend viele, ausreichend gute Zufallszahlen zu bekommen.

Die erste Idee ist, die Berechnung öfters durchzuführen, um dann den Mittelwert für Pi anzunehmen. Allerdings dauert das schnell recht lange, weil im einfachen Fall nur eine CPU verwendet wird.

Da selbst mein Telefon mittlerweile mindestens zwei CPUs hat, sollte man also einen Weg finden können, diese auch zu nutzen. Parallelprogrammierung zur Hilfe bitte.

Python bietet ein eigenes Modul hierfür, das multiprocessing Modul. Ich selbst habe mich durch eine recht sperrige Erklärung in einem Projekt durchgekämpft und dann ein Klassenmodell für meine Zwecke verwendet, es geht aber manchmal unheimlich viel einfacher.

Die Pool-Klasse des multiprocessing Moduls baut ein Berechnungspool auf, der sich mittels speziellem map Befehl befüllen lässt.

Im folgenden Fall wird die gemappte Liste allerdings nur verwendet, um die pi-Funktion entsprechend viele Male aufzurufen, normalerweise kann man so natürlich auch Eingabeparameter übergeben:

import random
from multiprocessing import Pool


def pi(v):
    n = 10**6
    pi = 0
    for i in xrange(n):
        if random.random()**2 + random.random()**2 < 1:
            pi+=1
    return 4.0*pi/n

def calculate_pi(reps = range(1000)):
    pool = Pool()
    results = pool.map(pi, reps)
    pool.close()
    pool.join()
    return sum(results)/len(results)

if __name__ == "__main__":
    print calculate_pi()

Mit folgendem Ergebnis:

$ python calculate_pi.py
$ 3.14161892

Hier das zugehörige Gist:


Comments

comments powered by Disqus