Logaritmo binario

Exponente de una potencia de dos

Gráfica de log ₂  x en función de un número real positivo x

En matemáticas , el logaritmo binario ( log ₂  n ) es la potencia a la que se debe elevar el número 2 para obtener el valor  n . Es decir, para cualquier número real x ,

${\displaystyle x=\log _{2}n\quad \Longleftrightarrow \quad 2^{x}=n.}$

Por ejemplo, el logaritmo binario de 1 es 0 , el logaritmo binario de 2 es 1 , el logaritmo binario de 4 es  2 y el logaritmo binario de 32 es  5 .

El logaritmo binario es el logaritmo en base 2 y es la función inversa de la potencia de dos . Además de log ₂ , una notación alternativa para el logaritmo binario es lb (la notación preferida por ISO 31-11 e ISO 80000-2 ).

Históricamente, la primera aplicación de los logaritmos binarios fue en teoría musical , por Leonhard Euler : el logaritmo binario de una relación de frecuencias de dos tonos musicales da el número de octavas en las que se diferencian los tonos. Los logaritmos binarios se pueden utilizar para calcular la longitud de la representación de un número en el sistema de numeración binario , o el número de bits necesarios para codificar un mensaje en la teoría de la información . En informática , cuentan el número de pasos necesarios para la búsqueda binaria y algoritmos relacionados. Otras áreas en las que se utiliza con frecuencia el logaritmo binario incluyen la combinatoria , la bioinformática , el diseño de torneos deportivos y la fotografía .

Los logaritmos binarios se incluyen en las funciones matemáticas estándar de C y en otros paquetes de software matemático.

Historia

Leonhard Euler fue el primero en aplicar los logaritmos binarios a la teoría musical , en 1739.

Los poderes de dos se conocen desde la antigüedad; por ejemplo, aparecen en Elementos , Props. de Euclides . IX.32 (sobre la factorización de potencias de dos) y IX.36 (la mitad del teorema de Euclides-Euler , sobre la estructura de los números pares perfectos ). Y el logaritmo binario de una potencia de dos es simplemente su posición en la secuencia ordenada de potencias de dos. Sobre esta base, a Michael Stifel se le atribuye la publicación de la primera tabla conocida de logaritmos binarios en 1544. Su libro Arithmetica Integra contiene varias tablas que muestran los números enteros con sus correspondientes potencias de dos. Invertir las filas de estas tablas permite interpretarlas como tablas de logaritmos binarios. ^{[1] [2]}

Antes que Stifel, al matemático jainista del siglo VIII, Virasena , se le atribuye un precursor del logaritmo binario. El concepto de ardhacheda de Virasena se ha definido como el número de veces que un número dado se puede dividir en partes iguales entre dos. Esta definición da lugar a una función que coincide con el logaritmo binario en potencias de dos, ^[3] pero es diferente para otros números enteros, dando el orden 2-ádico en lugar del logaritmo. ^[4]

La forma moderna de un logaritmo binario, aplicable a cualquier número (no sólo a potencias de dos), fue considerada explícitamente por Leonhard Euler en 1739. Euler estableció la aplicación de los logaritmos binarios a la teoría musical, mucho antes de que sus aplicaciones en la teoría de la información y la informática se convirtieran en conocido. Como parte de su trabajo en esta área, Euler publicó una tabla de logaritmos binarios de los números enteros del 1 al 8, con siete dígitos decimales de precisión. ^{[5] [6]}

Definición y propiedades

La función logaritmo binaria se puede definir como la función inversa a la potencia de dos , que es una función estrictamente creciente sobre los números reales positivos y, por lo tanto, tiene una inversa única. ^[7] Alternativamente, puede definirse como ln n /ln 2 , donde ln es el logaritmo natural , definido en cualquiera de sus formas estándar. El uso del logaritmo complejo en esta definición permite extender el logaritmo binario a los números complejos . ^[8]

Como ocurre con otros logaritmos, el logaritmo binario obedece a las siguientes ecuaciones, que pueden usarse para simplificar fórmulas que combinan logaritmos binarios con multiplicación o exponenciación: ^[9]

${\displaystyle \log _{2}xy=\log _{2}x+\log _{2}y}$

${\displaystyle \log _{2}{\frac {x}{y}}=\log _{2}x-\log _{2}y}$

