Scindage binaire

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche concernant les mathématiques et l’informatique.

Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

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.

[modifier] 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.^[1] 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.