可以蒙特卡洛圆周率计算中使用的世界纪录？ [英] Can a monte carlo pi calculation be used for world record?

问题描述

我有这样的随机函数来计算圆周率蒙特卡罗风格：

I have this random function to calculate pi monte carlo style:

max=10000000;
format long;

in = 0;
tic
for k=1:max
    x = rand();
    y = rand();
    if sqrt(x^2 + y^2) < 1
        in = in + 1;
    end
end

toc
calc_pi = 4*in/max 
epsilon = abs(pi - calc_pi)

calcPi(100000000);

如果我能遍历这个10e100时候，会这样算法世界纪录的竞争？如果是的话我怎么能找到重复的将给予的N位数是多少？

If I could iterate this 10e100 times, could this algorithm compete with world record ? if so how can I find the number of iteration will give the N-digit?

推荐答案

这是一个很好的锻炼计算圆周率，但它可能是一个非常低效的。一些言论：

This is a nice exercise for calculating pi, but it is probably a very inefficient one. Some remarks:

• 我的统计数据之前，我有我的咖啡生疏，但我想用 1 /开方（n_guess）错误秤。为了得到n个数字，你需要的错误10 ^（ - N），所以你需要大约（10 ^ N）^ 2 随机猜测。如果你这样做1e100的猜测，因为你提出，你只会得到50圆周率数字的数量级！由此迭代的数目是所需的位数，这是可怕的慢一些exponentional功能。一个好的算法是线性的，也许在你需要的位数。

• My statistics are rusty before I had my coffee, but I guess the error scales with 1 / sqrt(n_guess). To get N digits, you need an error of 10^(-N), so you would need roughly (10^N)^2 random guesses. If you would do 1e100 guesses, as you proposed, you would only get on the order of 50 digits of pi! The number of iteration is thus some exponentional function of the number of required digits, which is horribly slow. A good algorithm is maybe linear in the number of digits you want.

通过所需要的大量猜测，你要开始质疑你的随机数生成器的质量。

With the large number of guesses required, you have to start questioning the quality of your random number generator.

您算法将通过浮点错误到1E-16左右的限制。计算圆周率的数字需要某种任意precision数字格式。

Your algorithm will be limited by floating-point errors to 1e-16 or so. Calculating digits of pi requires some sort of arbitrary precision number format.

要加快你的算法，你可以离开了的sqrt（）。

To speed up your algorithm, you can leave out the sqrt().

不要使用一个名为最高变量，这将覆盖现有的功能。使用n_guess左右。

Don't use a variable called max, this overwrites an existing function. Use n_guess or so.

快速和肮脏的测试，以证明我的理论（在咖啡）：

Quick and dirty test to prove my theory (after coffee):

pie = @(n) 4 * nnz(rand(n,1).^2 + rand(n, 1).^2 < 1) / n;
ntrial = round(logspace(1, 8, 100));
pies = arrayfun(pie, ntrial);

loglog(ntrial, abs(pies - pi), '.k', ntrial, ntrial.^-.5, '--r')
xlabel('ntrials')
ylabel('epsilon')
legend('Monte Carlo', '1 / sqrt(ntrial)')

这篇关于可以蒙特卡洛圆周率计算中使用的世界纪录？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！