Não consigo encontrar o meu erro neste programa Scheme for PI calcular

Question

Estou fazendo um experimento de Monte Carlo para calcular uma aproximação da PI. De SICP:

O método de Monte Carlo é composto por escolher experimentos amostra ao acaso a partir de um grande conjunto e tomada de seguida deduções sobre a base da probabilidades estimada a partir de tabular os resultados daqueles experimentos. Por exemplo, nós podemos aproximar usando o fato de que 6 / pi ^ 2 é a probabilidade de que dois inteiros escolhidos aleatoriamente não terá Factores em comum; isto é, que a sua maior divisor comum será 1. Para obter a aproximação, nós realizar um grande número de experiências. Em cada experimento que escolher dois inteiros aleatoriamente e realizar um teste para ver se o GCD é 1. A fração de vezes que o teste é passado dá -nos a nossa estimativa de 6 / pi ^ 2 e, a partir isso obtemos a nossa aproximação pi.

Mas quando eu executar o meu programa que eu obter valores como 3,9 ...

Aqui está o meu programa:

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

Meu intérprete é MIT / GNU 7.7.90

Obrigado por qualquer ajuda.

Answer 1

Bem, para responder sua pergunta diretamente, você tem as para trás se-afirmação; deve ser desta forma.

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

Então, você está calculando 1-6 / p ² no limite como o # de ensaios se aproxima do infinito. Este rendimento de "pi" = sqrt (6 / (1-6 / p ² )) = sqrt (6p ² / (p ² - 6)) = 3,911).

---

Vamos dar um passo para trás aqui, embora, e olhar para o que o método de Monte Carlo faz por nós com esse cálculo (dica: esperar a convergência muito lenta Quantas vezes você está executando-o.?) ...

Cada ensaio quer nos dá 0 ou 1, com uma probabilidade de p = 6 / p ² . Este é um exemplo de uma Bernoulli processo, que tem, para o número de um de m em um certo número de ensaios n , um binomial distribuição .

Considere ? = m / n, a fracção de vezes que passam o teste comuns-divisores. Isto tem um valor médio de p e uma variância de p (1-p) / n, ou Desv s _? = sqrt (p (1-p) / n). Para n = 10000, você deve esperar um dev std de 0,00488. 95% do tempo você será dentro de 2 devs std da média, e 5% do tempo você vai estar fora 2 devs std, ou entre 0,5982 e 0,6177. Assim, uma estimativa de p a partir deste método, dado n = 10000, irá estar compreendida entre 3,117 e 3,167 a 95% do tempo e fora desta gama de 5% do tempo.

Se você quiser aumentar o número de ensaios por 100, que reduz dev std por um fator de 10 e a estimativa de p se estreitou entre 3,1391 e 3,1441 com 95% de confiança.

métodos de Monte Carlo são agradáveis ??para uma estimativa aproximada mas eles precisam de lotes e lotes de ensaios para uma resposta precisa, e, geralmente, chegar a um ponto de retornos decrescentes.

Não que esta é uma maneira infrutífera de pi aproximada, basta estar ciente do problema.

Answer 2

eu encontrar o meu erro. Obrigado a todos. Eu estava incrementando os casos de sucesso no lugar errado.

O código corrigido é:

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