Calcolo di pi greco
# Calcolo di pi greco

Esistono diversi metodi per il calcolo di π (pi greco).

## Metodi standard

### Cerchi

π può essere ottenuto a partire da un cerchio di raggio ed area noti, essendo l'area data dalla formula:

    $A=\pi r^{2}\,\!,$

che permette di calcolare esplicitamente π:

    $\pi =A/r^{2}.$

Se un cerchio di raggio r viene disegnato con il suo centro nel punto (0,0), qualsiasi punto la cui distanza dall'origine sia minore o uguale a r sarà all'interno del cerchio. Il teorema di Pitagora dà il quadrato della distanza di qualsiasi punto (x,y) dall'origine:

    $d^{2}=x^{2}+y^{2}.$

Il "foglio da disegno" matematico è costruito pensando quadrati di lato unitario centrati attorno ad ogni punto (x,y), dove x e y sono gli interi compresi fra -r e r. I quadrati i cui centri siano dentro o sulla circonferenza possono essere contati verificando per ciascuno se

    $x^{2}+y^{2}\leq r^{2}.$

Il numero di punti che soddisfano la condizione approssima allora l'area del cerchio, che può essere usata per calcolare un'approssimazione di $\pi$.

La formula può essere scritta come:

    $\pi \approx {\frac {1}{r^{2}}}\sum _{x=-r}^{r}\;\sum _{y=-r}^{r}{\Big1{\hbox{ se }}x^{2}+y^{2}\leq r^{2},\;0{\hbox{ altrimenti}}{\Big )}.$

In altre parole, si comincia scegliendo un valore di r; si considerano tutti i punti (x,y) per i quali sia x sia y siano interi compresi fra −r e r. Partendo da zero, si aggiunge uno per ciascun punto la cui distanza dall'origine (0,0) sia minore o uguale a r. Al termine, si divide la somma così ottenuta — rappresentante l'area del cerchio di raggio r — per l'intero $r^2$ per trovare un'approssimazione di π. Si ottengono migliori approssimazioni per valori maggiori di r.

Per esempio, se r è 5, allora i punti considerati sono:

    (−5,5)(−4,5)(−3,5)(−2,5)(−1,5)(0,5)(1,5)(2,5)(3,5)(4,5)(5,5) (−5,4)(−4,4)(−3,4)(−2,4)(−1,4)(0,4)(1,4)(2,4)(3,4)(4,4)(5,4) (−5,3)(−4,3)(−3,3)(−2,3)(−1,3)(0,3)(1,3)(2,3)(3,3)(4,3)(5,3) (−5,2)(−4,2)(−3,2)(−2,2)(−1,2)(0,2)(1,2)(2,2)(3,2)(4,2)(5,2) (−5,1)(−4,1)(−3,1)(−2,1)(−1,1)(0,1)(1,1)(2,1)(3,1)(4,1)(5,1) (−5,0)(−4,0)(−3,0)(−2,0)(−1,0)(0,0)(1,0)(2,0)(3,0)(4,0)(5,0) (−5,−1)(−4,−1)(−3,−1)(−2,−1)(−1,−1)(0,−1)(1,−1)(2,−1)(3,−1)(4,−1)(5,−1) (−5,−2)(−4,−2)(−3,−2)(−2,−2)(−1,−2)(0,−2)(1,−2)(2,−2)(3,−2)(4,−2)(5,−2) (−5,−3)(−4,−3)(−3,−3)(−2,−3)(−1,−3)(0,−3)(1,−3)(2,−3)(3,−3)(4,−3)(5,−3) (−5,−4)(−4,−4)(−3,−4)(−2,−4)(−1,−4)(0,−4)(1,−4)(2,−4)(3,−4)(4,−4)(5,−4) (−5,−5)(−4,−5)(−3,−5)(−2,−5)(−1,−5)(0,−5)(1,−5)(2,−5)(3,−5)(4,−5)(5,−5)

I 12 punti (0,±5), (±5,0), (±3,±4), (±4,±3) sono esattamente sulla circonferenza, e ci sono 69 punti completamente all'interno, così l'area approssimata vale 81, e π vale in questa approssimazione 3.24. Risultati per diversi r sono riportati nella tabella seguente:

| r | Area | Approssimazione di π |
| - | - | - |
| 2 | 13 | 3.25 |
| 3 | 29 | 3.22222 |
| 4 | 49 | 3.0625 |
| 5 | 81 | 3.24 |
| 10 | 317 | 3.17 |
| 20 | 1257 | 3.1425 |
| 100 | 31417 | 3.1417 |
| 1000 | 3141549 | 3.141549 |

In modo simile, gli algoritmi più complessi riportati di seguito coinvolgono calcoli ripetuti di qualche tipo, e portano ad approssimazioni migliori al crescere del numero di calcoli.

