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.
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 ) tales que
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 , metro ) y Q ( metro , segundo ). Cuando a y b están lo 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 por término, pero es asintóticamente más rápida ya que se reducen los tamaños de todos los subproductos que ocurren. 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 sólo una división final con la precisión objetivo; esto no sólo es más rápido, sino que elimina convenientemente los errores de redondeo. Para aprovechar al máximo el esquema, se deben utilizar técnicas de multiplicación rápida como la multiplicación de Toom-Cook y el algoritmo de Schönhage-Strassen ; con la multiplicación ordinaria de O ( n 2 ), la división binaria puede no generar 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 los 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.
