布丰针估算圆周率的实验接近圆周率,但并不能得到完美的值。

5

我正在处理一份非常典型的大学作业。我需要使用蒙特卡罗方法通过Buffon Needle来编写一个C程序以估算圆周率。我认为我的程序可以正常运行,但我从未正确地得到过π。它总是接近典型的3.14,但有时它是3.148910,有时是3.13894。这背后的原因是什么?我能做些什么使其更加“接近”准确值吗? (代码注释为波兰语,英文注释在括号内。)

#include <stdio.h>
#include <math.h>
#include <time.h>  
#include <stdlib.h>

int main(int argc, char **argv)
{
    srand(time(NULL));
    int i; //wprowadzenie licznika (counter)
    double l; // dlugosc igly (lenght of needle)
    double n;// liczba prob (number of trials)
    double L; // szerokosc miedzy liniami (width between lines)
    double x; // kat miedzy igla a normalna do linii (angle)
    double pi; // szacowana wartosc liczby pi (pi)
    double P=0; //ilość prób spełniających warunek styku igły z linią (ammount of trials that worked)
    double d; //odleglosc srodka igly od linii (distance between centre of needle and line)
    double y; //minimalizacja obliczeń 
    double  stosun; //stosunek wykonanych obliczeń (ammount of trials to ammount of succesfull trials)
    printf("Program szacuje wartosc liczby pi metoda Monte Carlo na podstawie Igly Buffona. Prosze Pamietac o:\n-Podaniu liczby prób jako wartości większej od zera i całkowitej\n-Podaniu długości igły mniejszej niż szerokości między liniami\n");
    printf("Prosze podac liczbe prob:\n");
    scanf("%lf", &n);
    printf("Prosze podac dlugosc igly:\n");
    scanf( "%lf", &l);
    printf("Prosze podac szerokość miedzy liniami:\n");
    scanf("%lf", &L);
    if (n <= 0.0 || l > L) 
    {
        printf("Nastąpił błąd wynikających z podania niepoprawnych danych\n");
        return 1;
    }
    printf("%f %f %f", n,l,L); //debuging midway

    for (i=0; i<n; i++)
{
    x = ((double)rand()/RAND_MAX)*3.1415;       // losowy kat w radianach (random angle in radians)

    d = ((double)rand()/RAND_MAX)*L/2;         // losowa dlugosc igly mniejsza niz odstep miedzy liniami (random needle lenght)

    y = (l/2) * sin (x);
printf("Próba%d\n", i);
    if (d<=y)                                    
    {
        P++;                                  
    }

}

stosun=n/P;
printf("Stosun %lf", stosun);
pi=stosun*2*l/L;
printf("liczba pi=%lf", pi); 
    return 0;
}

3
这是一个随机过程,因此结果永远不会完全正确。将其运行于更大的n值,以获得更高的准确度。 - Hong Ooi
1
你的典型n是多少?(顺便说一下,在任何情况下都不要将整数计数器的上限变为double!!) - The Vee
3
我建议先尝试将“3.1415”替换为“MATH_PI”。 - alain
2
  1. 变量名应指示用途或内容(最好两者兼备)。像l、n、L、x、p、d、y这样的变量名即使在当前上下文中也是毫无意义的。
  2. 代码应保持一致的缩进。在每个左花括号“{”后进行缩进,在每个右花括号“}”前取消缩进。
  3. 通过单个空行分隔代码块(for、if、else、while、do...while、switch、case、default)。
- user3629249
1
在编译时,始终启用所有警告,然后修复这些警告。(对于 gcc,至少使用:-Wall -Wextra -pedantic,我还使用:-Wconversion -std=gnu99)作为帮助,当不使用 main() 的参数时,请使用 int main( void ) 签名。 - user3629249
显示剩余6条评论
1个回答

7
蒙特卡罗模拟的方差往往非常大。(随着n的增加,它们会收敛到零误差,但速度非常慢。)您可以在此处阅读有关布丰针的详细信息。我想引起您的注意的是图中绘制了5个不同运行的1000次投掷的图形。检查每个图形,看起来该值已经收敛,但结果相当错误(并且每种情况都不同)。
在开始之前进行分析是很好的。上述来源中严格完成的误差估计约为5.6 / n。这是方差,所以要得到标准偏差,我们需要一个平方根,这使情况变得更糟。投掷1000次后,您可以预期π的误差约为0.073(尽管这可能因纯粹的机会而增加一倍,或者减少得多)。投掷一百万次后,它应该正确到±0.002左右。经过一亿次投掷,您可能会获得小数点后前三位正确,第四位或第五位出现第一个错误(很少)。我不知道您的n,但您得到的值似乎很符合典型值。 编辑:使用n = 1,000,000,它们为+3 σ和-1 σ>。
注意,有一个常见的误解是通过运行多次并平均结果(毕竟这些结果应该以上下波动的概率相同)来解决这个问题。当然,这种方法可行,但除了可以分发到多台机器上之外,没有任何优势。运行100个每次迭代一千次的模拟的误差与运行单个10万次迭代的模拟的误差完全相同。
因此,使估计更好的一个明显的方法是增加命中数。蒙特卡罗方法的一个重要优点是,各个样本通常是完全独立的,因此允许进行很好的并行化(OpenMP、向量化指令、GPU)。但第一步真正应该尝试让您的代码运行更快,以便将n增加一个数量级或更少的影响较小。例如,因为您知道从分析中精度永远不会真正惊人,所以可以使用float而不是double,后者在某些平台上速度快两倍。消除对sin的调用(如果您不需要π的值,这肯定更优雅)。每1000步左右输出您的摘要。
一个不太明显的方法是正确地进行分析,并注意如何减少方差中的分子(分母将是任何你做的东西)。如果我没弄错,当针的长度等于线之间的距离时,这个实验会跑得最好:小于此长度是次优的,而大于此长度会带来多重交叉,而这是你不想要的。也许还有其他方法可以通过改变角度和/或位置的分布来增强它。

我认为使用准随机数生成器可以将方差降至 1/n,而不是使用均匀采样时的 1/sqrt(n)。请参阅准蒙特卡罗方法 - Iwillnotexist Idonotexist
@IwillnotexistIdonotexist 很不错!我得尝试一下是否适用于体积计算(其中函数是特征函数),但听起来很有前途。 - The Vee
QMC是专门为了在多维空间中获得比均匀分布更好的整合而设计的。所需的随机数生成器属性是“低差异性”,而传统的PRNGs则没有这种属性。无论如何,我可能弄错了,方差是(log n)^s / n,其中s是空间的维度,但仍然比1/sqrt(n)快得多。 - Iwillnotexist Idonotexist

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接