Нахождение цифр PI с помощью Монте-Карло

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

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

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

Answer 2

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

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

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

Answer 3

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