En matemáticas , la divisió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.
Método
Dada una serie
donde p n y q n son números enteros, el objetivo de la división binaria es calcular los números enteros P ( a , b ) y Q ( a , b ) de manera que
La división consiste en establecer m = [( a + b ) / 2] y calcular de forma recursiva P ( a , b ) y Q ( a , b ) a partir de P ( a , m ), P ( m , b ), Q ( a , m ) y Q ( m , b ). Cuando una y b son lo suficientemente cerca, P ( un , b ) y Q ( un , b ) se puede calcular directamente a partir de p un ... p b y q un ... q b .
Comparación con otros métodos
La división binaria requiere más memoria que la suma directa término por término, pero es asintóticamente más rápida ya que se reducen los tamaños de todos los subproductos presentes. Además, mientras que el esquema de evaluación más ingenuo para una serie racional utiliza una división de precisión total para cada término de la serie, la división binaria requiere solo una división final en la precisión objetivo; esto no solo es más rápido, sino que elimina convenientemente los errores de redondeo. Para aprovechar al máximo el esquema, se deben utilizar algoritmos de multiplicación rápida como Toom – Cook y Schönhage – Strassen ; Con la multiplicación O ( n 2 ) ordinaria , la división binaria puede no producir ninguna aceleración o ser más lenta.
Dado que todas las subdivisiones de la serie se pueden calcular independientemente unas de otras, la división binaria se presta bien a la paralelización y al punto de control .
En un sentido menos específico, la división binaria también puede referirse a cualquier algoritmo de división y conquista que siempre divide el problema en dos mitades.
Referencias
- Xavier Gourdon y Pascal Sebah. Método de división binaria
- David V. Chudnovsky y Gregory V. Chudnovsky. Álgebra informática 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 multiprecisión rápida de series de números racionales . Papel 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. Simpos. Matemáticas aplicadas, AMS, v.48, págs. 79-125 (1994).
- Bach, E. La complejidad de las constantes teóricas de números. Info. Proc. Letters, N 62, págs. 145-152 (1997).
- Borwein, JM, Bradley, DM y Crandall, RE Estrategias computacionales para la función zeta de Riemann. J. de Computación. Apl. Math., V.121, N 1-2, págs. 247-296 (2000).
- Karatsuba, EA Evaluación rápida de funciones trascendentales. (Inglés. Original ruso) Probl. Inf. Transm. 27, N ° 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