Kreiszahl Pi

[Elija7906]

Ich arbeite gerade an einer Aufgabe über die Kreiszahl PI und habe diese eigentlich auch erledigt frage mich aber warum sich meine Ausgerechnete zahl Pi so sehr von der Math.PI abweicht und wie ich die abweichung verringern könnte?

Vielen Dank!

package Mathe;


import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.Random;

public class Kreiszahl {
    long anzahlPunkte = 1000000000;
    double radius = 1;
    public static void main(String[] args) {

        BigDecimal pi = Algo(1000000000, 1);
        System.out.println("PI = "  + pi);
        System.out.println(Math.PI);
        
    }

    public static BigDecimal Algo(long anzahlPunkte, double radius) {
        Random random = new Random();
        long treffer = 0;
        //int treffer = 0;
        for (long i = 0; i < anzahlPunkte; i++) {
            double x = random.nextDouble() * radius;
            double y = random.nextDouble() * radius;

            if (x * x + y * y <= radius * radius) {

                treffer++;

            }
        }
        return BigDecimal.valueOf(4).multiply(BigDecimal.valueOf(treffer).divide(BigDecimal.valueOf(anzahlPunkte),20,RoundingMode.HALF_DOWN));
    }
}

 

[KonradN]

Also der Algorithmus ist recht ungenau. Du brauchst also nicht einmal BigDecimal oder so, denn die Genaugigkeit nimmt viel zu langsam zu um dies zu rechtfertigen.

Schauen wir einfach einmal im Wikipedia:

Monte Carlo integration - Wikipedia

en.wikipedia.org

