Logaritmo binario

El logaritmo binario es el logaritmo en base 2. En otras palabras, el logaritmo binario de un número es la solución de la ecuación $b$ ${\ estilo de visualización 2 ^ {x} = b.}$

El logaritmo binario de un número real existe si, según ISO 31-11 , se denota por [1] o . Ejemplos: $b$ ${\ estilo de visualización b> 0.}$ ${\ estilo de visualización \ nombre del operador {lb} b,}$ ${\ estilo de visualización \ nombre del operador {lb} (b)}$ ${\ estilo de visualización \ registro _ {2} b}$

\nombre del operador{lb} 1=0;\, \nombre del operador{lb} 2=1;\, \nombre del operador{lb} 16=4

\operatorname{lb} 0{,}5=-1;\, \operatorname{lb} \frac{1}{256}=-8

Historia

Históricamente, los logaritmos binarios encontraron su primer uso en teoría musical cuando Leonhard Euler estableció que el logaritmo binario del cociente de las frecuencias de dos tonos musicales es igual al número de octavas que separa un tono de otro. Euler también publicó una tabla de los logaritmos binarios de los números enteros del 1 al 8, hasta siete decimales [2] [3] .

Con el advenimiento de la informática , quedó claro que se necesitaban logaritmos binarios para determinar el número de bits necesarios para codificar un mensaje . Otros campos en los que se suele utilizar el logaritmo binario incluyen la combinatoria , la bioinformática , la criptografía , los torneos deportivos y la fotografía . Muchos sistemas de programación comunes proporcionan una función estándar para calcular el logaritmo binario.

Propiedades algebraicas

La siguiente tabla asume que todos los valores son positivos [4] :

	Fórmula	Ejemplo
Trabajar	${\ estilo de visualización \ nombre del operador {lb} (xy) = \ nombre del operador {lb} (x) + \ nombre del operador {lb} (y)}$	$\operatorname {lb} (256)=\operatorname {lb} (16\cdot 16)=\operatorname {lb} (16)+\operatorname {lb} (16)=4+4=8$
cociente de división	$\operatorname {lb} \!\left({\frac {x}{y}}\right)=\operatorname {lb} (x)-\operatorname {lb} (y)$	$\operatorname{lb} \left(\frac{1}{32}\right) = \operatorname{lb} (1) - \operatorname{lb} (32) = 0 - 5 = -5$
La licenciatura	${\ estilo de visualización \ nombre del operador {lb} (x^{p}) = p \ nombre del operador {lb} (x)}$	$\nombre del operador {lb} (1024)=\nombre del operador {lb} (2^{10})=10\nombre del operador {lb} (2)=10$
Raíz	$\operatorname {lb} {\sqrt[{p}]{x}}={\frac {\operatorname {lb} (x)}{p}}$	$\nombre del operador{lb} \sqrt{8} = \frac{1}{2}\nombre del operador{lb} 8 = \frac{3}{2} = 1{,}5$

Hay una generalización obvia de las fórmulas anteriores para el caso en que se permiten variables negativas, por ejemplo:

\nombre del operador{lb} |xy| = \nombre del operador{lb} (|x|) + \nombre del operador{lb} (|y|),

\operatorname{lb} \!\left|\frac xy \right| = \nombre del operador{lb} (|x|) - \nombre del operador{lb} (|y|),

La fórmula para el logaritmo de un producto se puede generalizar fácilmente a un número arbitrario de factores:

\operatorname{lb}(x_1 x_2 \dots x_n) = \operatorname{lb} (x_1) + \operatorname{lb} (x_2) + \dots + \operatorname{lb} (x_n)

Relación entre logaritmos binarios, naturales y decimales :

\operatorname{lb} x \approx 1{,}442695 \ln x

\operatorname{lb} x \approx 3{,}321928 \lg x

La función de logaritmo binario

Si consideramos el número logarítmico como una variable, obtenemos la función de logaritmo binario: . Está definido para toda la gama de valores: . El gráfico de esta función a menudo se llama logaritmo , es el inverso de la función . La función es monótonamente creciente, continua y diferenciable dondequiera que se defina. Su derivada viene dada por la fórmula [5] : $y=\operatorname {lb} x$ ${\ estilo de visualización x> 0,}$ $E(y)=(-\infty ;+\infty )$ ${\ estilo de visualización y = 2 ^ {x}}$

\frac {d} {dx} \nombre del operador{lb} x = \frac {\nombre del operador{lb} e} {x}

El eje y es una asíntota vertical porque: $(x=0)$

\lim_{x \to 0+0} \operatorname{lb} x = - \infty

Aplicación

Teoría de la información

El logaritmo binario de un número natural le permite determinar el número de dígitos en la representación interna de la computadora ( bit ) de este número: $norte$ $segundo(N)$

b(N) = \lpiso \operatorname{lb} N \rpiso + 1

(los paréntesis indican la parte entera del número)

La entropía de la información es una medida de la cantidad de información , también basada en el logaritmo binario

Complejidad de los algoritmos recursivos

Estimación de la complejidad asintótica de algoritmos recursivos de divide y vencerás [6] tales como clasificación rápida , transformada rápida de Fourier , búsqueda binaria , etc.

