Algoritmo de espiga

Algoritmo para calcular el valor de un número trascendental

Un algoritmo de espiga es un algoritmo para calcular el valor de un número trascendental (como π o e ) que genera los dígitos del número secuencialmente de izquierda a derecha, proporcionando una precisión creciente a medida que avanza el algoritmo. Los algoritmos de espiga también apuntan a minimizar la cantidad de almacenamiento intermedio requerido. El nombre proviene del sentido de la palabra "espiga" para un grifo o válvula que controla el flujo de un líquido. Los algoritmos de espiga pueden contrastarse con algoritmos que almacenan y procesan números completos para producir aproximaciones sucesivamente más precisas al trascendental deseado.

El interés en los algoritmos de espiga fue estimulado en los primeros días de las matemáticas computacionales por las restricciones extremas en la memoria, y un algoritmo de este tipo para calcular los dígitos de e apareció en un artículo de Sale en 1968. ^[1] En 1970, Abdali presentó un algoritmo más general para calcular las sumas de series en las que las razones de los términos sucesivos pueden expresarse como cocientes de funciones enteras de posiciones de términos. Este algoritmo es aplicable a muchas series familiares para funciones trigonométricas, logaritmos y números trascendentales porque estas series satisfacen la condición anterior. ^[2] El nombre "algoritmo de espiga" parece haber sido acuñado por Stanley Rabinowitz y Stan Wagon , cuyo algoritmo para calcular los dígitos de π a veces se conoce como " el algoritmo de espiga para π ". ^[3]

El algoritmo spigot de Rabinowitz y Wagon es acotado , en el sentido de que se debe especificar de antemano el número de términos de la serie infinita que se procesará. El término "algoritmo de streaming" ^[4] indica un enfoque sin esta restricción. Esto permite que el cálculo se ejecute indefinidamente variando la cantidad de almacenamiento intermedio a medida que avanza el cálculo.

Una variante del método de la espiga utiliza un algoritmo que puede utilizarse para calcular un único dígito arbitrario del trascendental sin calcular los dígitos anteriores: un ejemplo es la fórmula de Bailey-Borwein-Plouffe , un algoritmo de extracción de dígitos para π que produce dígitos de base 16. El inevitable truncamiento de la serie infinita subyacente del algoritmo significa que la precisión del resultado puede estar limitada por la cantidad de términos calculados.

Ejemplo

Este ejemplo ilustra el funcionamiento de un algoritmo de espiga calculando los dígitos binarios del logaritmo natural de 2 (secuencia A068426 en la OEIS ) utilizando la identidad

${\displaystyle \ln(2)=\sum _{k=1}^{\infty }{\frac {1}{k2^{k}}}\,.}$

Para empezar a calcular dígitos binarios a partir, por ejemplo, del lugar 8 multiplicamos esta identidad por 2 ⁷ (ya que 7 = 8 − 1):

${\displaystyle 2^{7}\ln(2)=2^{7}\sum _{k=1}^{\infty }{\frac {1}{k2^{k}}}\,.}$

Luego dividimos la suma infinita en una "cara", en la que los exponentes de 2 son mayores o iguales a cero, y una "cola", en la que los exponentes de 2 son negativos:

${\displaystyle 2^{7}\ln(2)=\sum _{k=1}^{7}{\frac {2^{7-k}}{k}}+\sum _{k=8}^{\infty }{\frac {1}{k2^{k-7}}}\,.}$

Solo nos interesa la parte fraccionaria de este valor, por lo que podemos reemplazar cada uno de los sumandos en la "cabeza" por

${\displaystyle {\frac {2^{7-k}}{k}}{\bmod {1}}={\frac {2^{7-k}{\bmod {k}}}{k}}\,.}$

Calculando cada uno de estos términos y sumándolos a un total acumulado donde nuevamente solo conservamos la parte fraccionaria, tenemos:

Añadimos algunos términos en la "cola", observando que el error introducido al truncar la suma es menor que el término final:

Sumando la "cabeza" y los primeros términos de la "cola" obtenemos:

${\displaystyle 2^{7}\ln(2){\bmod {1}}\approx {\frac {64}{105}}+{\frac {37}{360}}=0.10011100\ldots _{2}+0.00011010\ldots _{2}=0.1011\ldots _{2}\,,}$

Por lo tanto, los dígitos binarios del octavo al undécimo en la expansión binaria de ln(2) son 1, 0, 1, 1. Nótese que no hemos calculado los valores de los primeros siete dígitos binarios; de hecho, toda la información sobre ellos ha sido descartada intencionalmente al usar aritmética modular en la suma "principal".

El mismo enfoque se puede utilizar para calcular dígitos de la expansión binaria de ln(2) a partir de una posición n arbitraria. El número de términos en la suma de la "cabeza" aumenta linealmente con n , pero la complejidad de cada término solo aumenta con el logaritmo de n si se utiliza un método eficiente de exponenciación modular . La precisión de los cálculos y los resultados intermedios y el número de términos tomados de la suma de la "cola" son todos independientes de n , y solo dependen del número de dígitos binarios que se están calculando: se puede utilizar aritmética de precisión simple para calcular alrededor de 12 dígitos binarios, independientemente de la posición inicial.

Referencias

1. Sale, AHJ (1968). "El cálculo de e con muchos dígitos significativos". The Computer Journal . 11 (2): 229–230. doi : 10.1093/comjnl/11.2.229 .
2. Abdali, S Kamal (1970). "Suma de series especiales con precisión arbitraria" (PDF) . Comunicaciones de la ACM . 13 (9): 570. doi :10.1145/362736.362756.
3. Rabinowitz, Stanley; Wagon, Stan (1995). "Un algoritmo de espiga para los dígitos de Pi" (PDF) . American Mathematical Monthly . 102 (3): 195–203. doi :10.2307/2975006. JSTOR  2975006 . Consultado el 8 de mayo de 2013 .
4. Gibbons, Jeremy (24 de mayo de 2004). "Algoritmos de espiga sin límites para los dígitos de Pi" (PDF) .

Lectura adicional

• Arndt, Jorg; Haenel, Christoph, π desatado , Springer Verlag, 2000.
• Weisstein, Eric W. "Algoritmo Spigot". MundoMatemático .