Calcolo di pi greco

Da Wikipedia, l'enciclopedia libera.

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

Indice

1 Metodi standard
2 Metodi di estrazioni di cifre
3 Progetti
- 3.1 Pi Hex
- 3.2 Background pi
4 Note
5 Collegamenti esterni

[modifica] Metodi standard

[modifica] 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à la distanza di qualsiasi punto (x,y) dall'origine:

$d=\sqrt{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

$\sqrt{x^2+y^2} \le r.$

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

La formula può essere scritta come:

$\pi \approx \frac{1}{r^2} \sum_{x=-r}^{r} \; \sum_{y=-r}^{r} \Big(1\hbox{ se }\sqrt{x^2+y^2} \le r,\; 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² 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.

[modifica] 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 ^[1].)

[modifica] 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 $π$ 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 $π$ di questo tipo sono note come formule di tipo Machin.

Considerando un triangolo equilatero ed osservando che

$\sin(\frac{\pi}{6})=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} + ...$

[modifica] L'algoritmo Salamin-Brent

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

[modifica] Metodi di estrazioni di cifre

[modifica] Formula BBP (base 16)

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

$\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$

[modifica] Miglioramento di Bellard (base 64)

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

^[3]

$\pi=\frac{1}{2^6}\sum_{n=0}^\infty \frac{(-1)^n}{2^{10n}} (-\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})$

[modifica] Estensione ad una base arbitraria

Nel 1996, Simon Plouffe ha ottenuto un algoritmo per calcolare cifre di $π$ in una base arbitraria in un tempo O(n³log(n)³). ^[4]

[modifica] 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²). ^[5]

[modifica] Progetti

[modifica] Pi Hex

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

[modifica] Background pi

Ispirato da Pi Hex and Project Pi, Background Pi ^[6] 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.