Die Monte-Carlo- Methode zur Bestimmung der Kreiszahl  p

In den achtziger Jahren besuchte ich mit einer Schulklasse eine Landesgartenschau in Baden-Württemberg. Am Eingang musste jeder Besucher einen Pingpong Ball in eine Öffnung werfen, und eine große Digitalanzeige verriet dann eine nächste Näherung für die Kreiszahl p ...
So mitten im Trubel konnte ich den verdutzten Schülern keine erschöpfende Erklärung bieten; außerdem ging es  an diesem Tage ja auch um Pflanzen. Da es sich jedoch um eine 10.Klasse handelte, bekam ich später einen guten Aufhänger für die Behandlung von Näherungsverfahren für die Kreiszahl.

Mathematischer Hintergrund
Bei der  Monte-Carlo-Methode approximiert man  p durch sehr spektakuläre stochastische Überlegungen. 

  





In ein Einheitsquadrat mit Einheitsviertelkreis  ergießt sich ein Zufallsregen. Die Gesamtzahl g der Tropfen verhält sich zur Zahl der Tropfen im Viertelkreis v wie der Inhalt der Quadratfläche zum Inhalt der Viertelkreisfläche. Entsprechend ergibt sich folgende Näherungsgleichung:
                                 

Ein Tropfen treffe im Quadrat in P auf; ist  die Streckenlänge OP kleiner oder gleich 1, befindet sich P sogar im Viertelkreis (, und der Zähler v muss erhöht werden).

Struktogramm

                         // i ++ steht für das Inkrementieren von i um 1 pro Schleifendurchgang
                       for (int i = 1; i <= g; i++) {

            //Schleifenrumpf  }

                             

class Pi  {
  public static void main(String[] args)  {
    // Gesamtzahl der Tropfen
    int g = Integer.parseInt(args[0]); 
    // Tropfen im Viertelkreis
    int v = 0;
    // Koordinaten des Punktes P 
    double x,y;
    System.out.println(" Monte Carlo Methode");
    System.out.println(" Naeherung fuer Pi:");
    for (int i = 1; i <= g; i++)   {	
      x = Math.random();
      y = Math.random();
      if (Math.hypot(x,y) <= 1)	
        v = v + 1;
    }  
    double pi = 4*(double)v / g; 
    System.out.printf(" %d Tropfen, davon %d Tropfen im Viertelkreis, Pi etwa %g%n",g,v,pi);	 
  }
}	

		    

• Für die Koordinaten und für p benötigt man Gleitkommazahlen; diese werden durch den Datentyp double bereitgestellt.
• Math.random()liefert Zufallszahlen von 0 bis (ausschließlich) 1.
• Math.hypot(x,y)berechnet die Streckenlänge OP (Hypotenusenlänge).
• Das float bei der Berechnung der Näherung für p ist notwendig, da sonst eine Ganzzahldivision durchgeführt würde.
• Im Formatstring ist %g ein Platzhalter für eine Gleitkommazahl.

Wiederhole-Schleife

// Jetzt soll die Iteration abgebrochen werden, wenn sich die Näherungswerte
// nur noch im Rahmen eines vorgegebenen Epsilon-Bereiches ändern
class Pi_2  {
  public static void main(String[] args)  {
    int i = 0;
    int v = 0;
    // Startwert von Pi für den ersten Vergleich
    double pi = 3;
    double x,y,pi_alt;
    // Falls sich zwei Näherungswerte um höchstens diese Differenz epsi
    // unterscheiden, soll die Iteration abgebrochen werden
    double epsi = 1.E-5;
    do   {
      i++;   // Tropfenzahl
      pi_alt = pi;
      x = Math.random();
      y = Math.random();
      if (Math.hypot(x,y) <= 1)
        v++;  // Tropfen im Viertelkreis
      pi = 4*(float)v / i;
    }
    while (Math.abs(pi_alt - pi) > epsi);  
    System.out.printf(" Nach %6d Tropfen ist die Naeherung fuer Pi  %g%n",i,pi);
    //System.out.printf(" Der Konvergenzbereich ist %g breit", 2*epsi);   
  }
}

Die drei Aufrufe des Programmes verdeutlichen, wie sich im Sinne des Gesetzes der großen Zahl der Wert von p herauskristallisiert; allerdings ist eine sehr große Tropfenzahl für eine vergleichsweise "bescheidene" Näherung erforderlich; das Konvergenzverhalten des Verfahrens ist also "ungünstig".

Operatoren
Außerdem kann man mit dem o.g. Quelltext auch Überraschungen erleben: Ggf. steigt das Programm z.B. mit der Meldung aus, dass es nach 2 Tropfen eine Näherung 4 für p gäbe...Wie man leicht sieht, folgt dies, wenn die ersten Tropfen alle im Viertelkreis landen.
Um auch dies zu berücksichtigen, passen wir unsere Schleifenbedingung an:
       while ((Math.abs(pi_alt - pi) > epsi) || (i < 10));
Die Schleife soll also in jedem Fall für die ersten 9 Tropfen weiterlaufen; als logischen Operator haben wir || (für ODER) gewählt.

• Weitere logische Operatoren sind &&  ( für UND) und ! (für NICHT).
• An arithmetischen Operatoren haben wir bereits kennengelernt: +   -   *   /   %
• Relationale Operatoren <     >    <=     >=    ==     !=
  

Runden
Wie viele Tropfen unseres Zufallsregens sind nun notwendig, um p wenigstens auf 4 Dezimalen zu bestimmen?
Ausgehend von pi = 4*(float)v / i;
kann man z.B. pi mit 10000 multilplizieren, auf Einer runden und durch 10000 dividieren. 
Aus dem unteren Teil des Schleifenrumpfes würde dann

     ......
  pi = 4*(float)v / i;
  pi = Math.round(10000 * pi)/10000.0;
  }
 while (pi != 3.1415);

 Hier verdeutlichen die 5 Aufrufe, dass  sogar das verhaltene Tempo der Konvergenz sehr statistisch ist...

Quellen

1. Vorlesung "Einführung in die Programmierung" von Prof. Dr. Herbert Göttler im WS 2007 / 2008 an der Universität Mainz.
   
2. Übungsblätter "Einführung in die Programmierung" von Thomas Gottron im WS 2007 / 2008 an der Universität Mainz.
   
3. Reinhard Schiedermeier — Programmieren mit Java  ISBN: 978-3-8273-7116-4
   480 Seiten; Sprache: Deutsch; € 39,95 [D]
   
4. Herrn Mahdi D-Manesh / Universität Mainz / Fachbereich Informatik bin ich für die Durchsicht der Vorlage und die 
   hilfreichen Anregungen sehr dankbar.