我无法在此Scheme计划中找到我的错误来计算PI

Question

我正在进行蒙特卡罗实验来计算PI的近似值.来自SICP:

蒙特卡罗方法包括从大型集合中随机选择样本实验,然后根据从这些实验的结果列表中估计的概率进行推论.例如,我们可以使用这样的事实来近似:6/pi ^ 2是随机选择的两个整数没有共同因素的概率; 也就是说,他们最大的公约数将是1.为了得到近似值,我们进行了大量的实验.在每个实验中,我们随机选择两个整数并进行测试以确定它们的GCD是否为1.测试通过的次数给出了我们对6/pi ^ 2的估计,并由此得到我们对pi的近似值.

但是当我运行我的程序时,我获得了3.9的值......

这是我的计划:

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

我的翻译是麻省理工学院/ GNU 7.7.90

谢谢你的帮助.

Answer 1

好吧,直接回答你的问题,你的if语句倒退了; 它应该是这样的.

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

6 /π -所以你计算1 ²在极限试验的#接近无穷大.这产生"PI"= SQRT(6 /(1 - 6 /π ²))= SQRT(6π ² /(π ² -6))= 3.911).

让我们在这里退后一步,然后看看蒙特卡罗方法对我们这个计算的作用(提示:期望收敛非常慢.你运行它多少次？)......

每个试验任一给我们0或1,以概率p = 6 /π ².这是一个的例子伯努利过程,其中有,为1的数米的试验次数Ñ,一个二项式分布.

考虑ρ= m/n,即通过除数检验的次数.这是一个具有平均p的值,p(1-p)的方差/ n或标准偏差σ _ρ = SQRT(P(1-P)/ N).对于n = 10000,您应该期望std dev为0.00488.95%的时间你将在平均值的2 std devs内,5%的时间你将在2 std devs之外,或者在0.5982和0.6177之间.因此,给定n = 10000时,该方法的π估计值将在3.117和3.167之间95%的时间内,并且在该范围的5%的时间之外.

如果你想将试验次数增加100,那么std dev会减少10倍,π的估计值会在3.1391和3.1441之间变窄,置信度为95%.

蒙特卡罗方法很适合粗略估计,但是他们需要大量的试验来获得准确的答案,并且通常会达到收益递减的程度.

并不是说这是一种近似pi的无效方法,只要注意这个问题.