Pi

Pi ($\pi$) ist eine Zahl, die das Verhältnis zwischen dem Durchmesser eines Kreises und seinem Umfang beschreibt.

Algorithmische Berechnung

Viertelkreis, mit Flächenraster 10×10 angenähert, innerhalb 79 Punkte (rot), außerhalb 21 Punkte (blau)

$\pi$ lässt sich algorithmisch wie folgt berechnen: Man nimmt ein Quadrat der Seitenlänge 1 und zeichnet dort hinein einen Viertelkreis mit dem Radius 1. Dieser Viertelkreis hat die Fläche ${\frac {\pi }{4}}$. Über dieses Quadrat legt man nun ein Raster aus Punkten und prüft für jeden dieser Punkte, ob er in dem Viertelkreis liegt oder nicht. Die Anzahl der Punkte im Viertelkreis geteilt durch die Gesamtzahl der Punkte im Quadrat ergibt dann eine Näherung für ${\frac {\pi }{4}}$. Je engmaschiger dabei das Gitter ist, desto genauer wird auch die Näherung für $\pi$.

💬

Beispiel

Das rechts abgebildete Quadrat ist von einem Raster von 10×10 Punkten überzogen. Davon liegen 79 im Kreis (rot eingezeichnet). Als Näherung für ${\frac {\pi }{4}}$ ergibt sich der Wert ${\frac {79}{100}}=0,79$, multipliziert mit 4 die Näherung $3,16$ für $\pi$.

Als Programmablaufplan kann man diesen Algorithmus folgendermaßen darstellen:

graph TD start(("Start")) --> s1["Setze <code>x</code> auf 0"] --> s2["Setze <code>points_total</code> auf 0"] --> s3["Setze <code>points_circle</code> auf 0"] --> s4["Setze <code>STEP</code> auf 0.001"] --> wx{"<code>x</code> < 1?"} --ja--> s5["Setze <code>y</code> auf 0"] --> wy{"<code>y</code> < 1?"} --ja--> if{"<code>x</code>² + <code>y</code>² ≤ 1?"} --ja--> s6["Erhöhe <code>points_circle</code> um 1"] --> s7["Erhöhe <code>points_total</code> um 1"] --> s8["Erhöhe <code>y</code> um <code>STEP</code>"] --> wy wy --nein--> wx if --nein--> s7 wx --nein--> s9["Setze <code>pi</code> auf <code>points_circle</code> / <code>points_total</code> * 4"] --> out[/"Gib <code>pi</code> aus"/] --> ende(("Ende"))

Die Konstante STEP gibt dabei an, wie engmaschig das Gitter sein soll, und kann beliebig angepasst werden. Der Wert für STEP muss dabei zwischen 0 und 1 liegen.

Laufzeit dieses Algorithmus

Die Laufzeit dieses Algorithmus hängt davon ab, wie viele Punkte betrachtet werden müssen. Bei einem Gitter von $n\times n$ Punkten beträgt die Laufzeit darum ${\mathcal {O}}(n^{2})$.

Berechnung mit Monte-Carlo-Algorithmus

Viertelkreis, dessen Fläche durch die Monte-Carlo-Methode angenähert wird

Alternativ kann man auch einen Monte-Carlo-Algorithmus, d.h. einen Algorithmus mit einem zufallsbasierten Anteil, verwenden, um $\pi$ zu berechnen. Hier wird das Quadrat nicht mit einem systematischen Gitter, sondern einem zufälligen Hagel aus Punkten überzogen. Als Programmablaufplan kann man diesen Algorithmus folgendermaßen darstellen:

graph TD start(("Start")) --> s1["Setze <code>ZIEL</code> auf 10000"] --> s2["Setze <code>points_total</code> auf 0"] --> s3["Setze <code>points_circle</code> auf 0"] --> w{"<code>points_total</code> < <code>ZIEL</code>?"} --ja--> s4["Setze <code>x</code> auf eine Zufallszahl zwischen 0 und 1"] --> s5["Setze <code>y</code> auf eine Zufallszahl zwischen 0 und 1"] --> if{"<code>x</code>² + <code>y</code>² ≤ 1?"} --ja--> s6["Erhöhe <code>points_circle</code> um 1"] --> s7["Erhöhe <code>points_total</code> um 1"] --> w if --nein--> s7 w --nein--> s9["Setze <code>pi</code> auf <code>points_circle</code> / <code>points_total</code> * 4"] --> out[/"Gib <code>pi</code> aus"/] --> ende(("Ende"))

Die Konstante ZIEL gibt dabei an, wie viele zufällige Punkte in dem Quadrat verteilt werden sollen und kann beliebig angepasst werden. Je mehr Punkte gestreut werden, desto länger benötigt der Algorithmus, desto genauer ist aber auch das Ergebnis.

Laufzeit dieses Algorithmus

Die Laufzeit dieses Algorithmus hängt davon ab, wie viele Punkte betrachtet werden müssen. Bei $n$ zufällig gestreuten Punkten ergibt sich dabei eine Laufzeit von ${\mathcal {O}}(n)$.

Verwendung in verschiedenen Programmiersprachen

Verwendung von $\pi$ in verschiedenen Programmiersprachen

Programmiersprache	Ausdruck für $\pi$	ggf. nötige Import-Anweisung
Python	math.pi	import math
JavaScript	Math.PI	–