Scindage binaire

Le scindage binaire (en anglais binary splitting) est une méthode d'accélération du calcul de sommes avec des termes rationnels.

Le scindage binaire est par exemple utilisé pour l'évaluation de séries hypergéométriques en des points rationnels.

Le principe de base du scindage binaire consiste à diviser récursivement le domaine de sommation en petits groupes de rationnels à additionner, de simplifier les sommes de petits groupes (réduction au même dénominateur, élimination des facteurs communs) et d'itérer sur des groupes plus grands.

Fonctionnement

Soit la somme

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

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

$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.

Considérations algorithmiques

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.

Référence

• Xavier Gourdon et Pascal Sebah. Binary splitting method

Voir aussi

• Arbre de produits