Binary splitting

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 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},

où 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 est utilisé dans les logiciels les plus rapides pour calculer des constantes comme par exemple π et e avec une grande précision. Il est aussi utilisé pour l'évaluation de fonctions spéciales.

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

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Scindage binaire ».

Wikimedia Foundation. 2010.

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

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Binary splitting — In mathematics, binary splitting is a technique for speeding up numerical evaluation of many types of series with rational terms. In particular, it can be used to evaluate hypergeometric series at rational points. Given a series where pn and qn… …   Wikipedia

  • Binary — means composed of two parts or two pieces . It contrasts with Unary, Ternary, Quaternary, and so on.Binary may also refer to:* Binary option, also known as digital option OR all or nothing option * Binary numeral system, a representation for… …   Wikipedia

  • binary fission — n. asexual reproduction in protists by a splitting of the cell into two approximately equal parts …   English World dictionary

  • binary fission — noun : reproduction of a cell by division into two approximately equal parts the binary fission of protozoans * * * Biol. fission into two organisms approximately equal in size. Cf. multiple fission. [1895 1900] * * * binary fission noun… …   Useful english dictionary

  • Computational complexity of mathematical operations — The following tables list the running time of various algorithms for common mathematical operations. Here, complexity refers to the time complexity of performing computations on a multitape Turing machine.[1] See big O notation for an explanation …   Wikipedia

  • List of mathematics articles (B) — NOTOC B B spline B* algebra B* search algorithm B,C,K,W system BA model Ba space Babuška Lax Milgram theorem Baby Monster group Baby step giant step Babylonian mathematics Babylonian numerals Bach tensor Bach s algorithm Bachmann–Howard ordinal… …   Wikipedia

  • Multiplication algorithm — A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are in use. Efficient multiplication algorithms have existed since the advent of the decimal system.… …   Wikipedia

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

  • Быстрые алгоритмы — Значимость предмета статьи поставлена под сомнение. Пожалуйста, покажите в статье значимость её предмета, добавив в неё доказательства значимости по частным критериям значимости или, в случае если частные критерии значимости для… …   Википедия

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

Share the article and excerpts

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