División binaria

En matemáticas , la descomposición binaria es una técnica para acelerar la evaluación numérica de muchos tipos de series con términos racionales. En particular, se puede utilizar para evaluar series hipergeométricas en puntos racionales.

Dada una serie

${\displaystyle S(a,b)=\sum _{n=a}^{b}{\frac {p_{n}}{q_{n}}}}$

donde p _n y q _n son enteros, el objetivo de la división binaria es calcular los enteros P ( a , b ) y Q ( a , b ) tales que

${\displaystyle S(a,b)={\frac {P(a,b)}{Q(a,b)}}.}$

La división consiste en establecer m = [( a  + b )/2] y calcular recursivamente P ( a , b ) y Q ( a , b ) a partir de P ( a , m ), P ( m , b ), Q ( a , m ) y Q ( m , b ). Cuando a y b están suficientemente cerca, P ( a , b ) y Q ( a , b ) se pueden calcular directamente a partir de p _a ...p _b y q _a ...q _b . 

La división binaria requiere más memoria que la suma directa término a término, pero es asintóticamente más rápida, ya que se reducen los tamaños de todos los subproductos. Además, mientras que el método de evaluación más simple para una serie racional utiliza una división de precisión completa para cada término, la división binaria solo requiere una división final con la precisión deseada; esto no solo es más rápido, sino que también elimina convenientemente los errores de redondeo. Para aprovechar al máximo este método, se deben utilizar técnicas de multiplicación rápidas como la multiplicación de Toom-Cook y el algoritmo de Schönhage-Strassen ; con la multiplicación ordinaria O ( n² ), la división binaria puede no generar ninguna mejora de velocidad o incluso ser más lenta ^.

Dado que todas las subdivisiones de la serie se pueden calcular de forma independiente entre sí, la división binaria se presta bien a la paralelización y al establecimiento de puntos de control .

En un sentido menos específico, la división binaria también puede referirse a cualquier algoritmo de divide y vencerás que siempre divide el problema en dos mitades.

• Xavier Gourdon y Pascal Sebah. Método de división binaria.
• David V. Chudnovsky y Gregory V. Chudnovsky. Álgebra computacional al servicio de la física matemática y la teoría de números . En Computers and Mathematics (Stanford, CA, 1986) , págs.  09–232, Dekker, Nueva York, 1990.
• Bruno Haible, Thomas Papanikolaou. Evaluación rápida de precisión múltiple de series de números racionales . Artículo distribuido con el código fuente de la biblioteca CLN .
• Lozier, DW y Olver, FWJ Evaluación numérica de funciones especiales. Matemáticas de la computación 1943–1993: Medio siglo de matemáticas computacionales, W. Gautschi, eds., Proc. Sympos. Applied Mathematics, AMS, v.48, pp.  79–125 (1994).
• Bach, E. La complejidad de las constantes de la teoría de números. Info. Proc. Letters, N 62, pp.  145–152 (1997).
• Borwein, JM, Bradley, DM y Crandall, RE Estrategias computacionales para la función zeta de Riemann. J. of Comput. Appl. Math., vol. 121, n.º 1-2, págs.  247-296 (2000).
• Karatsuba, EA Evaluación rápida de funciones trascendentales. (Inglés. Original en ruso) Probl. Inf. Transm. 27, No.4, 339-360 (1991); traducción de Probl. Peredachi Inf. 27, No.4, 76–99 (1991).
• Ekatherina Karatsuba. Algoritmos rápidos y el método FEE