${\displaystyle \log _{2}x^{y}=y\log _{2}x.}$

Para obtener más información, consulte la lista de identidades logarítmicas .

Notación

En matemáticas, el logaritmo binario de un número n suele escribirse como log ₂  n . ^[10] Sin embargo, se han utilizado o propuesto varias otras notaciones para esta función, especialmente en áreas de aplicación.

Algunos autores escriben el logaritmo binario como lg n , ^{[11] [12]} la notación que figura en el Manual de estilo de Chicago . ^[13] Donald Knuth atribuye esta notación a una sugerencia de Edward Reingold , ^[14] pero su uso tanto en teoría de la información como en ciencias de la computación data de antes de que Reingold estuviera activo. ^{[15] [16]} El logaritmo binario también se ha escrito como log n con una declaración previa de que la base predeterminada para el logaritmo es  2 . ^{[17] [18] [19]} Otra notación que se utiliza a menudo para la misma función (especialmente en la literatura científica alemana) es ld n , ^{[20] [21] [22]} del latín logarithmus dualis ^[20] o logarithmus dyadis . ^[20] Las normas DIN 1302  [de] , ISO 31-11 e ISO 80000-2 recomiendan otra notación más, lb n . Según estos estándares, lg n no debe usarse para el logaritmo binario, ya que está reservado para el logaritmo común log ₁₀ n . ^{[23] [24] [25]}

Aplicaciones

Teoría de la información

El número de dígitos ( bits ) en la representación binaria de un entero positivo n es la parte integral 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 la entropía de la información a menudo se expresa con el logaritmo binario, correspondiente a hacer del bit 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]

combinatoria

Un torneo de eliminación simple de 16 jugadores con la estructura de un árbol binario completo . La altura del árbol (número de rondas del torneo) es el logaritmo binario del número de jugadores, redondeado a un número entero.

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 , con igualdad cuando n es una potencia de dos y el árbol es un árbol binario completo . ^[28] De manera relacionada, el número de Strahler de un sistema fluvial con n corrientes tributarias es como máximo log ₂  n + 1 . ^[29]
• Cada familia de conjuntos con n conjuntos diferentes tiene al menos log ₂  n elementos en su unión, siendo igual 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 gráfico de hipercubo . ^[31]
• Según el teorema de Ramsey , cada gráfico no dirigido de n -vértices tiene una camarilla o un conjunto independiente de tamaño logarítmico en n . Se desconoce el tamaño exacto que se puede garantizar, pero los mejores límites conocidos sobre su tamaño implican logaritmos binarios. En particular, todos los gráficos tienen una camarilla o un conjunto independiente de tamaño al menos1/2log ₂  n (1 − o (1)) y casi todos los gráficos no tienen una camarilla o un conjunto independiente de tamaño mayor que 2 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 rápidos , para obtener una distribución de permutaciones cercana a uniformemente aleatorio, es aproximadamente3/2iniciar sesión ₂  norte . Este cálculo forma la base para recomendar que las barajas de 52 cartas se barajen siete veces. ^[33]

Complejidad computacional

Búsqueda binaria en una matriz ordenada, un algoritmo cuya complejidad temporal involucra logaritmos binarios

El logaritmo binario también aparece frecuentemente en el análisis de algoritmos , ^[19] no sólo por el uso frecuente de la aritmética de números binarios en los algoritmos, sino también porque los logaritmos binarios ocurren en el análisis de algoritmos basados ​​en ramificaciones 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 por un factor de dos, entonces el número de iteraciones necesarias para seleccionar una única opción es nuevamente la parte integral 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 binario perfectamente equilibrado que contiene n elementos tiene una altura log ₂ ( n + 1) − 1 . ^[35]

El tiempo de ejecución de un algoritmo generalmente se expresa en notación O grande , que se utiliza para simplificar expresiones omitiendo sus factores constantes y términos de orden inferior. Debido a que los logaritmos en diferentes bases difieren entre sí sólo por un factor constante, también se puede decir que los algoritmos que se ejecutan en tiempo O (log ₂  n ) se ejecutan en, digamos, 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 se puede omitir. 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:

• Clasificación rápida de tiempo promedio y otros algoritmos de clasificación por comparación ^[38]
• Búsqueda en árboles de búsqueda binarios equilibrados ^[39]
• Exponenciació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 el tiempo O ( n ^{log ₂  3} ) , ^[42] y el algoritmo de Strassen para multiplicar n × n matrices en el 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 de las recurrencias de divide y vencerás .

