Logarithme binaire

Cet article est une ébauche concernant l’analyse.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Consultez la liste des tâches à accomplir en page de discussion.

En mathématiques, le logarithme binaire (log₂ n) est le logarithme de base 2. C’est la fonction réciproque de la fonction puissance de deux : $x \mapsto 2 x$ . Le logarithme binaire de $x$ est la puissance à laquelle le nombre 2 doit être élevé pour obtenir la valeur $x$ , soit : $\operatorname {lb} (x)=a\Leftrightarrow x=2^{a}$ .

Ainsi, le logarithme binaire de 1 est 0, le logarithme binaire de 2 est 1, le logarithme binaire de 4 est 2, le logarithme binaire de 8 est 3.

La notation mathématique moderne du logarithme binaire d'un nombre $n$ s'écrit $log 2 n$ ^[1]. Cependant, d'autres notions ont été utilisées dans la littérature, selon les domaines et champs d'application.

Certains auteurs écrivent le logarithme binaire comme $lg n$ ^[2]^,^[3], comme dans The Chicago Manual of Style^[4]. Donald Knuth met cette notation au crédit de Edward Reingold^[5] mais elle était utilisée en théorie de l'information et informatique avant les années d'activité de Reingold^[6]^,^[7]. Le logarithme binaire est aussi écrit $log n$ avec une note préliminaire que la base du logarithme est $2$ ^[8]^,^[9]^,^[10]. Une autre notation souvent utilisée pour cette fonction (notamment dans la littérature scientifique allemande) est $ld n$ ^[11]^,^[12]^,^[13] du latin logarithmus dualis^[11] ou logarithmus dyadis^[11], mais la norme ISO 80000-2^[14] indique que $log 2 (x)$ devrait être symbolisé par $lb (x)$ . En fait, en analyse de la complexité des algorithmes, dans un contexte dans lequel il n'y a pas de confusion possible, il est parfois simplement noté $log (x)$ ^[15]^,^[16]^,^[17]^,^[18].

Musique

En musique, le logarithme binaire intervient dans la formule permettant de déterminer la valeur en cents d’un intervalle. Cette valeur est égale en cents à 1200 fois le logarithme binaire du rapport de fréquence de l'intervalle. Le rapport de fréquence d'un intervalle est le quotient de la fréquence la plus haute sur la fréquence la plus basse de cet intervalle. Un cent vaut exactement un centième de demi-ton.

Informatique

En informatique, l'orientation binaire du matériel fait souvent du logarithme binaire le plus facile à calculer et le plus précis, les autres en étant dérivés.

En effet, soit $(e; m)$ la représentation virgule flottante binaire d'un nombre réel non nul $x$ , où $e$ est un entier porteur de l'ordre de grandeur, et $m$ un significande tel que $1 \leq | m | < 2$ . Alors, si $m > 0$ :

x=m\times 2^{e}\ {\textrm {entraine}}\ \operatorname {lb} (x)=e+\operatorname {lb} (m).