Combinatoria

Si un árbol binario contiene nodos, entonces su altura no es menor que (la igualdad se logra si es una potencia de 2) [7] . En consecuencia, el número de Strahler-Filosofov para un sistema fluvial con afluentes no excede [8] . $norte$ $\ log _ {2} n$ $norte$ $norte$ ${\ estilo de visualización \ log _ {2} n + 1}$

La dimensión isométrica de un cubo parcial con vértices no es menor que el número de aristas del cubo, no mayor que la igualdad cuando el cubo parcial es un gráfico de hipercubo [9] . $norte$ ${\ estilo de visualización \ registro _ {2} n.}$ ${\frac {1}{2}}n\log _{2}n,$

Según el teorema de Ramsey , un gráfico de vértice no dirigido contiene una camarilla o un conjunto independiente cuyo tamaño depende logarítmicamente de El tamaño exacto de este conjunto se desconoce, pero actualmente las mejores estimaciones contienen logaritmos binarios. $norte$ $norte.$

Otros usos

El número de rondas del juego según el sistema olímpico es igual al logaritmo binario del número de participantes en la competición [10] .

En teoría musical , para resolver la cuestión de cuántas partes dividir una octava , se requiere encontrar una aproximación racional para Si expandimos este número a una fracción continua , entonces la tercera fracción convergente (7/12) nos permite para justificar la división clásica de la octava en 12 semitonos [11] . $\log_2 \frac {3}{2} \approx 0{,}585.$

Notas

↑ A veces, especialmente en las ediciones alemanas, se denota el logaritmo binario (del latín logarithmus dyadis ), véase Bauer, Friedrich L. Origins and Foundations of Computing: In Cooperation with Heinz Nixdorf MuseumsForum (inglés) . - Springer Science & Business Media , 2009. - P. 54. - ISBN 978-3-642-02991-2 . ${\ estilo de visualización \ nombre del operador {ld} b}$
↑ Euler, Leonhard (1739), Capítulo VII. De Variorum Intervallorum Receptis Appelationibus , Tentamen novae theoriae musicae ex certissismis harmoniae principiis dilucide expositae , Academia de San Petersburgo, p. 102-112 , < http://eulerarchive.maa.org/pages/E033.html > Archivado el 11 de octubre de 2018 en Wayback Machine .
↑ Tegg, Thomas (1829), Logaritmos binarios , Enciclopedia de Londres; o, Diccionario universal de ciencia, arte, literatura y mecánica práctica: que comprende una visión popular del estado actual del conocimiento, Volumen 4 , p. 142–143 , < https://books.google.com/books?id=E-ZTAAAAYAAJ&pg=PA142 > Archivado el 23 de mayo de 2021 en Wayback Machine .
↑ Vygodsky M. Ya. Manual de matemáticas elementales, 1978 , p. 187..
↑ Función logarítmica. // Enciclopedia matemática (en 5 tomos) . - M .: Enciclopedia soviética , 1982. - T. 3.
↑ Harel, David; Feldman, Yishai A. Algoritmia: el espíritu de la computación . - Nueva York: Addison-Wesley, 2004. - Pág . 143 . - ISBN 978-0-321-11784-7 .
↑ Leiss, Ernst L. (2006), A Programmer's Companion to Algorithm Analysis , CRC Press, p. 28, ISBN 978-1-4200-1170-8 , < https://books.google.com/books?id=E6BNGFQ6m_IC&pg=RA2-PA28 > Archivado el 12 de agosto de 2020 en Wayback Machine .
↑ Devroye, L. & Kruszewski, P. (1996), Sobre el número de Horton-Strahler para intentos aleatorios , RAIRO Informatique Théorique et Applications Vol . 30 (5): 443-456, doi : 10.1051/ita/1996300504431 , < https ://eudml.org/doc/92635 > Archivado el 7 de octubre de 2015 en Wayback Machine .
↑ Eppstein, David (2005), The lattice dimension of a graph , European Journal of Combinatorics volumen 26 (5): 585–592 , DOI 10.1016/j.ejc.2004.05.001
↑ Kharin A. A. Organización y celebración de concursos. Guía metodológica . - Izhevsk: UdGU, 2011. - S. 27.
↑ Shilov G. E. Gamma simple. Dispositivo de escala musical. Copia de archivo fechada el 22 de febrero de 2014 en Wayback Machine M.: Fizmatgiz, 1963. 20 p. Serie "Conferencias Populares de Matemáticas", Número 37.

Literatura

Vygodsky M. Ya. Manual de matemáticas elementales . - ed. 25 - M .: Nauka, 1978. - ISBN 5-17-009554-6 .
Korn G., Korn T. Manual de Matemáticas (para Investigadores e Ingenieros) . - M. : Nauka, 1973. - 720 p.
Fikhtengol'ts G. M. Curso de cálculo diferencial e integral. - ed. 6to. — M .: Nauka, 1966. — 680 p.

Enlaces

Tabla de logaritmos binarios de enteros del 1 al 100. Archivado el 12 de agosto de 2019 en Wayback Machine .