Encontrar dígitos PI usando Monte Carlo

Question

Eu tentei muitos algoritmos para encontrar p usando Monte Carlo. Uma das soluções (em Python) é o seguinte:

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

A parte triste é que, mesmo com 1000000000 a precisão é muito ruim ( 3.141 ... ).

Esta é a máxima precisão deste método pode oferecer? A razão que eu escolher Monte Carlo foi que é muito fácil de quebrá-lo em partes paralelas. Existe um outro algoritmo para p que é fácil de quebrar em pedaços e calcular?

Answer 1

Este é um exemplo clássico de Monte Carlo. Mas se você está tentando quebrar o cálculo do pi em partes paralelas, por que não usar uma série infinita e deixar que cada núcleo ter um intervalo, em seguida, somar os resultados que você vá?

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

Answer 2

Seu erro fracionário passa sqrt(N)/N = 1/sqrt(N), Portanto, esta é uma maneira muito ineficiente para obter uma estimativa precisa. Esse limite é definido pela natureza estatística da medição e não pode ser derrotado.

Você deve ser capaz de obter cerca de dígitos floor(log_10(N))/2-1 de boa precisão para N joga. Talvez -2 apenas para ser seguro ...

Mesmo que ele assume que você estiver usando uma RNG real ou um bom PRNG suficiente.

Answer 3

Use um gerador de números aleatórios quasi ( http://www.nag.co. uk / IndustryArticles / introduction_to_quasi_random_numbers.pdf ) em vez de um RNG pseudo padrão. números aleatórios quase cobrir a área de integração (o que você está fazendo é uma integração MC) de forma mais uniforme do que números aleatórios pseudo, dando uma melhor convergência.