Ich kann meinen Fehler in diesem Scheme-Programm nicht finden, um PI

Question

zu berechnen Ich mache ein Monte-Carlo-Experiment, um eine Approximation von PI zu berechnen. Von SICP:

Das Verfahren Monte Carlo besteht aus Probe Experimente zufällig aus einem großen Satz auswählen und dann Abzüge auf der Grundlage der Wahrscheinlichkeiten geschätzt von machen die Ergebnisse dieser Experimente Tabelliermaschinen. Zum Beispiel können wir approximieren mit der Tatsache, dass 6/pi^2 ist die Wahrscheinlichkeit, dass zwei Integer zufällig ausgewählt werden keine gemeinsame Faktoren haben; das heißt, dass ihr größter gemeinsamer Teiler 1 sein wird. Um die Approximation zu erhalten, führen wir eine große Anzahl von Experimenten durch. In jedem Versuch wählen wir zwei ganze Zahlen zufällig und führen Sie einen Test zu sehen, ob ihre GCD 1. Der Anteil Mal ist, dass der Test gibt uns übergeben wird unsere Schätzung von 6/pi^2, und von dieser wir erhalten unsere Annäherung an pi.

Aber wenn ich mein Programm laufe ich Werte wie 3.9 erhalten ...

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

Dank für jede Hilfe.

Answer 1

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

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

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

---

Lassen Sie uns hier wieder, wenn auch einen Schritt, und schauen, was das Verfahren für uns Monte Carlo hat bei dieser Berechnung (Hinweis: sehr langsame Konvergenz erwarten Wie oft haben Sie es laufen.?) ...

Jeder Versuch gibt uns entweder 0 oder 1, mit der Wahrscheinlichkeit p = 6/ . Dies ist ein Beispiel für eine Bernoulli process, die für die Anzahl von 1 m in einer Reihe von Versuchen n, eine binomial distribution hat.

Betrachten Sie ρ = m/n, der Bruchteil von Zeiten, die den Common-Divisors-Test bestehen. Dieses a 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 eine Std-Entwicklung von 0,00488 erwarten. 95% of the time you will be within 2 std devs of the mean, und in 5% der Fälle sind Sie außerhalb von 2 std devs oder zwischen 0,5982 und 0,6177. So wird eine Schätzung von π von dieser Methode, gegeben n = 10000, zwischen 3,117 und 3,167 95% der Zeit und außerhalb dieses Bereichs 5% der Zeit sein.

Wenn Sie die Anzahl der Versuche um 100 erhöhen möchten, reduziert das Standard-Dev um einen Faktor von 10 und der Schätzwert von π wird zwischen 3,1391 und 3,1441 mit 95% Konfidenz verengt.

Monte-Carlo-Methoden sind für eine grobe Schätzung, aber sie brauchen viel und eine Menge Versuche für eine genaue Antwort, und erreichen in der Regel einen Punkt der abnehmenden Renditen.

Nicht, dass dies eine fruchtlose Möglichkeit ist, pi zu approximieren, sei dir des Problems bewusst.

Answer 2

Ich finde meinen Fehler. Danke an alle. Ich habe die erfolgreichen Fälle an der falschen Stelle inkrementiert.

Der korrigierte Code ist:

(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)))