Trovare cifre PI con Monte Carlo

Question

Ho provato molti algoritmi per la ricerca di π usando Monte Carlo. Una delle soluzioni (in Python) è questa:

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 è che anche con 1000000000 la precisione è molto male ( 3.141 ... ).

E 'questa la massima precisione di questo metodo può offrire? La ragione per cui ho scelto di Monte Carlo è che è molto facile da rompere in parti parallele. C'è un altro algoritmo per π che è facile da rompere in pezzi e calcolare?

Answer 1

Questo è un classico esempio di Monte Carlo. Ma se si sta cercando di rompere il calcolo di pi greco in parti parallele, perché non utilizzare una serie infinita e lasciare che ogni core prendere una serie, poi riassumere i risultati, come si va?

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

Answer 2

Il tuo errore frazionale passa sqrt(N)/N = 1/sqrt(N), quindi questo è un modo molto inefficiente per ottenere una stima precisa. Tale limite è fissato dalla natura statistica della misura e non può essere battuto.

Si dovrebbe essere in grado di ottenere circa cifre floor(log_10(N))/2-1 di buona precisione per N getta. Forse -2 giusto per essere sicuri ...

Anche a quel assume che si sta utilizzando un vero e proprio generatore di numeri casuali o un buon abbastanza PRNG.

Answer 3

Usa un generatore di numeri casuali quasi ( http://www.nag.co. uk / IndustryArticles / introduction_to_quasi_random_numbers.pdf ) invece di una pseudo RNG standard. numeri casuali quasi coprire l'area di integrazione (quello che stai facendo è un integrazione MC) in modo più uniforme rispetto pseudo numeri casuali, dando una migliore convergenza.