Logaritmo binario

Exponente de una potencia de dos

Gráfica del logaritmo de 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 función 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 la 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 difieren 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 están incluidos en las funciones matemáticas estándar de C y otros paquetes de software matemático.

Historia

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

Las potencias de dos se conocen desde la antigüedad; por ejemplo, aparecen en los Elementos de Euclides , Props. IX.32 (sobre la factorización de potencias de dos) y IX.36 (mitad del teorema de Euclides-Euler , sobre la estructura de los números perfectos pares ). 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. Invirtiendo las filas de estas tablas se pueden interpretar como tablas de logaritmos binarios. ^{[1] [2]}

Antes que Stifel, se le atribuye al matemático jainista del siglo VIII Virasena el precursor del logaritmo binario. El concepto de ardhacheda de Virasena se ha definido como el número de veces que un número dado puede dividirse exactamente por dos. Esta definición da lugar a una función que coincide con el logaritmo binario en las 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 solo 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 se conocieran sus aplicaciones en la teoría de la información y la informática. 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 una precisión de siete dígitos decimales. ^{[5] [6]}

Definición y propiedades

La función logaritmo binario puede definirse como la función inversa elevada a la segunda potencia , que es una función estrictamente creciente sobre los números reales positivos y, por lo tanto, tiene una única inversa. ^[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 que el logaritmo binario se extienda a los números complejos . ^[8]

Al igual que otros logaritmos, el logaritmo binario obedece a las siguientes ecuaciones, que pueden utilizarse 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 a menudo se escribe 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 aparece en The Chicago Manual of Style . ^[13] Donald Knuth atribuye esta notación a una sugerencia de Edward Reingold , ^[14] pero su uso tanto en la teoría de la información como en la informática 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, lb n . De acuerdo con estas normas, lg n no debería utilizarse 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 de entropía de información se expresa a menudo con el logaritmo binario, lo que corresponde a convertir el bit en 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 cuadro de 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]
• Toda familia de conjuntos con n conjuntos diferentes tiene al menos log _2n  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 al menos log ₂  n y tiene como máximo ⁠1/2n log ₂  n aristas, con igualdad cuando el cubo parcial es un grafo hipercubo . ^[31]
• Según el teorema de Ramsey , cada grafo no dirigido de n vértices tiene un grupo o un conjunto independiente de tamaño logarítmico en n . No se conoce el tamaño preciso que se puede garantizar, pero los mejores límites conocidos sobre su tamaño involucran logaritmos binarios. En particular, todos los grafos tienen un grupo o un conjunto independiente de tamaño al menos ⁠1/2⁠ log ₂  n (1 − o (1)) y casi todos los gráficos no tienen una camarilla o 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 mezclas aleatorias de Gilbert-Shannon-Reeds , se puede demostrar que la cantidad de veces que es necesario mezclar una baraja de n cartas, mediante mezclas aleatorias , para obtener una distribución de permutaciones que sea cercana a uniformemente aleatoria, 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]

Complejidad computacional

Búsqueda binaria en una matriz ordenada, un algoritmo cuya complejidad temporal implica 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 algoritmos, sino también porque los logaritmos binarios aparecen en el análisis de algoritmos basados ​​en ramificaciones bidireccionales. ^[14] Si un problema tiene inicialmente 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 de nuevo 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 forma similar, un} árbol de búsqueda binaria perfectamente equilibrado que contiene n elementos tiene una altura log ₂ ( n + 1) − 1 . ^[35]

