Scindage binaire

Soit la somme

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

où p_n, q_n, a et b sont des entiers[1]. Le scindage binaire permet de calculer les entiers P(a, b) and Q(a, b) tels que

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

Le scindage consiste à diviser l'intervalle [a, b] en deux intervalles égaux : [a, m] et [m, b] (où m = [(a+b)/2] est le milieu du segment) et à calculer récursivement P(a, b) et Q(a, b) à partir de P(a, m), P(m, b), Q(a, m) et Q(m, b).

Quand les deux bornes de l'intervalle de la sous-division [i, j] sont suffisamment proches, le calcul de P(i, j) et Q(i, j) est effectué directement à partir des p_i...p_j et q_i...q_j.

Le scindage binaire demande plus de mémoire que la sommation directe mais est asymptotiquement plus rapide puisque les tailles des sous-sommes sont beaucoup plus petites. De plus, les méthodes naïves d'évaluation de séries rationnelles utilisent une division multi-précision (division coûteuse) pour chacun des termes de la série, alors que le scindage binaire n'utilise qu'une seule division multiprécision. Cela réduit aussi les erreurs d'arrondi.

Avec des algorithmes de multiplication classique, qui multiplient 2 nombres à n chiffres en O(n²) opérations, le scindage binaire n'apporte aucun gain d'efficacité. Cependant, si des algorithmes de multiplication rapide tels que Toom-Cook ou Schönhage-Strassen sont utilisés, le scindage est plus efficace que la somme naïve.

Les sous-sommes sont indépendantes les unes des autres et donc le calcul par scindage binaire se prête bien au calcul parallèle.

Le scindage binaire désigne aussi un cas particulier des algorithmes diviser pour régner dans lesquels la division a lieu en deux parties égales.

• Xavier Gourdon et Pascal Sebah. Binary splitting method

• Arbre de produits