Нахождение цифр 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) более равномерно, чем псевдослучайные числа, давая лучше конвергенция.