Нахождение цифр PI с помощью Монте-Карло
-
13-09-2019 - |
Вопрос
Я испробовал множество алгоритмов поиска π с помощью Монте-Карло.Одно из решений (в 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...).
Это максимальная точность, которую может предложить этот метод?Причина, по которой я выбрал Монте-Карло, заключалась в том, что его очень легко разбить на параллельные части.Есть ли другой алгоритм для π, который легко разбить на части и вычислить?
Решение
Это классический пример Монте-Карло.Но если вы пытаетесь разбить вычисление числа Пи на параллельные части, почему бы просто не использовать бесконечную серию и не позволить каждому ядру принимать диапазон, а затем суммировать результаты по ходу дела?
Другие советы
Ваша дробная ошибка проходит sqrt(N)/N = 1/sqrt(N)
, Так что это очень неэффективный способ получить точную оценку.Этот предел установлен статистическим характером измерения и не может быть превышен.
Вы должны быть в состоянии добраться floor(log_10(N))/2-1
цифры хорошей точности для N
бросает.Может быть -2
просто ради безопасности...
Даже при этом предполагается, что вы используете настоящий ГСЧ или достаточно хороший ГПСЧ.
Используйте генератор квазислучайных чисел (http://www.nag.co.uk/IndustryArticles/introduction_to_quasi_random_numbers.pdf) вместо стандартного псевдоГСЧ.Квазислучайные числа покрывают область интегрирования (то, что вы делаете, это интеграция MC) более равномерно, чем псевдослучайные числа, обеспечивая лучшую сходимость.