Ich kann nicht meinen Fehler in diesem Schema Programm berechnet PI finden

Question

Ich mache ein Experiment Monte Carlo eine Annäherung von PI zu berechnen. Von SICP:

  

Das Verfahren Monte Carlo besteht aus   Auswahl Probe Experimente zufällig   aus einem großen Satz und dann machen   Abzüge auf der Grundlage der   Wahrscheinlichkeiten abgeschätzt aus   Tabelliermaschinen die Ergebnisse dieser   Experimente. Zum Beispiel können wir   annähernd mit der Tatsache, dass   6 / pi ^ 2 ist die Wahrscheinlichkeit, dass zwei   Zahlen zufällig ausgewählt werden keine   Faktoren gemeinsam; das heißt, dass ihre   größte gemeinsame Teiler wird 1 sein   erhalten die Annäherung an, wir   eine große Anzahl von Experimenten durchführen.   Bei jedem Versuch wählten wir zwei   Zahlen nach dem Zufallsprinzip und führen Sie einen Test   zu sehen, ob ihre GCD 1. Die Fraktion ist   Mal, dass der Test bestanden ist, gibt   uns unsere Schätzung von 6 / pi ^ 2, und aus   Diese erhalten wir unsere Annäherung an   pi.

Aber wenn ich mein Programm laufe ich erhalte Werte wie 3,9 ...

Hier ist mein Programm:

(define (calculate-pi trials)
  (define (this-time-have-common-factors?)
    (define (get-rand)
      (+ (random 9999999999999999999999999999999) 1))
    (= (gcd (get-rand) (get-rand)) 1))
  (define (execute-experiment n-times acc)
    (if (> n-times 0)
        (if (this-time-have-common-factors?)
            (execute-experiment (- n-times 1) acc)
            (execute-experiment (- n-times 1) (+ acc 1)))
        acc))
  (define n-success (execute-experiment trials 0))
  (define prob (/ n-success trials))
  (sqrt (/ 6 prob)))

Mein Dolmetscher ist MIT / GNU 7.7.90

Vielen Dank für jede Hilfe.

Answer 1

Nun, Ihre Frage direkt zu beantworten, können Sie die if-Anweisung nach hinten haben; es sollte so sein.

    (if (this-time-have-common-factors?)
        (execute-experiment (- n-times 1) (+ acc 1)
        (execute-experiment (- n-times 1) acc))

So Sie 1 sind die Berechnung - 6 / π ² in der Grenze als die Anzahl der Versuche gegen unendlich. Dies ergibt "pi" = sqrt (6 / (1 - 6 / π ² )) = sqrt (6π ² / (π ² - 6)) = 3,911).

---

Lassen Sie uns einen Schritt hier zurück, obwohl, und schauen, was die Monte-Carlo-Methode hat für uns bei dieser Berechnung (Hinweis: erwarten sehr langsame Konvergenz Wie oft sind Sie es ausgeführt wird.?) ...

Jeder Versuch entweder gibt uns 0 oder 1, mit einer Wahrscheinlichkeit von p = 6 / π ² . Dies ist ein Beispiel für einen Bernoulli-Prozess , die für die Anzahl von 1en m hat in einer Reihe von Studien n , ein Binomialverteilung .

Betrachten ρ = m / n, der Bruchteil der Zeit des gemeinsamen Divisoren-Test bestanden. Dies hat einen Mittelwert von p und eine Varianz von p (1-p) / n, oder std dev σ _ρ = sqrt (p (1-p) / n). Für n = 10000, sollten Sie einen std Entwickler von 0,00488 erwarten. 95% der Zeit, die Sie innerhalb von 2 std Devs des mittleren sein werden, und 5% außen 2 std devs oder zwischen 0,5982 und 0,6177 der Zeit Sie sein. So eine Schätzung von π von dieser Methode, da n = 10000, zwischen 3.117 und 3.167 95% der Zeit und außerhalb dieses Bereichs 5% der Zeit sein wird.

Wenn Sie die Anzahl der Versuche um 100 erhöhen wollen, die um den Faktor 10 und die Schätzung von π wird verengt zwischen 3,1391 und 3,1441 mit 95% std Entwickler reduziert.

Monte-Carlo-Methoden sind schön für eine grobe Schätzung, aber sie brauchen viele Versuche für eine genaue Antwort, und in der Regel einen Punkt des abnehmenden Ertrags erreichen.

Nicht, dass dies ein fruchtlos Weg ist nur ungefähre pi, seien sich des Problems bewusst.

Answer 2

Ich finde meine Fehler. Dank an alle. Ich war die erfolgreichen Fälle an der falschen Stelle erhöht wird.

Der korrigierte Code lautet:

(define (calculate-pi trials)
  (define (this-time-have-common-factors?)
    (define (get-rand)
      (+ (random 9999999) 1))
    (= (gcd (get-rand) (get-rand)) 1))
  (define (execute-experiment n-times acc)
    (if (> n-times 0)
        (if (this-time-have-common-factors?)
            (execute-experiment (- n-times 1) (+ acc 1))
            (execute-experiment (- n-times 1) acc))
        acc))
  (define n-success (execute-experiment trials 0))
  (define prob (/ n-success trials))
  (sqrt (/ 6 prob)))