logaritmo binario

El número de dígitos ( bits ) en la representación binaria de un entero positivo n es la parte entera de 1 + log ₂ n , es decir ^{[ 12 ].}

${\displaystyle \lfloor \log _{2}n\rfloor +1.}$

En teoría de la información, la definición de la cantidad de autoinformación y entropía de la información se expresa a menudo con el logaritmo binario, lo que corresponde a considerar el bit como la unidad fundamental de información . Con estas unidades, el teorema de Shannon-Hartley expresa la capacidad de información de un canal como el logaritmo binario de su relación señal-ruido, más uno. Sin embargo, el logaritmo natural y el nat también se utilizan en notaciones alternativas para estas definiciones. ^{[ 26 ]}

Aunque el logaritmo natural es más importante que el logaritmo binario en muchas áreas de las matemáticas puras, como la teoría de números y el análisis matemático , ^{[ 27 ]} el logaritmo binario tiene varias aplicaciones en combinatoria :

• Todo árbol binario con n hojas tiene una altura de al menos log₂n , siendo igual cuando n es una potencia de dos y el árbol es un árbol binario completo . ^{[ 28 ]} De manera similar, el número de Strahler _de un sistema fluvial con n afluentes es ^{como máximo} log₂n + 1. [ ₂₉ ^]
• Toda familia de conjuntos con n conjuntos diferentes tiene al menos log ₂ n elementos en su unión, con igualdad cuando la familia es un conjunto potencia . ^{[ 30 ]}
• Todo cubo parcial con n vértices tiene una dimensión isométrica de al menos log ₂ n y tiene como máximo 1 / 2 n log ₂ n aristas , con igualdad cuando el cubo parcial es un grafo hipercubo . ^{[ 31 ]}
• Según el teorema de Ramsey , todo grafo no dirigido de n vértices tiene una camarilla o un conjunto independiente de tamaño logarítmico en n . No se conoce el tamaño exacto que se puede garantizar, pero las mejores cotas conocidas para su tamaño involucran logaritmos binarios. En particular, todos los grafos tienen una camarilla o un conjunto independiente de tamaño al menos 1 / 2 log 2 n (1 − o (1)) y casi todos los grafos no tienen una camarilla o un conjunto independiente de tamaño mayor que ₂ log ₂ n (1 + o (1)) . ^{[ 32 ]}
• A partir de un análisis matemático del modelo de barajado aleatorio de Gilbert-Shannon-Reeds , se puede demostrar que el número de veces que se necesita barajar una baraja de n cartas, utilizando barajados de tipo riffle , para obtener una distribución de permutaciones cercana a la aleatoria uniforme, es aproximadamente 3 / 2 log ₂ n . Este cálculo constituye la base de la recomendación de que las barajas de 52 cartas se barajen siete veces. ^{[ 33 ]}

El logaritmo binario también aparece con frecuencia en el análisis de algoritmos , ^{[ 19 ]} no solo por el uso frecuente de la aritmética de números binarios en algoritmos, sino también porque los logaritmos binarios aparecen en el análisis de algoritmos basados ​​en ramificación de dos vías. ^{[ 14 ]} Si un problema inicialmente tiene n opciones para su solución, y cada iteración del algoritmo reduce el número de opciones a la mitad, entonces el número de iteraciones necesarias para seleccionar una sola opción es nuevamente la parte entera de log₂n _. Esta idea se utiliza en el análisis de varios algoritmos y estructuras de datos . Por ejemplo, en la búsqueda binaria , el tamaño del problema a resolver se reduce a la mitad con cada iteración, y por lo tanto se necesitan aproximadamente log₂n _iteraciones para obtener una solución para un problema de tamaño n . ^{[ 34 ]} De manera similar, un árbol de búsqueda binaria perfectamente equilibrado que contiene n elementos tiene una altura _de log₂ ( n +1)⁻¹ . ^{[ 35 ]}

El tiempo de ejecución de un algoritmo se suele expresar en notación O grande , que se utiliza para simplificar expresiones omitiendo sus factores constantes y términos de orden inferior. Dado que los logaritmos en diferentes bases difieren entre sí solo por un factor constante, se puede decir que los algoritmos que se ejecutan en tiempo O (log ₂ n ) también se ejecutan, por ejemplo, en tiempo O (log ₁₃ n ) . Por lo tanto, la base del logaritmo en expresiones como O (log n ) u O ( n log n ) no es importante y puede omitirse. ^{[ 11 ] [ 36 ]} Sin embargo, para los logaritmos que aparecen en el exponente de un límite de tiempo, la base del logaritmo no puede omitirse. Por ejemplo, O (2 ^{log ₂ n} ) no es lo mismo que O (2 ^{ln n} ) porque el primero es igual a O ( n ) y el segundo a O ( n ^0.6931... ) .

