Fórmula de Bailey-Borwein-Plouffe

${\displaystyle B_{N}(a)=\sum _{k=N}^{\infty }{\frac {16^{N-k}}{8k+a}}}$

Aunque se trata de una suma infinita, es muy fácil de calcular, porque sus términos son pequeños y decrecen rápidamente.

• En efecto, el primer término de la suma es: ${\displaystyle b_{N}={\frac {1}{8N+a}}}$. Si se busca el enésimo dígito hexadecimal de π (N = 1 000 000 000 por ejemplo), el primer término es mucho menor que 1.
• Además, cada término tiene un cero más a la derecha de la coma que el precedente, porque para k ≥ N, b_k > 16 b_k+1:

${\displaystyle {\frac {b_{k}}{b_{k+1}}}={\frac {16^{N-k}}{16^{N-(k+1)}}}{\frac {8(k+1)+a}{8k+a}}=16\left(1+{\frac {8}{8k+a}}\right)\longrightarrow 16^{+}}$.

Finalmente, la suma B_N(a) es de la forma (en el peor caso):

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

${\displaystyle +\ 0,0*********.\ .\ .\ }$

${\displaystyle +\ 0,00********.\ .\ .\ }$

${\displaystyle +\ 0,000********.\ .\ .\ }$

Por lo tanto, para obtener B_N(a) con una precisión de P cifras detrás de la coma, es suficiente calcular los P primeros términos de la suma, agregándose algunos términos más para evitar errores que aparecen al realizar cálculos con valores aproximados.

