Fòrmula de Bailey-Borwein-Plouffe

La fòrmula de Bailey-Borwein-Plouffe (o fòrmula BBP) permet calcular l'enèsim dígit de π en base 2 (o 16) sense necessitat de trobar els precedents, d'una manera ràpida i utilisant molt poc espai de memòria en la computadora. Simon Plouffe junt en David Bailey i Peter Borwein varen trobar esta fòrmula el 19 de setembre de 1995 usant un programa informàtic cridat PSLQ que busca relacions entre número entero.^[1]

La fòrmula BBP

$π = \sum_{k = 0}^{\infty} \frac{1}{1 6^{k}} (\frac{4}{8 k + 1} - \frac{2}{8 k + 4} - \frac{1}{8 k + 5} - \frac{1}{8 k + 6})$

La demostració d'esta fòrmula es troba més avall.

Us de la fòrmula per a calcular els decimals del número π

A continuació es mostra el càlcul de l'enèsim dígit hexadecimal de π.

Primer es deu observar que el dígit ubicat en la posició N+1 de π en base 16 és el mateix que el primer dígit hexadecimal de 16^Nπ. En efecte, com en la base 10, multiplicar un número en base 16 per 16 equival a desplaçar la menge decimal un lloc cap a la dreta. D'esta manera, multiplicant per 16^N, la menge es desplaça N llocs cap a la dreta. El problema original es reduïx al càlcul del primer dígit de 16^Nπ. Usant la fòrmula BBP:

1 6^{N} π = \sum_{k = 0}^{\infty} 1 6^{N - k} (\frac{4}{8 k + 1} - \frac{2}{8 k + 4} - \frac{1}{8 k + 5} - \frac{1}{8 k + 6})

El càlcul dels primers dígits hexadecimals a la dreta de la menge d'este número no és senzill per dos raons: el número és molt gran i la suma és infinita.

Supongam que $S_{N} (a) = \sum_{k = 0}^{\infty} \frac{1 6^{N - k}}{8 k + a}$ . El càlcul dels primers dígits hexadecimals de S_N(a) permetrà obtindre els de 16^Nπ, a través de la relació:

1 6^{N} π = 4 S_{N} (1) - 2 S_{N} (4) - S_{N} (5) - S_{N} (6)

Descomponent la suma S_N(a) en dos:

S_{N} (a) = \sum_{k = 0}^{\infty} \frac{1 6^{N - k}}{8 k + a} = \sum_{k = 0}^{N - 1} \frac{1 6^{N - k}}{8 k + a} + \sum_{k = N}^{\infty} \frac{1 6^{N - k}}{8 k + a} = A_{N} (a) + B_{N} (a)

es poden calcular A_N(a) i B_N(a) en forma independent.

Càlcul de B_N(a)

$B_{N} (a) = \sum_{k = N}^{\infty} \frac{1 6^{N - k}}{8 k + a}$

Encara que es tracta d'una suma infinita, és molt fàcil de calcular, perque els seus térmens són menuts i decreixen ràpidament.

En efecte, el primer terme de la suma és: $b_{N} = \frac{1}{8 N + a}$ . Si es busca l'enèsim dígit hexadecimal de π (N = 1 000 000 000 per eixemple), el primer terme és molt menor que 1.
Ademés, cada terme té un zero més a la dreta de la menge que el precedent, perque per a k ≥ N, b_k > 16 b_k+1:

\frac{b_{k}}{b_{k + 1}} = \frac{1 6^{N - k}}{1 6^{N - (k + 1)}} \frac{8 (k + 1) + a}{8 k + a} = 16 (1 + \frac{8}{8 k + a}) ⟶ 1 6^{+}

.

Finalment, la suma B_N(a) és de la forma (en el pijor cas):

$B_{N} = 0, * * * * * * * * * * . . . .$

+ 0, 0 * * * * * * * * * . . .

+ 0, 00 * * * * * * * * . . .

+ 0, 000 * * * * * * * * . . .

Per lo tant, per a obtindre B_N(a) en una precisió de P sifres darrere de la menge, és suficient calcular els P primers térmens de la suma, agregant-se alguns térmens més per a evitar errors que apareixen en realisar càlculs en valors aproximats.

Aixina, es calcula: ${B_{N}}^{'} (a) = \sum_{k = N}^{N + P + 10} \frac{1 6^{N - k}}{8 k + a}$

Com esta suma solament posseïx una chicoteta cantitat de térmens, el temps que insume esta operació és insignificant per a una computadora.

Càlcul de A_N(a)

$A_{N} (a) = \sum_{k = 0}^{N - 1} \frac{1 6^{N - k}}{8 k + a}$

El problema per al càlcul de A_N(a) és que els primers térmens són molt grans (N sifres de base 16 abans de la menge). No obstant, de la mateixa manera que les primeres sifres darrere de la menge, no importa la part sancera, que també és gran. Per lo tant, pugues "eliminar-se" usant aritmètica modular.

Tota la dificultat es reduïx a trobar la part fraccionaria de $\frac{1 6^{N - k}}{8 k + a}$ . Per a això realisem la divisió sancera de 16^N-k per 8k+a:

$\exists q \in ℤ, \exists r < 8 k + a, 1 6^{N - k} = q (8 k + a) + r$

Aixina $\frac{1 6^{N - k}}{8 k + a} = q + \frac{r}{8 k + a}$

$\frac{r}{8 k + a}$ és menor que 1, per lo tant, és la part fraccional de $\frac{1 6^{N - k}}{8 k + a}$ .

I $\frac{r}{8 k + a} = \frac{1 6^{N - k} (\mod 8 k + a)}{8 k + a}$

Aixina, es calcula: ${A_{N}}^{'} (a) = \sum_{k = 0}^{N - 1} \frac{1 6^{N - k} (\mod 8 k + a)}{8 k + a}$ .

Utilisant el método de l'exponenciación binaria, $1 6^{N - k} (\mod 8 k + a)$ es calcula ràpidament (en un temps d'eixecució d'O(log₂(N-k)).

Conclusió

Al cap i a la fi, per a obtindre els primers dígits de π base 16 (o 2), es deuen calcular els primers dígits de:

$π_{N} = 4 {S_{N}}^{'} (1) - 2 {S_{N}}^{'} (4) - {S_{N}}^{'} (5) - {S_{N}}^{'} (6)$

en ${S_{N}}^{'} (a) = \sum_{k = 0}^{N - 1} \frac{1 6^{N - k} (\mod 8 k + a)}{8 k + a} + \sum_{k = N}^{N + P + 10} \frac{1 6^{N - k}}{8 k + a}$ .

Vore també

Referències

↑
The Quest for Pi
- Archivat el 27 de setembre de 2011 archivat en Wayback Machine. (en anglés)

Referències

Este artícul conté una traducció derivada de «Fórmula de Bailey-Borwein-Plouffe» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[1] The Quest for Pi
Archivat el 27 de setembre de 2011 archivat en Wayback Machine. (en anglés)

[2] Archivat el 27 de setembre de 2011 archivat en Wayback Machine. (en anglés)

[1]

La fòrmula BBP

Us de la fòrmula per a calcular els decimals del número π

Càlcul de BN(a)

Càlcul de AN(a)

Conclusió

Vore també

Referències

Referències

Càlcul de B_N(a)

Càlcul de A_N(a)