Los algoritmos con tiempo de ejecución O ( n  log n )  a veces se denominan linealítmicos . ^{[ 37 ]} Algunos ejemplos de algoritmos con tiempo de ejecución O (log n ) u O ( n log n ) son:

• Tiempo promedio de quicksort y otros algoritmos de ordenación por comparación ^{[ 38 ]}
• Búsqueda en árboles de búsqueda binaria balanceados ^{[ 39 ]}
• Exponenciación por elevación al cuadrado ^{[ 40 ]}
• Subsecuencia creciente más larga ^{[ 41 ]}

Los logaritmos binarios también aparecen en los exponentes de los límites de tiempo para algunos algoritmos de divide y vencerás , como el algoritmo de Karatsuba para multiplicar números de n bits en tiempo O ( n ^{log ₂ 3} ) , ^{[ 42 ]} y el algoritmo de Strassen para multiplicar matrices de n × n en tiempo O ( n ^{log ₂ 7} ) . ^{[ 43 ]} La aparición de logaritmos binarios en estos tiempos de ejecución se puede explicar haciendo referencia al teorema maestro para recurrencias de divide y vencerás .

En bioinformática , los microarrays se utilizan para medir la intensidad de la expresión de diferentes genes en una muestra de material biológico. Las distintas tasas de expresión de un gen se comparan a menudo mediante el logaritmo binario de la razón de las tasas de expresión: el logaritmo de la razón de dos tasas de expresión se define como el logaritmo binario de la razón de las dos tasas. Los logaritmos binarios permiten una comparación conveniente de las tasas de expresión: una tasa de expresión duplicada se puede describir con un logaritmo de la razón de 1 , una tasa de expresión reducida a la mitad se puede describir con un logaritmo de la razón de −1 , y una tasa de expresión sin cambios se puede describir con un logaritmo de la razón de cero, por ejemplo. ^{[ 44 ]}

Los puntos de datos obtenidos de esta manera se visualizan a menudo como un diagrama de dispersión en el que uno o ambos ejes de coordenadas son logaritmos binarios de razones de intensidad, o en visualizaciones como el diagrama MA y el diagrama RA que rotan y escalan estos diagramas de dispersión de razones logarítmicas. ^{[ 45 ]}

En teoría musical , el intervalo o diferencia perceptiva entre dos tonos se determina por la relación de sus frecuencias. Los intervalos que provienen de razones de números racionales con numeradores y denominadores pequeños se perciben como particularmente eufónicos. El más simple e importante de estos intervalos es la octava , una relación de frecuencias de 2:1 . El número de octavas que separan dos tonos es el logaritmo binario de su relación de frecuencias. ^{[ 46 ]}

Para estudiar sistemas de afinación y otros aspectos de la teoría musical que requieren distinciones más finas entre tonos, es útil tener una medida del tamaño de un intervalo que sea más fina que una octava y sea aditiva (como los logaritmos) en lugar de multiplicativa (como las razones de frecuencia). Es decir, si los tonos x , y y z forman una secuencia ascendente de tonos, entonces la medida del intervalo de x a y más la medida del intervalo de y a z debe ser igual a la medida del intervalo de x a z . Dicha medida viene dada por el cent , que divide la octava en 1200 intervalos iguales ( 12 semitonos de 100 cents cada uno). Matemáticamente, dados tonos con frecuencias f ₁ y f ₂ , el número de cents en el intervalo de f ₁ a f ₂ es ^{[ 46 ].}

${\displaystyle \left|1200\log _{2}{\frac {f_{1}}{f_{2}}}\right|.}$

La milioctava se define de la misma manera, pero con un multiplicador de ¹⁰⁰⁰ en lugar de 1200. ^[ 47 ^]

En los juegos y deportes competitivos que involucran a dos jugadores o equipos en cada juego o partido, el logaritmo binario indica el número de rondas necesarias en un torneo de eliminación directa para determinar un ganador. Por ejemplo, un torneo de 4 jugadores requiere log₂ ₄ = 2 rondas para determinar al ganador, un torneo de 32 equipos requiere log₂ ₃₂ = 5 rondas, etc. En este caso, para n jugadores/equipos donde n no es una potencia de 2, log₂ _{n se redondea hacia arriba} , ya que es necesario tener al menos una ronda en la que no jueguen todos los competidores restantes. Por ejemplo, log₂ 6 es _{aproximadamente} 2,585 , que se redondea a 3 , lo que indica que un torneo de 6 equipos requiere 3 rondas (dos equipos quedan fuera de la primera ronda o un equipo queda fuera de la segunda). El mismo número de rondas también es necesario para determinar un ganador claro en un torneo de sistema suizo . ^{[ 48 ]}

