Поиск цифр PI с использованием Monte Carlo

Question

Я пробовал много алгоритмов для поиска π с использованием Монте-Карло. Одно из решений (в Python) это:

def calc_PI(): 
    n_points = 1000000 
    hits = 0 

    for i in range(1, n_points): 
     x, y = uniform(0.0, 1.0), uniform(0.0, 1.0) 

     if (x**2 + y**2) <= 1.0: 
      hits += 1 

    print "Calc2: PI result", 4.0 * float(hits)/n_points 

Печально, что даже при 1000000000 точность ОЧЕНЬ плохо (3,141 ...).

Это максимальная точность, которую может предложить этот метод? Причина, по которой я выбираю Монте-Карло, заключалась в том, что ее легко разбить в параллельных частях. Есть ли еще один алгоритм для π, который легко разбить на куски и рассчитать?

Answer 1

Это классический пример Монте-Карло. Но если вы пытаетесь разбить вычисление pi на параллельные части, почему бы просто не использовать бесконечную серию и позволить каждому ядру принять диапазон, а затем суммировать результаты по мере продвижения?

http://mathworld.wolfram.com/PiFormulas.html

Answer 2

Ваша дробная ошибка заканчивается sqrt(N)/N = 1/sqrt(N), поэтому это очень неэффективный способ получения точной оценки. Этот предел задается статистическим характером измерения и не может быть избит.

Вы должны быть в состоянии получить около floor(log_10(N))/2-1 цифр хорошей точности для N бросков. Возможно, -2 просто для того, чтобы быть в безопасности ...

Даже при этом предполагается, что вы используете настоящий RNG или достаточно хороший PRNG.

Answer 3

Используйте квази генератор случайных чисел (http://www.nag.co.uk/IndustryArticles/introduction_to_quasi_random_numbers.pdf) вместо стандартного псевдо RNG. Квази-случайные числа охватывают область интеграции (то, что вы делаете, это интеграция с MC) более равномерно, чем псевдослучайные числа, что дает лучшую конвергенцию.