et le calcul de $lb(x)$ se ramène ainsi au domaine [1 ; 2[.

Par exemple, $10 = 2 3 \times 1,25$ , $lb(10) = 3 + lb(1,25)$ .

où $lb(1,25)$ est la partie fractionnaire du logarithme cherché.

Chaque bit de $lb(1,25)$ peut se calculer directement bit à bit à l'aide des relations :

{\displaystyle \operatorname {lb} (1)=0\quad

Quand on cherche un nouveau bit de $x$ (0 < $x$ < 2) :

on élève x au carré
- si $x$ vaut au moins 2, on note 1, on divise $x$ par 2 et on poursuit ;
- sinon, on note 0 et on poursuit.

Ainsi

{\begin{aligned}\operatorname {lb} (10)&=11_{2}+\operatorname {lb} (1,25)\\&=11_{2}+\operatorname {lb} (1,5625)/2\\&=11,0_{2}+\operatorname {lb} (2,44140625)/4\\&=11,01_{2}+\operatorname {lb} (1,220703125)/4\\&=11,01_{2}+\operatorname {lb} (1,490116119)/8\\&=11,010_{2}+\operatorname {lb} (2,220446049)/16\\&=11,0101_{2}+\operatorname {lb} (1,110223025)/16\\&=11,01010_{2}+\operatorname {lb} (1,232611)/32\\&=11,010100_{2}+\operatorname {lb} (1,519330)/64\\&=11,010100_{2}+\operatorname {lb} (2,308)/128\\&=\dots \end{aligned}}

Or 11,0101001₂ = 3,3203125, et on a déjà 2^3,3203125 = 9,9888...

Remarque

La valeur $lb(10) = 3,32...$ entraîne que le codage binaire d'un entier décimal occupera au moins 3,32 bits par chiffre décimal, soit 4 bits pour un chiffre, 7 bits pour 2 chiffres et 10 bits pour 3 chiffres (ou tranche de 3 chiffres).

Références

↑ C'est le cas dans Encyclopedia of Mathematics et The Princeton Companion to Mathematics.
↑ (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press and McGraw-Hill, 2001, 2^e éd. (1^re éd. 1990) (ISBN 0-262-03293-7), p. 34, 53–54.
↑ (en) Robert Sedgewick et Kevin Daniel Wayne, Algorithms, Addison-Wesley Professional, 2011 (ISBN 978-0-321-57351-3, lire en ligne), p. 185.
↑ (en) The Chicago Manual of Style, University of Chicago Press, 2003, 25^e éd., p. 530.
↑ (en) Donald E. Knuth, Fundamental Algorithms, vol. 1, Addison-Wesley Professional, coll. « The Art of Computer Programming », 1997 (ISBN 978-0-321-63574-7), p. 11. La même notation se trouve dans la 2^e édition de 1973 du même ouvrage (p. 23) mais sans donner le nom de Reingold.
↑ (en) Ernesto Trucco, « A note on the information content of graphs », The Bulletin of mathematical biophysics, vol. 18, n^o 2,‎ 1956, p. 129–135 (DOI 10.1007/BF02477836, MR 0077919).
↑ (en) John N. Mitchell, « Computer multiplication and division using binary logarithms », IRE Transactions on Electronic Computers, vol. EC-11, n^o 4,‎ 1962, p. 512–517 (DOI 10.1109/TEC.1962.5219391, Bibcode 1962IRTEC..11..512M).
↑ (en) Georges Fiche et Gerard Hebuterne, Mathematics for Engineers, John Wiley & Sons, 2013 (ISBN 978-1-118-62333-6, lire en ligne), p. 152 :
« In the following, and unless otherwise stated, the notation $log x$ always stands for the logarithm to the base $2$ of $x$ »
.
↑ (en) Thomas M. Cover et Joy A. Thomas, Elements of Information Theory, John Wiley & Sons, 2012 (ISBN 978-1-118-58577-1, lire en ligne), p. 33 :
« Unless otherwise specified, we will take all logarithms to base $2$ »
.
↑ (en) Michael T. Goodrich et Roberto Tamassia, Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley & Sons, 2002, p. 23 :
« One of the interesting and sometimes even surprising aspects of the analysis of data structures and algorithms is the ubiquitous presence of logarithms ... As is the custom in the computing literature, we omit writing the base $b$ of the logarithm when $b = 2$ . »
1 2 3 (de) Hans Jörg Tafel, Einführung in die digitale Datenverarbeitung [« Introduction au traitement numérique des données »], Munich, Carl Hanser Verlag, 1971, 20–21 p. (ISBN 3-446-10569-7).
↑ (de) Ulrich Tietze et Christoph Schenk, Halbleiter-Schaltungstechnik, Springer Verlag, 1999 (ISBN 3-540-64192-0, lire en ligne ), 1370
↑ (en) Friedrich L. Bauer, Origins and Foundations of Computing: In Cooperation with Heinz Nixdorf MuseumsForum, Springer Science & Business Media, 2009 (ISBN 978-3-642-02991-2, lire en ligne), p. 54.
↑ ISO 80000-2:2009. Organisation internationale de normalisation. Consulté le 18 janvier 2012.
↑ Voir par exemple Complexité des algorithmes. Sylvain Perifel. 2014, sous licence Creative Commons, p.xvi.
↑ For DIN 1302 see (de) Brockhaus Enzyklopädie in zwanzig Bänden [« Encyclopédie Brockhaus en vingt volumes »], vol. 11, Wiesbaden, F.A. Brockhaus, 1970 (ISBN 978-3-7653-0000-4), p. 554.
↑ For ISO 31-11 see Ambler Thompson, Guide for the Use of the International System of Units (SI) — NIST Special Publication 811, 2008 Edition — Second Printing, NIST, mars 2008 (lire en ligne [PDF]), p. 33.
↑ For ISO 80000-2 see « Quantities and units – Part 2: Mathematical signs and symbols to be used in the natural sciences and technology », dans International Standard ISO 80000-2, 1, 1^er décembre 2009 (lire en ligne [PDF]), p. 18.

Logarithme binaire

Musique

Informatique

Remarque

Références

Voir aussi

Related Articles