Bioinformática

Un microarray para aproximadamente 8700 genes. Las tasas de expresión de estos genes se comparan mediante logaritmos binarios.

En bioinformática , los microarrays se utilizan para medir con qué fuerza se expresan diferentes genes en una muestra de material biológico. A menudo se comparan diferentes tasas de expresión de un gen utilizando el logaritmo binario de la relación de tasas de expresión: la relación logarítmica de dos tasas de expresión se define como el logaritmo binario de la relació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 mediante una proporción logarítmica de 1 , una tasa de expresión reducida a la mitad se puede describir mediante una proporción logarítmica de −1 y una tasa de expresión sin cambios se puede describir mediante una relación logarítmica de cero, por ejemplo. ^[44]

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

Teoría musical

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

Para estudiar los 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 que sea aditiva (como lo son los logaritmos) en lugar de multiplicativa (como lo son las frecuencias). las proporciones son). 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 . Tal medida viene dada por la centésima , que divide la octava en 1200 intervalos iguales ( 12 semitonos de 100 centésimas cada uno). Matemáticamente, dados los tonos con frecuencias f ₁ y f ₂ , el número de centavos 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 forma, pero con un multiplicador de 1000 en lugar de 1200 . ^[47]

Programación deportiva

En juegos competitivos y deportes en los que participan 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 simple necesarias para determinar un ganador. Por ejemplo, un torneo de 4 jugadores requiere log ₂  4 = 2 rondas para determinar el ganador, un torneo de 32 equipos requiere log ₂  32 = 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 no participan en la primera ronda o un equipo no participa en la segunda ronda). También es necesario el mismo número de rondas para determinar un claro ganador en un torneo del sistema suizo . ^[48]

Fotografía

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. Una sola parada 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 de la lente durante la exposición y t es el número de segundos de exposición. ^[51]

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

Cálculo

Calculadora científica HP-35 (1972). Las claves log e ln están en la fila superior; no hay ninguna clave de registro ₂  .

Conversión de otras bases

Una manera fácil de calcular log ₂  n en calculadoras que no tienen una 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 de e o 10 a 2 se pueden utilizar las fórmulas : ^{[50] [53]}

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

o aproximadamente

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

redondeo de enteros

El logaritmo binario se puede convertir en una función de números enteros y a números enteros redondeándolo hacia arriba o hacia abajo. Estas dos formas de logaritmo binario entero están relacionadas mediante esta fórmula:

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

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

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

El logaritmo binario entero se puede interpretar como el índice de base cero del bit 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 menos significativo . Muchas plataformas de hardware incluyen soporte para encontrar el número de ceros a la izquierda u operaciones equivalentes, que pueden usarse para encontrar rápidamente el logaritmo binario. Las funciones flsy flslen el kernel de Linux ^[55] y en algunas versiones de la biblioteca de software libc también calculan el logaritmo binario (redondeado a un número entero más uno).

Aproximación iterativa

Para un número real positivo general , el logaritmo binario se puede calcular en dos partes. ^[56] Primero, se calcula la parte entera , (llamada 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 número 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 ) . ^[56] En otras palabras: ${\displaystyle \lfloor \log _{2}x\rfloor }$

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

Para números de punto flotante normalizados , la parte entera viene dada por el exponente de punto flotante, ^[57] y para números enteros se puede determinar realizando una operación de conteo de ceros a la izquierda . ^[58]

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