Da findest Du dann unter anderem eine Herleitung, die die Genauigkeit angibt ... und die ist abhängig von 1 / Wurzel(N). Also 100 Mal mehr Berechnungen geben nur 1/10 Verbesserung.
Also für 0,0001 Genauigkeit braucht es also ca. eine Milliarde Durchläufe... um da eine Stelle mehr dazu zu bekommen, wären es 100 Milliarden ... Nur um so paar Größenordnungen zu skizzieren ... (Also ganz wichtig: Hier geht es nur um Größenordnungen um die grobe Erwartung zu verdeutlichen ...

Um den Punkt BigDecimal vs. double noch zu berücksichtigen: Die Genauigkeit reicht da bis um 15 Stellen ... Und wenn Du auf ungefähr 10 Stellen genau werden willst, dann wären das über 10 hoch 21 Durchgänge ... Ich denke, das zeigt, wie schlecht diese Annäherung von pi ist.

 

[Elija7906]

Also der Algorithmus ist recht ungenau. Du brauchst also nicht einmal BigDecimal oder so, denn die Genaugigkeit nimmt viel zu langsam zu um dies zu rechtfertigen.

Schauen wir einfach einmal im Wikipedia:

Monte Carlo integration - Wikipedia

en.wikipedia.org

Da findest Du dann unter anderem eine Herleitung, die die Genauigkeit angibt ... und die ist abhängig von 1 / Wurzel(N). Also 100 Mal mehr Berechnungen geben nur 1/10 Verbesserung.
Also für 0,0001 Genauigkeit braucht es also ca. eine Milliarde Durchläufe... um da eine Stelle mehr dazu zu bekommen, wären es 100 Milliarden ... Nur um so paar Größenordnungen zu skizzieren ... (Also ganz wichtig: Hier geht es nur um Größenordnungen um die grobe Erwartung zu verdeutlichen ...

Um den Punkt BigDecimal vs. double noch zu berücksichtigen: Die Genauigkeit reicht da bis um 15 Stellen ... Und wenn Du auf ungefähr 10 Stellen genau werden willst, dann wären das über 10 hoch 21 Durchgänge ... Ich denke, das zeigt, wie schlecht diese Annäherung von pi ist.

Ok Danke habs Verstanden. Werde das besser umsetzen. Das Mathe soooo komplex ist wusste ja keine xd😅.

 

[Kaltblueter]

Das Mathe soooo komplex ist wusste ja keine xd

Eigentlich ist Monte-Carlo ein sehr einfaches (und verständliches) Verfahren, um PI annähernd zu bestimmen.

 

[Kaltblueter]

Ich hab dir das mal ins Reine gebracht... Leider ist das Verfahren eher ineffizient:

import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;
import java.util.concurrent.ThreadLocalRandom;

public class MonteCarloPi {
  public static void main(String[] args) {
    System.out.println("Monte Carlo Pi (100000, 100)");
    System.out.println(calculatePi(100_000, 100));
    System.out.println(Math.PI);
  }

  public static BigDecimal calculatePi(int iterations, int precision) {
    if (iterations <= 0) {
      throw new IllegalArgumentException("iterations must be greater than zero");
    }
    if (precision <= 0) {
      throw new IllegalArgumentException("precision must be greater than zero");
    }

    long pointsInsideCircle = 0;
    ThreadLocalRandom random = ThreadLocalRandom.current();
    for (int i = 0; i < iterations; i++) {
      double x = random.nextDouble();
      double y = random.nextDouble();
      if (x * x + y * y <= 1.0) {
        pointsInsideCircle++;
      }
    }

    MathContext mathContext = new MathContext(precision, RoundingMode.HALF_UP);
    return BigDecimal.valueOf(pointsInsideCircle)
        .multiply(BigDecimal.valueOf(4))
        .divide(BigDecimal.valueOf(iterations), mathContext);
  }
}

 

[Oneixee5]

Ich hab dir das mal ins Reine gebracht... Leider ist das Verfahren eher ineffizient:

import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;
import java.util.concurrent.ThreadLocalRandom;

public class MonteCarloPi {
  public static void main(String[] args) {
    System.out.println("Monte Carlo Pi (100000, 100)");
    System.out.println(calculatePi(100_000, 100));
    System.out.println(Math.PI);
  }

  public static BigDecimal calculatePi(int iterations, int precision) {
    if (iterations <= 0) {
      throw new IllegalArgumentException("iterations must be greater than zero");
    }
    if (precision <= 0) {
      throw new IllegalArgumentException("precision must be greater than zero");
    }

    long pointsInsideCircle = 0;
    ThreadLocalRandom random = ThreadLocalRandom.current();
    for (int i = 0; i < iterations; i++) {
      double x = random.nextDouble();
      double y = random.nextDouble();
      if (x * x + y * y <= 1.0) {
        pointsInsideCircle++;
      }
    }

    MathContext mathContext = new MathContext(precision, RoundingMode.HALF_UP);
    return BigDecimal.valueOf(pointsInsideCircle)
        .multiply(BigDecimal.valueOf(4))
        .divide(BigDecimal.valueOf(iterations), mathContext);
  }
}

Wie oben schon schon mal erklärt:
Wenn du der Methode precision = 100 (100 signifikante Stellen) übergibst, rechnet BigDecimal im letzten Schritt zwar intern mit einer gigantischen Scheingenauigkeit von 100 Stellen. Das Ergebnis wird dadurch aber kein bisschen genauer, da die mathematische Basis (die iterations in double) diese Genauigkeit gar nicht hergibt.
Nach den ersten 3 bis 4 Stellen besteht das Ergebnis nur noch aus "Zufallsrauschen".
Für die Monte-Carlo-Methode machen hohe precision-Werte über 15 keinen Sinn, da ein Java-double ohnehin nur 64-Bit (ca. 15–17 signifikante Dezimalstellen) abspeichern kann.

 

[Kaltblueter]

Für effiziente Verfahren nimmt man i.d.R. den Chudnovsky-Algorithmus oder den Gauss-Salamin-Algo:



Kann ich implementieren, falls Bedarf besteht?

 

[Oneixee5]

Selbst wenn Java-Zahlen unendlich viele Nachkommastellen speichern könnten, scheitert die Präzision an der Monte-Carlo-Methode selbst.
Monte Carlo ist ein statistisches Zufallsverfahren. Die Genauigkeit steigt extrem langsam – und zwar mit der Quadratwurzel der Iterationen.

Für 3 korrekte Nachkommastellen brauchst du etwa 100.000 bis 1.000.000 Durchläufe.
Für 6 korrekte Nachkommastellen brauchst du bereits rund 1.000.000.000.000 (1 Billion) Durchläufe.
Für 100 korrekte Nachkommastellen bräuchtest du eine Anzahl an Iterationen mit über 200 Nullern. Das würde selbst auf allen Computern der Erde zusammen länger dauern, als das Universum existiert.

 

[Oneixee5]

Das ist die maximal zulässige Genauigkeit... das hat mit Scheingenauigkeit nichts zu tun. Also spar dir deine Bissigkeit.

Es stimmt: In deiner finalen Formel (pointsInsideCircle * 4 / iterations) taucht die Variable double scheinbar gar nicht auf. Du rechnest dort nur mit long (Ganzzahlen), die du in ein BigDecimal umwandelst.
Die Ungenauigkeit von double kommt aber schon früher rein, nämlich direkt in der Schleife bei der Bestimmung von pointsInsideCircle.

double "zerstört" hier die Genauigkeit:
Deine Schleife entscheidet bei jedem Durchlauf, ob ein Punkt im Kreis liegt oder nicht:

double x = random.nextDouble();
double y = random.nextDouble();
if (x * x + y * y <= 1.0) {
  pointsInsideCircle++;
}

 

[KonradN]

Sorry, aber:

• Wo ist BigDecimal als Vorgabe gesetzt? Der TE hat es verwendet in seinem Code und es wurde deutlich gemacht, dass es Quatsch ist.
• Ein moderner Rechner könnte tausende Jahre rechnen und würde mit dem Genauigkeitsbereich von double nicht verlassen. Daher ist es einfach nur Unsinn, da so einen Code zu schreiben, wie er angeboten hat.