En fotografía , los valores de exposición se miden en términos del logaritmo binario de la cantidad de luz que llega a la película o al sensor, de acuerdo con la ley de Weber-Fechner que describe una respuesta logarítmica del sistema visual humano a la luz. Un paso de exposición es una unidad en una escala logarítmica de base 2. ^{[ 49 ] [ 50 ]} Más precisamente, el valor de exposición de una fotografía se define como

${\displaystyle \log _{2}{\frac {N^{2}}{t}}}$

donde N es el número f que mide la apertura del objetivo durante la exposición, y t es el número de segundos de exposición. ^{[ 51 ]}

Los logaritmos binarios (expresados ​​como pasos) también se utilizan en densitometría para expresar el rango dinámico de materiales fotosensibles o sensores digitales. ^{[ 52 ]}

Una forma sencilla de calcular log₂ _n en calculadoras que no tienen la función log₂ es usar las funciones de logaritmo natural ( ln ) o logaritmo común ( log o log₁₀ ), que se encuentran en _{la mayoría de} las calculadoras científicas . Para cambiar la base del logaritmo a 2 desde e , 10 o cualquier otra base b , se pueden usar las fórmulas : ^{[ 50 ] [ 53 ]}

${\displaystyle \log _{2}n={\frac {\ln n}{\ln 2}}={\frac {\log _{10}n}{\log _{10}2}}={\frac {\log _{b}n}{\log _{b}2}}\,.}$

Aproximadamente, ^{[ 54 ] [ 55 ]}

${\displaystyle \log _{2}n\approx 1.442695\ln n\approx 3.321928\log _{10}n\,.}$

El logaritmo binario se puede convertir en una función de enteros a enteros redondeándolo hacia arriba o hacia abajo. Estas dos formas de logaritmo binario entero están relacionadas por la siguiente fórmula:

${\displaystyle \lfloor \log _{2}(n)\rfloor =\lceil \log _{2}(n+1)\rceil -1,{\text{ si }}n\geq 1.}$^{[ 56 ]}

La definición puede ampliarse definiendo${\displaystyle \lfloor \log _{2}(0)\rfloor =-1}$. Extendida de esta manera, esta función está relacionada con el número de ceros iniciales de la representación binaria sin signo de 32 bits de x , nlz( x ) .

${\displaystyle \lfloor \log _{2}(n)\rfloor =31-\operatorname {nlz} (n).}$^{[ 56 ]}

El logaritmo binario entero puede interpretarse como el índice basado en cero del bit 1 más significativo de la entrada. En este sentido, es el complemento de la operación de búsqueda del primer conjunto , que encuentra el índice del bit 1 menos significativo . Muchas plataformas de hardware incluyen soporte para encontrar el número de ceros iniciales, u operaciones equivalentes, que pueden usarse para encontrar rápidamente el logaritmo binario. Las funciones flsy en el kernel de Linux ^{[ 57 ]} y en algunas versiones de la biblioteca de software libc también calculan el logaritmo binario (redondeado al entero más uno).flsl

Para un número${\displaystyle x}$representado en coma flotante como${\displaystyle x=2^{E}(1+m)}$, con exponente entero${\displaystyle E}$y mantis${\displaystyle m}$en el rango${\displaystyle 0\leq m<1}$, el logaritmo binario se puede aproximar aproximadamente como${\displaystyle \log _{2}x\approx E+m}$. ^{[ 16 ]} Esta aproximación es exacta en ambos extremos del rango de mantisas, pero subestima el logaritmo en el medio del rango, alcanzando un error máximo de aproximadamente 0,086 en una mantisa de aproximadamente 0,44. Se puede hacer más precisa utilizando una función lineal por partes de${\displaystyle m}$, ^{[ 58 ]} o, de forma más burda, añadiendo un término de corrección constante.${\displaystyle \log _{2}x\approx E+m+\sigma }$Por ejemplo, elegir${\displaystyle \sigma \approx 0.043}$reduciría a la mitad el error máximo. El algoritmo rápido de raíz cuadrada inversa utiliza esta idea, con un término de corrección diferente que se puede inferir que es${\displaystyle \sigma \approx 0.0450466}$, manipulando directamente la representación binaria de${\displaystyle x}$multiplicar este logaritmo aproximado por${\displaystyle -{\tfrac {1}{2}}}$, obteniendo un valor de punto flotante que se aproxima a${\displaystyle 1/{\sqrt {x}}}$. ^{[ 59 ]}