1. Comience con un número real y en el intervalo medio abierto [1, 2) . Si y = 1 , entonces el algoritmo está 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 cuadrados necesarios. Es decir, z = y ^{2 m} con m elegido de manera que z esté en [2, 4) .
3. Tomando el logaritmo de ambos lados y haciendo algo de álgebra:
   $${\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 cuales es el número de elevaciones al cuadrado requeridas en la i -ésima iteración del algoritmo: ${\displaystyle m_{i}}$

$${\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 el que se encuentra que la parte fraccionaria en el paso 1 es cero, se trata de una secuencia finita que termina en algún punto. En caso contrario, se trata de una serie infinita que converge según el criterio de la razón , ya que cada término es estrictamente menor que el anterior (ya que todo m _i > 0 ). Para uso práctico, esta serie infinita debe truncarse para llegar a un resultado aproximado. Si la serie se trunca después del i -ésimo término, entonces el error en el resultado es menor que 2 ^{−( m ₁ + m ₂ + ⋯ + m _i )} . ^[56]

Soporte de biblioteca de software

La log2función está incluida en las funciones matemáticas estándar de C. La versión predeterminada de esta función toma argumentos de doble precisión , pero sus variantes permiten que el argumento sea de precisión simple o doble largo . ^[59] En entornos informáticos que admiten números complejos y conversión de tipos implícita, como MATLAB , se permite que el argumento de la log2función sea un número negativo , devolviendo uno complejo. ^[60]

Referencias

1. Groza, Vivian Shaw; Shelley, Susanne M. (1972), Matemáticas de precálculo, Nueva York: Holt, Rinehart y Winston, pág. 182, ISBN 978-0-03-077670-0.
2. Stifel, Michael (1544), Arithmetica integra (en latín), p. 31. Una copia de la misma tabla con dos entradas más aparece en la p. 237, y otra copia extendida a las potencias negativas aparece en la p. 249b.
3. Joseph, GG (2011), La cresta del pavo real: raíces no europeas de las matemáticas (3.ª ed.), Princeton University Press, p. 352.
4. Véase, por ejemplo, Shparlinski, Igor (2013), Aplicaciones criptográficas de la teoría analítica de números: límites inferiores de complejidad y pseudoaleatoriedad, Progreso en informática y lógica aplicada, vol. 22, Birkhäuser, pág. 35, ISBN 978-3-0348-8037-4.
5. Euler, Leonhard (1739), "Chapter VII. De Variorum Intervallorum Receptis Appelationibus", Tentamen novae theoriae musicae ex certissismis harmoniae principiis dilucide expositae (en latín), Academia de San Petersburgo, págs. 102-112.
6. 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ágs. 142-143.
7. Batschelet, E. (2012), Introducción a las matemáticas para científicos de la vida, Springer, p. 128, ISBN 978-3-642-96080-2.
8. Por ejemplo, Microsoft Excel proporciona la IMLOG2función para logaritmos binarios complejos: consulte Bourg, David M. (2006), Excel Scientific and Engineering Cookbook, O'Reilly Media, p. 232, ISBN 978-0-596-55317-3.
9. Kolman, Bernardo; Shapiro, Arnold (1982), "11.4 Propiedades de los logaritmos", Álgebra para estudiantes universitarios, Academic Press, págs. 334–335, ISBN 978-1-4832-7121-7.
10. Por ejemplo, esta es la notación utilizada en la Encyclopedia of Mathematics y The Princeton Companion to Mathematics .
11. Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001) [1990], Introducción a los algoritmos (2ª ed.), MIT Press y McGraw-Hill, págs. 34, 53–54, ISBN 0-262-03293-7
12. Sedgewick, Robert ; Wayne, Kevin Daniel (2011), Algoritmos, Addison-Wesley Professional, pág. 185, ISBN 978-0-321-57351-3.
13. El Manual de estilo de Chicago (25ª ed.), University of Chicago Press, 2003, p. 530.
14. Knuth, Donald E. (1997), Algoritmos fundamentales , El arte de la programación informática , vol. 1 (3.ª ed.), Addison-Wesley Professional, ISBN 978-0-321-63574-7, pag. 11. La misma notación estaba en la segunda edición de 1973 del mismo libro (p. 23), pero sin el crédito a Reingold.
15. Trucco, Ernesto (1956), "Una nota sobre el contenido informativo de los gráficos", Bull. Matemáticas. Biofísica. , 18 (2): 129–135, doi :10.1007/BF02477836, SEÑOR  0077919.
16. Mitchell, John N. (1962), "Multiplicación y división por computadora utilizando logaritmos binarios", IRE Transactions on Electronic Computers , EC-11 (4): 512–517, doi :10.1109/TEC.1962.5219391.
17. Ficha, Georges; Hebuterne, Gerard (2013), Matemáticas para ingenieros, John Wiley & Sons, pág. 152, ISBN 978-1-118-62333-6, En lo sucesivo, y a menos que se indique lo contrario, la notación log x siempre representa el logaritmo en base 2 de x.
18. Portada, Thomas M .; Thomas, Joy A. (2012), Elementos de la teoría de la información (2ª ed.), John Wiley & Sons , p. 33, ISBN 978-1-118-58577-1, A menos que se especifique lo contrario, llevaremos todos los logaritmos a base 2.
19. Goodrich, Michael T .; Tamassia, Roberto (2002), Diseño de algoritmos: fundamentos, análisis y ejemplos de Internet , John Wiley & Sons, p. 23, Uno de los aspectos interesantes y a veces incluso sorprendentes del análisis de estructuras de datos y algoritmos es la presencia ubicua de logaritmos... Como es costumbre en la literatura informática, omitimos escribir la base b del logaritmo cuando b  = 2 .
20. Tafel, Hans Jörg (1971), Einführung in die digitale Datenverarbeitung [ Introducción al procesamiento de información digital ] (en alemán), Munich: Carl Hanser Verlag , págs. 20-21, ISBN 3-446-10569-7
21. Tietze, Ulrich; Schenk, Christoph (1999), Halbleiter-Schaltungstechnik (en alemán) (primera reimpresión corregida, 11ª ed.), Springer Verlag , p. 1370, ISBN 3-540-64192-0
22. Bauer, Friedrich L. (2009), Orígenes y fundamentos de la informática: en cooperación con Heinz Nixdorf MuseumsForum, Springer Science & Business Media , p. 54, ISBN 978-3-642-02991-2.
23. Para DIN 1302, consulte Brockhaus Enzyklopädie en zwanzig Bänden [ Enciclopedia Brockhaus en veinte volúmenes ] (en alemán), vol. 11, Wiesbaden: FA Brockhaus, 1970, pág. 554, ISBN 978-3-7653-0000-4.
24. Para ISO 31-11, consulte Thompson, Ambler; Taylor, Barry M (marzo de 2008), Guía para el uso del Sistema Internacional de Unidades (SI) — Publicación especial NIST 811, edición de 2008 — Segunda impresión (PDF) , NIST , p. 33.
25. Para ISO 80000-2, consulte "Cantidades y unidades - Parte 2: Signos y símbolos matemáticos que se utilizarán en las ciencias naturales y la tecnología" (PDF) , Norma internacional ISO 80000-2 (1.ª ed.), 1 de diciembre de 2009, Sección 12, Funciones exponenciales y logarítmicas, pág. 18.
26. Van der Lubbe, Jan CA (1997), Teoría de la información, Cambridge University Press, pág. 3, ISBN 978-0-521-46760-5.
27. Stewart, Ian (2015), Domar el infinito, Quercus, p. 120, ISBN 9781623654733, en matemáticas y ciencias avanzadas el único logaritmo de importancia es el logaritmo natural.
28. Leiss, Ernst L. (2006), Un compañero del programador para el análisis de algoritmos, CRC Press, p. 28, ISBN 978-1-4200-1170-8.
29. Devroye, L .; Kruszewski, P. (1996), "Sobre el número de Horton-Strahler para intentos aleatorios", RAIRO Informatique Théorique et Applications , 30 (5): 443–456, doi : 10.1051/ita/1996300504431 , MR  1435732.
30. De manera equivalente, una familia con k elementos distintos tiene como máximo 2 ^k conjuntos distintos, con igualdad cuando es un conjunto potencia.
31. Eppstein, David (2005), "La dimensión reticular de un gráfico", European Journal of Combinatorics , 26 (5): 585–592, arXiv : cs.DS/0402028 , doi :10.1016/j.ejc.2004.05.001 , SEÑOR  2127682, S2CID  7482443.
32. Graham, Ronald L .; Rothschild, Bruce L .; Spencer, Joel H. (1980), Teoría de Ramsey , Wiley-Interscience, pág. 78.
33. Bayer, Dave ; Diaconis, Persi (1992), "Trayendo la cola de milano hasta su guarida", The Annals of Applied Probability , 2 (2): 294–313, doi : 10.1214/aoap/1177005705 , JSTOR  2959752, MR  1161056.
34. Mehlhorn, Kurt ; Sanders, Peter (2008), "2.5 Un ejemplo: búsqueda binaria", Algoritmos y estructuras de datos: la caja de herramientas básica (PDF) , Springer, págs. 34–36, ISBN 978-3-540-77977-3.
35. Roberts, Fred ; Tesman, Barry (2009), Combinatoria aplicada (2ª ed.), CRC Press, pág. 206, ISBN 978-1-4200-9983-6.
36. Sipser, Michael (2012), "Ejemplo 7.4", Introducción a la teoría de la computación (3.ª ed.), Cengage Learning, págs. 277-278, ISBN 9781133187790.
37. Sedgewick y Wayne (2011), pág. 186.
38. Cormen et al. (2001), pág. 156; Goodrich y Tamassia (2002), pág. 238.
39. Cormen et al. (2001), pág. 276; Goodrich y Tamassia (2002), pág. 159.
40. Cormen et al. (2001), pág. 879–880; Goodrich y Tamassia (2002), pág. 464.
41. Edmonds, Jeff (2008), Cómo pensar en los algoritmos, Cambridge University Press, p. 302, ISBN 978-1-139-47175-6.
42. Cormen et al. (2001), pág. 844; Goodrich y Tamassia (2002), pág. 279.
43. Cormen et al. (2001), sección 28.2..
44. Causton, Helen; Quackenbush, John; Brazma, Alvis (2009), Análisis de datos de expresión genética de microarrays: una guía para principiantes, John Wiley & Sons, págs. 49–50, ISBN 978-1-4443-1156-3.
45. Eidhammer, Ingvar; Barsnes, Harald; Eide, Geir Egil; Martens, Lennart (2012), Métodos computacionales y estadísticos para la cuantificación de proteínas mediante espectrometría de masas, John Wiley & Sons, p. 105, ISBN 978-1-118-49378-6.
46. Campbell, Murray; Greated, Clive (1994), Guía de acústica para músicos, Oxford University Press, pág. 78, ISBN 978-0-19-159167-9.
47. Randel, Don Michael , ed. (2003), Diccionario de Música de Harvard (4ª ed.), The Belknap Press de Harvard University Press, pág. 416, ISBN 978-0-674-01163-2.
48. Francia, Robert (2008), Introducción a la educación física y las ciencias del deporte, Cengage Learning, p. 282, ISBN 978-1-4180-5529-5.
49. Allen, Isabel; Triantaphillidou, Sophie (2011), El manual de la fotografía, Taylor & Francis, p. 228, ISBN 978-0-240-52037-7.
50. Davis, Phil (1998), Más allá del sistema de zonas, CRC Press, p. 17, ISBN 978-1-136-09294-7.
51. Allen y Triantaphillidou (2011), pág. 235.
52. Zwerman, Susan; Okun, Jeffrey A. (2012), Manual de la sociedad de efectos visuales: técnicas y flujo de trabajo, CRC Press, pág. 205, ISBN 978-1-136-13614-6.
53. Bauer, Craig P. (2013), Historia secreta: la historia de la criptología, CRC Press, p. 332, ISBN 978-1-4665-6186-1.
54. Warren Jr., Henry S. (2002), Hacker's Delight (1ª ed.), Addison Wesley , p. 215, ISBN 978-0-201-91465-8
55. fls, API del kernel de Linux, kernel.org , consultado el 17 de octubre de 2010.
56. Majithia, JC; Levan, D. (1973), "Una nota sobre cálculos de logaritmos de base 2", Actas del IEEE , 61 (10): 1519–1520, doi :10.1109/PROC.1973.9318.
57. Stephenson, Ian (2005), "9.6 Funciones Fast Power, Log2 y Exp2", Representación de producción: diseño e implementación, Springer-Verlag, págs. 270-273, ISBN 978-1-84628-085-6.
58. Warren Jr., Henry S. (2013) [2002], "11-4: Logaritmo entero", Hacker's Delight (2ª ed.), Addison Wesley - Pearson Education, Inc. , p. 291, ISBN 978-0-321-84268-8, 0-321-84268-5.
59. "7.12.6.10 Las funciones log2", especificación ISO/IEC 9899:1999 (PDF) , p. 226.
60. Redfern, Darren; Campbell, Colin (1998), El manual de Matlab® 5, Springer-Verlag, pág. 141, ISBN 978-1-4612-2170-8.

enlaces externos

• Weisstein, Eric W. , "Logaritmo binario", MathWorld
• Anderson, Sean Eron (12 de diciembre de 2003), "Encuentre la base logarítmica 2 de un entero de N bits en operaciones O(lg(N))", Bit Twiddling Hacks , Universidad de Stanford , consultado el 25 de noviembre de 2015
• Feynman y la máquina de conexión