Encontrar dígitos PI utilizando Monte Carlo

Question

He probado muchos algoritmos para encontrar π usando Monte Carlo. Una de las soluciones (en Python) es la siguiente:

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

La parte triste es que incluso con 1000 millones la precisión es muy mala ( 3.141 ... ).

¿Es esta la máxima precisión de este método puede ofrecer? La razón por la que elegí Monte Carlo es que es muy fácil de romper en partes paralelas. ¿Hay algún otro algoritmo para π que es fácil de romper en pedazos y calcular?

Answer 1

Este es un ejemplo clásico de Monte Carlo. Pero si usted está tratando de romper el cálculo de pi en partes paralelas, ¿por qué no utilizar una serie infinita y dejar que cada núcleo toma un rango, entonces sumar los resultados a medida que avanza?

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

Answer 2

Su error relativo pasa sqrt(N)/N = 1/sqrt(N), así que esta es una manera muy ineficiente para obtener una estimación precisa. Este límite se establece por la naturaleza estadística de la medición y no puede ser batido.

Usted debe ser capaz de obtener unos dígitos floor(log_10(N))/2-1 de buena precisión para N lanza. Tal vez -2 sólo para estar seguro ...

Incluso a que asume que está utilizando un generador de números aleatorios real o una buena suficiente PRNG.

Answer 3

Utilice un generador de números aleatorios cuasi ( http://www.nag.co. uk / IndustryArticles / introduction_to_quasi_random_numbers.pdf) en lugar de un pseudo RNG estándar. números aleatorios cuasi cubren el área de integración (lo que está haciendo es una integración MC) de manera más uniforme que los números pseudo-aleatorios, dando una mejor convergencia.