Para un número real positivo general , el logaritmo binario se puede calcular en dos partes. ^{[ 60 ]} Primero, se calcula la parte entera ,${\displaystyle \lfloor \log _{2}x\rfloor }$(llamada la característica del logaritmo). Esto reduce el problema a uno donde el argumento del logaritmo está en un rango restringido, el intervalo [ 1, 2) , simplificando el segundo paso de calcular la parte fraccionaria (la mantisa del logaritmo). Para cualquier x > 0 , existe un entero único n tal que 2 ⁿ ≤ x < 2 ^{n +1} , o equivalentemente 1 ≤ 2 ^{− n} x < 2 . Ahora la parte entera del logaritmo es simplemente n , y la parte fraccionaria es log ₂ (2 ^{− n} x ) . ^{[ 60 ]} En otras palabras:

${\displaystyle \log _{2}x=n+\log _{2}y\quad {\text{donde }}y=2^{-n}x{\text{ y }}y\in [1,2)}$

Para los números de punto flotante normalizados , la parte entera viene dada por el exponente de punto flotante, ^{[ 61 ]} y para los enteros se puede determinar realizando una operación de conteo de ceros iniciales . ^{[ 62 ]}

La parte fraccionaria del resultado es log₂ _y y se puede calcular iterativamente, utilizando únicamente multiplicación y división elementales. ^{[ 60 ]} El algoritmo para calcular la parte fraccionaria se puede describir en pseudocódigo de la siguiente manera:

1. Comienza con un número real y en el intervalo semiabierto [ 1, 2) . Si y = 1 , entonces el algoritmo ha terminado y la parte fraccionaria es cero.
2. De lo contrario, eleva al cuadrado y repetidamente hasta que el resultado z se encuentre en el intervalo [ 2, 4) . Sea m el número de elevaciones al cuadrado necesarias. Es decir, z = y ^{2 m} con m elegido de tal manera que z esté en [ 2, 4) .
3. Tomando el logaritmo de ambos lados y haciendo algunos cálculos algebraicos:$${\displaystyle {\begin{aligned}\log _{2}z&=2^{m}\log _{2}y\\\log _{2}y&={\frac {\log _{2}z}{2^{m}}}\\&={\frac {1+\log _{2}(z/2)}{2^{m}}}\\&=2^{-m}+2^{-m}\log _{2}(z/2).\end{aligned}}}$$
4. Una vez más, z /2 es un número real en el intervalo [ 1, 2) . Regrese al paso 1 y calcule el logaritmo binario de z /2 usando el mismo método.

El resultado de esto se expresa mediante las siguientes fórmulas recursivas, en las que${\displaystyle m_{i}}$es el número de elevaciones al cuadrado necesarias en la i -ésima iteración del algoritmo: $${\displaystyle {\begin{aligned}\log _{2}x&=n+2^{-m_{1}}\left(1+2^{-m_{2}}\left(1+2^{-m_{3}}\left(1+\cdots \right)\right)\right)\\&=n+2^{-m_{1}}+2^{-m_{1}-m_{2}}+2^{-m_{1}-m_{2}-m_{3}}+\cdots \end{aligned}}}$$

En el caso especial en que la parte fraccionaria del paso 1 sea cero, se trata de una secuencia finita que termina en algún punto. De lo contrario, es una serie infinita que converge según el criterio de la razón , ya que cada término es estrictamente menor que el anterior (dado que todo m _i > 0 ). Véase el método de Horner . Para su uso práctico, esta serie infinita debe truncarse para obtener un resultado aproximado. Si la serie se trunca después del i -ésimo término, el error en el resultado es menor que 2 ^{−( m ₁ + m ₂ + ⋯ + m _i )} . ^{[ 60 ]}

La log2función está incluida en las funciones matemáticas estándar de C. La versión predeterminada de esta función acepta argumentos de doble precisión , pero existen variantes que permiten que el argumento sea de precisión simple o de tipo long double . ^{[ 63 ]} En entornos informáticos que admiten números complejos y conversión implícita de tipos, como MATLAB, el argumento de la log2función puede ser un número negativo , devolviendo un número complejo. ^{[ 64 ]}