Así, se calcula: ${\displaystyle B_{N}'(a)=\sum _{k=N}^{N+P+10}{\frac {16^{N-k}}{8k+a}}}$

Como esta suma solo posee una pequeña cantidad de términos, el tiempo que insume esta operación es insignificante para una computadora.

${\displaystyle A_{N}(a)=\sum _{k=0}^{N-1}{\frac {16^{N-k}}{8k+a}}}$

El problema para el cálculo de A_N(a) es que los primeros términos son muy grandes (N cifras de base 16 antes de la coma). Sin embargo, al igual que las primeras cifras detrás de la coma, no importa la parte entera, que también es grande. Por lo tanto, puede "eliminarse" usando aritmética modular.

Toda la dificultad se reduce a hallar la parte fraccionaria de ${\displaystyle {\frac {16^{N-k}}{8k+a}}}$. Para ello realizamos la división entera de 16^N-k por 8k+a:

${\displaystyle \exists q\in \mathbb {Z} ,\exists r<8k+a,\ 16^{N-k}=q(8k+a)+r}$

Así ${\displaystyle {\frac {16^{N-k}}{8k+a}}=q+{\frac {r}{8k+a}}}$

${\displaystyle {\frac {r}{8k+a}}}$ es menor que 1, por lo tanto, es la parte fraccional de ${\displaystyle {\frac {16^{N-k}}{8k+a}}}$.

Y ${\displaystyle {\frac {r}{8k+a}}={\frac {16^{N-k}{\pmod {8k+a}}}{8k+a}}}$

Así, se calcula: ${\displaystyle A_{N}'(a)=\sum _{k=0}^{N-1}{\frac {16^{N-k}{\pmod {8k+a}}}{8k+a}}}$.

Utilizando el método de la exponenciación binaria, ${\displaystyle 16^{N-k}{\pmod {8k+a}}}$ se calcula rápidamente (con un tiempo de ejecución de O(log₂(N-k)).

Al fin y al cabo, para obtener los primeros dígitos de π base 16 (o 2), se deben calcular los primeros dígitos de:

${\displaystyle \pi _{N}=4\ S_{N}'(1)-2\ S_{N}'(4)-S_{N}'(5)-S_{N}'(6)}$

con ${\displaystyle S_{N}'(a)=\sum _{k=0}^{N-1}{\frac {16^{N-k}{\pmod {8k+a}}}{8k+a}}+\sum _{k=N}^{N+P+10}{\frac {16^{N-k}}{8k+a}}}$.

• B_n'(a) se calcula en complejidad lineal (O(1))
• A_n'(a) : utilizando el método de la exponenciación binaria, sus términos se calculan en O(log₂(n)). Así la suma de n términos, A_n'(a), se calcula en O(n*log₂(n)).

Así S_n'(a) se calcula en O(1)+O(n*log₂(n))=O(n*log₂(n)). Finalmente, π_n se calcula en 4*O(n*log₂(n))=O(n*log₂(n)).

Por lo tanto el tiempo de cálculo es proporcional a n*log₂(n), es decir, casi lineal.

La complejidad en el uso de memoria es constante, ya que solo se realizan sumas sucesivas de pequeños números (con una precisión de unos diez decimales es suficiente).

Fórmula original : ${\displaystyle \pi \ =\ \sum _{i=0}^{\infty }{\frac {1}{16^{i}}}\left({\frac {4}{8i+1}}-{\frac {2}{8i+4}}-{\frac {1}{8i+5}}-{\frac {1}{8i+6}}\right)}$

${\displaystyle \forall r\in \mathbb {C} \ \ \ \ \pi \ =\ \sum _{i=0}^{\infty }{\frac {1}{16^{i}}}\left({\frac {4+8r}{8i+1}}-{\frac {8r}{8i+2}}-{\frac {4r}{8i+3}}-{\frac {2+8i}{8i+4}}-{\frac {1+2r}{8i+5}}-{\frac {1+2r}{8i+6}}+{\frac {r}{8i+7}}\right)}$

${\displaystyle \pi {\sqrt {2}}\ =\ \sum _{i=0}^{\infty }{\frac {(-1)^{i}}{8^{i}}}\left({\frac {4}{6i+1}}+{\frac {1}{6i+2}}+{\frac {1}{6i+3}}\right)}$

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

${\displaystyle \pi ^{2}\ =\ {\frac {9}{8}}\ \sum _{i=0}^{\infty }{\frac {1}{64^{i}}}\left({\frac {16}{(6i+1)^{2}}}-{\frac {24}{(6i+2)^{2}}}-{\frac {8}{(6i+3)^{2}}}-{\frac {6}{(6i+4)^{2}}}-{\frac {1}{(6i+5)^{2}}}\right)}$

${\displaystyle \pi ^{2}\ =\ {\frac {2}{27}}\ \sum _{i=0}^{\infty }{\frac {1}{729^{i}}}\left({\frac {243}{(12i+1)^{2}}}-{\frac {405}{(12i+2)^{2}}}-{\frac {81}{(12i+4)^{2}}}-{\frac {27}{(12i+5)^{2}}}-{\frac {72}{(12i+6)^{2}}}-{\frac {9}{(12i+7)^{2}}}-{\frac {9}{(12i+8)^{2}}}-{\frac {5}{(12i+10)^{2}}}+{\frac {1}{(12i+11)^{2}}}\right)}$

La última fórmula permite hallar dígitos aislados de ${\displaystyle \pi ^{2}}$ en base 3 o 9.

${\displaystyle \pi \ =\ \sum _{i=0}^{\infty }{\frac {(-1)^{i}}{4^{i}}}\left({\frac {2}{4i+1}}+{\frac {2}{4i+2}}+{\frac {1}{4i+3}}\right)}$

${\displaystyle \pi \ =\ {\frac {1}{64}}\ \sum _{i=0}^{\infty }{\frac {(-1)^{i}}{2^{10i}}}\left(-{\frac {32}{4i+1}}-{\frac {1}{4i+3}}+{\frac {256}{10i+1}}-{\frac {64}{10i+3}}-{\frac {4}{10i+5}}-{\frac {4}{10i+7}}+{\frac {1}{10i+9}}\right)}$