Recherche de chiffres PI en utilisant Monte Carlo

Question

J'ai essayé de nombreux algorithmes pour trouver π en utilisant Monte Carlo. L'une des solutions (en Python) est la suivante:

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 

Le plus triste est que même avec la précision 1000000000 est très mauvais (3,141 ...).

Est-ce la précision maximale que cette méthode peut offrir? La raison pour laquelle j'ai choisi Monte Carlo, c'est qu'il est très facile de le casser en parties parallèles. Existe-t-il un autre algorithme pour π qui soit facile à décomposer et à calculer?

Answer 1

Ceci est un exemple classique de Monte Carlo. Mais si vous essayez de diviser le calcul de pi en parties parallèles, pourquoi ne pas simplement utiliser une série infinie et laisser chaque noyau prendre une portée, puis additionner les résultats au fur et à mesure?

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

Answer 2

Votre erreur fractionnaire passe par sqrt(N)/N = 1/sqrt(N), donc c'est un moyen très inefficace d'obtenir une estimation précise. Cette limite est fixée par la nature statistique de la mesure et ne peut pas être battue.

Vous devriez pouvoir obtenir environ floor(log_10(N))/2-1 chiffres de bonne précision pour N jette. Peut-être -2 juste pour être sûr ...

Même à cela, il suppose que vous utilisez un vrai RNG ou un PRNG assez bon.

Answer 3

utiliser un générateur de nombres quasi aléatoires (http://www.nag.co.uk/IndustryArticles/introduction_to_quasi_random_numbers.pdf) au lieu d'une norme pseudo RNG. Les nombres quasi aléatoires couvrent la zone d'intégration (ce que vous faites est une intégration MC) plus uniformément que les nombres pseudo-aléatoires, donnant une meilleure convergence.