El tiempo de ejecución de un algoritmo se expresa generalmente 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í solo por un factor constante, también se puede decir que los algoritmos que se ejecutan en tiempo O (log ₂  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 se puede omitir. ^{[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 un tiempo de ejecución O ( n  log  n ) a veces se denominan linealímicos . ^[37] Algunos ejemplos de algoritmos con un tiempo de ejecución O (log n ) o O ( n log n ) son:

• Ordenamiento rápido de tiempo promedio y otros algoritmos de ordenamiento por comparación ^[38]
• Búsqueda en árboles de búsqueda binarios balanceados ^[39]
• Exponenciación por cuadrado ^[40]
• Subsecuencia creciente más larga ^[41]

Los logaritmos binarios también ocurren 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 n × n en tiempo O ( n ^{log ₂  7} ) . ^[43] La ocurrencia de logaritmos binarios en estos tiempos de ejecución puede explicarse por referencia al teorema maestro para 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 la intensidad con la que se expresan diferentes genes en una muestra de material biológico. Las diferentes tasas de expresión de un gen se comparan a menudo utilizando el logaritmo binario de la relación de las 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 con una relación logarítmica de 1 , una tasa de expresión reducida a la mitad se puede describir con una relación logarítmica de −1 y una tasa de expresión sin cambios se puede describir con 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 proporciones de intensidad, o en visualizaciones como el diagrama MA y el diagrama RA que rotan y escalan estos diagramas de dispersión de proporciones logarítmicas. ^[45]

Teoría musical

En teoría musical , el intervalo o diferencia perceptual entre dos tonos está determinada 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 en las que difieren dos tonos es el logaritmo binario de su relación de frecuencias. ^[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 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 debería ser igual a la medida del intervalo de x a z . Tal medida está dada por el cent , que divide la octava en 1200 intervalos iguales ( 12 semitonos de 100 cents cada uno). Matemáticamente, dados los 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 1000 en lugar de 1200. ^[47 ]

Programación deportiva

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 simple requerido 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 (ya sea que dos equipos se queden fuera de la primera ronda o que un equipo se quede fuera de la segunda ronda). La misma cantidad de rondas también es necesaria para determinar un ganador claro en un torneo de 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. Un solo 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 de la lente durante la exposición, y t es el número de segundos de exposición. ^[51]

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

Cálculo

Calculadora científica HP-35 (1972). Las teclas log y ln están en la fila superior; no hay  tecla log _{2 .}

Conversión desde otras bases

Una forma sencilla 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 usar 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 números enteros

El logaritmo binario se puede convertir en una función de números enteros y de números enteros redondeándolo hacia arriba o hacia abajo. Estas dos formas de logaritmo binario entero están relacionadas por 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 . 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}(0)\rfloor =-1}$

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

El logaritmo binario entero se puede interpretar como el índice basado en cero del bit 1 más significativo en 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 se pueden utilizar para encontrar rápidamente el logaritmo binario. Las funciones flsand flslen el núcleo Linux ^[55] y en algunas versiones de la biblioteca de software libc también calculan el logaritmo binario (redondeado a un entero, más uno).

Aproximación iterativa

Para un número real positivo general , el logaritmo binario puede calcularse 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 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 los números de punto flotante normalizados , la parte entera está dada por el exponente de punto flotante, ^[57] y para los números enteros se puede determinar realizando una operación de conteo de ceros iniciales . ^[58]

La parte fraccionaria del resultado es log ₂  y y se puede calcular iterativamente, utilizando solo 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 semiabierto [1, 2) . Si y = 1 , entonces el algoritmo está completo y la parte fraccionaria es cero.
2. De lo contrario, eleva y al cuadrado 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 modo que z se encuentre 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 utilizando el mismo método.

El resultado de esto se expresa mediante las siguientes fórmulas recursivas, en las que es el número de cuadraturas 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. De lo contrario, es una serie infinita que converge de acuerdo con la prueba de la razón , ya que cada término es estrictamente menor que el anterior (ya que cada 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 acepta argumentos de precisión doble , pero sus variantes permiten que el argumento sea de precisión simple o que sea un 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 , que devuelve un número complejo. ^[60]

Referencias

1. Groza, Vivian Shaw; Shelley, Susanne M. (1972), Matemáticas 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ág. 237, y otra copia ampliada a potencias negativas aparece en la pág. 249b.
3. Joseph, GG (2011), La cresta del pavo real: raíces no europeas de las matemáticas (3.ª ed.), Princeton University Press, pág. 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, Progress in Computer Science and Applied Logic, 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ág. 128, ISBN 978-3-642-96080-2.
8. Por ejemplo, Microsoft Excel proporciona la IMLOG2función para logaritmos binarios complejos: véase Bourg, David M. (2006), Excel Scientific and Engineering Cookbook, O'Reilly Media, pág. 232, ISBN 978-0-596-55317-3.
9. Kolman, Bernard; 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 Enciclopedia de Matemáticas y en 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. Manual de estilo de Chicago (25.ª edición), University of Chicago Press, 2003, pág. 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, pág. 11. La misma notación apareció en la segunda edición de 1973 del mismo libro (pág. 23) pero sin el crédito a Reingold.
15. Trucco, Ernesto (1956), "Una nota sobre el contenido de información de los grafos", Bull. Math. Biophys. , 18 (2): 129–135, doi :10.1007/BF02477836, MR  0077919.
16. Mitchell, John N. (1962), "Multiplicación y división por computadora usando logaritmos binarios", IRE Transactions on Electronic Computers , EC-11 (4): 512–517, doi :10.1109/TEC.1962.5219391.
17. Fiche, 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ág. 33, ISBN 978-1-118-58577-1A menos que se especifique lo contrario, tomaremos todos los logaritmos en base 2..
19. Goodrich, Michael T. ; Tamassia, Roberto (2002), Algorithm Design: Foundations, Analysis, and Internet Examples , 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 omnipresente 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ág. 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 la norma ISO 31-11, véase Thompson, Ambler; Taylor, Barry M (marzo de 2008), Guía para el uso del Sistema Internacional de Unidades (SI) — Publicación especial 811 del NIST, edición de 2008 — Segunda impresión (PDF) , NIST , pág. 33.
25. Para la norma ISO 80000-2, véase "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), Domando lo infinito, Quercus, pág. 120, ISBN 9781623654733En 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ág. 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, MR  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), "Siguiendo el rastro del juego de 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 algoritmos, Cambridge University Press, pág. 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 génica 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 por espectrometría de masas, John Wiley & Sons, pág. 105, ISBN 978-1-118-49378-6.
46. Campbell, Murray; Greated, Clive (1994), Guía 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 la ciencia del deporte, Cengage Learning, pág. 282, ISBN 978-1-4180-5529-5.
49. Allen, Elizabeth; Triantaphillidou, Sophie (2011), El manual de fotografía, Taylor & Francis, pág. 228, ISBN 978-0-240-52037-7.
50. Davis, Phil (1998), Más allá del sistema de zonas, CRC Press, pág. 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 Visual Effects Society: flujo de trabajo y técnicas, 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ág. 332, ISBN 978-1-4665-6186-1.
54. Warren Jr., Henry S. (2002), Hacker's Delight (1.ª ed.), Addison Wesley , pág. 215, ISBN 978-0-201-91465-8
55. fls, API del kernel de Linux, kernel.org , recuperado el 17 de octubre de 2010.
56. Majithia, JC; Levan, D. (1973), "Una nota sobre los cálculos de logaritmos en base 2", Actas del IEEE , 61 (10): 1519–1520, doi :10.1109/PROC.1973.9318.
57. Stephenson, Ian (2005), "9.6 Funciones rápidas de potencia, 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ág. 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ág. 226.
60. Redfern, Darren; Campbell, Colin (1998), 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), "Encontrar el logaritmo en base 2 de un entero de N bits en operaciones O(lg(N))", Bit Twiddling Hacks , Stanford University , consultado el 25 de noviembre de 2015
• Feynman y la máquina de conexiones