Scindage binaire

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.

Sommaire

Fonctionnement

Soit la somme

S(a,b) = \sum_{n=a}^b \frac{p_n}{q_n},

pn, qn, 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 pi...pj et qi...qj.

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 multi-précision. Cela évite aussi les erreurs d'arrondi.

Avec des algorithmes de multiplication classique (en O(n2)), le scindage binaire n'apporte aucune efficacité, mais avec des algorithmes de multiplication rapide du genre Toom-Cook ou Schönhage-Strassen, 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.

Note

  1. Le rapport de pn par qn est donc rationnel.

Référence


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Scindage binaire de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Binary splitting — 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… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • BPSK — Phase shift keying Traduction terminée Phase shift keying → …   Wikipédia en Français

  • Binary-phase shift keying — Phase shift keying Traduction terminée Phase shift keying → …   Wikipédia en Français

  • Binary phase-shift keying — Phase shift keying Traduction terminée Phase shift keying → …   Wikipédia en Français

  • DPSK — Phase shift keying Traduction terminée Phase shift keying → …   Wikipédia en Français

  • Differential phase-shift keying — Phase shift keying Traduction terminée Phase shift keying → …   Wikipédia en Français

  • Modulation par sauts de phase — Phase shift keying Traduction terminée Phase shift keying → …   Wikipédia en Français

  • Phase-shift keying — Le Phase shift keying (ou PSK, soit « modulation par déplacement de phase ») désigne une famille de formes de modulations numériques qui ont toutes pour principe de véhiculer de l information binaire via la phase d un signal de… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”