### Frazioni continue

A parte la rappresentazione in termini di frazioni continue [3; 7, 15, 1, 292, 1, 1, …], che non mostra alcuno schema riconoscibile, π ha molte rappresentazioni come frazione continua generalizzata, incluse le seguenti:

    $\pi =3+{\cfrac {1}{6+{\cfrac {9}{6+{\cfrac {25}{6+{\cfrac {49}{6+{\cfrac {81}{6+{\cfrac {121}{\ddots \,}}}}}}}}}}}}$
    ${\frac {4}{\pi }}=1+{\cfrac {1}{3+{\cfrac {4}{5+{\cfrac {9}{7+{\cfrac {16}{9+{\cfrac {25}{11+{\cfrac {36}{13+{\cfrac {49}{\ddots }}}}}}}}}}}}}}$

(Altre rappresentazioni si trovano presso The Wolfram Functions Site.)

### Trigonometria

La serie di Gregory-Leibniz

    ${\frac {\pi }{4}}={\frac {1}{1}}-{\frac {1}{3}}+{\frac {1}{5}}-{\frac {1}{7}}+\cdots +{\frac {(-1)^{i}}{2i+1}}+\cdots$

è la serie di potenze di arctan(x) nel caso particolare $x=1$; la sua velocità di convergenza è troppo lenta perché sia di interesse pratico. Comunque, la serie converge molto più rapidamente per piccoli valori di $x$; si giunge quindi a formule dove $\pi$ si ricava come somma di tangenti razionali, come quella di John Machin:

    ${\frac {\pi }{4}}=4\arctan {\frac {1}{5}}-\arctan {\frac {1}{239}}$

Formule per $\pi$ di questo tipo sono note come formule di tipo Machin.

Considerando un triangolo equilatero ed osservando che

    $\sin \left({\frac {\pi }{6}}\right)=^{1}\!\!/\!_{2}$

si trova che:

    $\pi =3\sum _{n=0}^{\infty }{\frac {(2n)!}{n!^{2}(2n+1)2^{4n}}}=3+{\frac {1}{8}}+{\frac {9}{640}}+{\frac {15}{7168}}+...$

### L'algoritmo Salamin-Brent

L'algoritmo di Salamin-Brent fu scoperto indipendentemente da Richard Brent e Eugene Salamin nel 1975. Permette di calcolare $\pi$ fino a N cifre significative in un tempo proporzionale a N log(N) log(log(N)), molto più velocemente delle formule trigonometriche.

## Metodi di estrazioni di cifre

### Formula BBP (base 16)

La formula BBP (Bailey-Borwein-Plouffe) per calcolare $\pi$ fu scoperta nel 1995 da Simon Plouffe. La formula calcola $\pi$ in base 16 senza bisogno di calcolare le cifre precedenti ("estrazione di cifre").

    $\pi =\sum _{n=0}^{\infty }\left({\frac {4}{8n+1}}-{\frac {2}{8n+4}}-{\frac {1}{8n+5}}-{\frac {1}{8n+6}}\right)\left({\frac {1}{16}}\right)^{n}$

### Miglioramento di Bellard (base 64)

Una formula alternativa per il calcolo di $\pi$ in base 64 venne derivato da Fabrice Bellard; tale metodo permette di calcolare cifre il 43% più velocemente.

    $\pi ={\frac {1}{2^{6}}}\sum _{n=0}^{\infty }{\frac {(-1)^{n}}{2^{10n}}}\left(-{\frac {2^{5}}{4n+1}}-{\frac {1}{4n+3}}+{\frac {2^{8}}{10n+1}}-{\frac {2^{6}}{10n+3}}-{\frac {2^{2}}{10n+5}}-{\frac {2^{2}}{10n+7}}+{\frac {1}{10n+9}}\right)$

### Estensione ad una base arbitraria

Nel 1996, Simon Plouffe ha ottenuto un algoritmo per calcolare cifre di $\pi$ in una base arbitraria in un tempo $O(n^3log(n)^3).$

### Miglioramento usando la formula di Gosper

Nel 1997, Fabrice Bellard ha migliorato la formula di Plouffe per l'estrazione di cifre in una base arbitraria, riducendo il tempo di calcolo a $O(n^2).$

## Progetti

### Pi Hex

Il progetto Pi Hex, terminato nel 2000, ha calcolato cifre binarie di $\pi$ su una rete distribuita impiegando parecchie centinaia di computer.

### Background pi

Ispirato da Pi Hex and Project Pi, Background Pi cerca di calcolare cifre decimali sequenzialmente. È in fase di sviluppo una nuova versione, che gestisca diversi progetti con un'interfaccia più amichevole rispetto al BOINC.

