En matemáticas , el logaritmo binario ( log 2 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 ,
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 . La función logaritmo binario es la función inversa de la potencia de dos funciones. Además de log 2 , las notaciones alternativas para el logaritmo binario incluyen lg , ld , lb (la notación preferida por ISO 31-11 e ISO 80000-2 ) y (con una declaración previa de que la base predeterminada es 2) log .
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 frecuencia 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 numérico 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 son 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. La parte entera de un logaritmo binario se puede encontrar usando la operación de buscar el primer conjunto en un valor entero, o buscando el exponente de un valor de punto flotante . La parte fraccionaria del logaritmo se puede calcular de manera eficiente.
Historia
Los poderes de dos se conocen desde la antigüedad; por ejemplo, aparecen en Euclid's Elements , Props. IX.32 (sobre la factorización de potencias de dos) y IX.36 (la mitad del teorema de Euclides-Euler , sobre la estructura de números pares perfectos ). Y el logaritmo binario de una potencia de dos es solo 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. La inversión de las filas de estas tablas permite interpretarlas como tablas de logaritmos binarios. [1] [2]
Antes que Stifel, al matemático Jain 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 uniformemente 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 enteros, dando el orden 2-ádico en lugar del logaritmo. [4]
La forma moderna de un logaritmo binario, que se aplica a cualquier número (no solo 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 de logaritmo binario puede definirse 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, se puede definir 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]
Al igual que con otros logaritmos, el logaritmo binario obedece a las siguientes ecuaciones, que se pueden usar para simplificar fórmulas que combinan logaritmos binarios con multiplicación o exponenciación: [9]
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 se escribe a menudo como log 2 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 listada 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 se remonta a 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 usa 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 , ISO 31-11 e ISO 80000-2 recomiendan otra notación más, lb n . De acuerdo con estos estándares, lg n no debe usarse para el logaritmo binario, ya que está reservado para el logaritmo común log 10 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 2 n , es decir, [12]
En la teoría de la información, la definición de la cantidad de autoinformación y entropía de la información a menudo se expresa con el logaritmo binario, lo que corresponde a hacer del bit la unidad fundamental de información. Sin embargo, el logaritmo natural y el nat también se utilizan en notaciones alternativas para estas definiciones. [26]
Combinatoria
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 2 n , con igualdad cuando n es una potencia de dos y el árbol es un árbol binario completo . [28] En relación con esto, el número de Strahler de un sistema fluvial con n corrientes tributarias es como máximo log 2 n + 1 . [29]
- Cada familia de conjuntos con n conjuntos diferentes tiene al menos log 2 n elementos en su unión, con igualdad cuando la familia es un conjunto de poder . [30]
- Cada cubo parcial con n vértices tiene una dimensión isométrica de al menos log 2 n , y tiene como máximo1/2 n log 2 n aristas, con igualdad cuando el cubo parcial es un gráfico de hipercubo . [31]
- De acuerdo con el teorema de Ramsey , cada grafo 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 de su tamaño involucran logaritmos binarios. En particular, todas las gráficas tienen una camarilla o un conjunto independiente de tamaño al menos1/2log 2 n (1 - o (1)) y casi todas las gráficas no tienen un grupo o conjunto independiente de tamaño mayor que 2 log 2 n (1 + o (1)) . [32]
- A partir de un análisis matemático del modelo de Gilbert-Shannon-cañas de baraja al azar, se puede demostrar que el número de veces que uno necesita para mezclar un n mazo de cartas -Card, utilizando baraja de rifle , para conseguir una distribución de permutaciones que está cerca uniformemente aleatorio, es aproximadamente3/2log 2 n . Este cálculo constituye la base para la recomendación de que los mazos de 52 cartas se barajen siete veces. [33]
Complejidad computacional
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 los algoritmos, sino también porque los logaritmos binarios ocurren en el análisis de algoritmos basados en ramificaciones bidireccionales. [14] Si un problema inicialmente tiene n opciones para su solución, y cada iteración del algoritmo reduce el número de opciones en un factor de dos, entonces el número de iteraciones necesarias para seleccionar una sola opción es nuevamente la parte integral de log 2 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 2 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 2 ( n + 1) - 1 . [35]
El tiempo de ejecución de un algoritmo generalmente se expresa en notación O grande , que se usa 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 2 n ) se ejecutan en, digamos, O (log 13 n ) tiempo. 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 2 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 lineales . [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 medio y otros algoritmos de clasificación por comparación [38]
- Búsqueda en árboles de búsqueda binarios equilibrados [39]
- Exponenciación por cuadratura [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 el tiempo O ( n log 2 3 ) , [42] y el algoritmo de Strassen para multiplicar n × n matrices en el tiempo O ( n log 2 7 ) . [43] La ocurrencia de logaritmos binarios en estos tiempos de ejecución se puede explicar por referencia al teorema maestro para las recurrencias de divide y vencerás .
Bioinformática
En bioinformática , los microarrays se utilizan para medir la fuerza con la que se expresan los genes diferentes en una muestra de material biológico. Las diferentes tasas de expresión de un gen a menudo se comparan utilizando el logaritmo binario de la proporción de tasas de expresión: la proporción logarítmica de dos tasas de expresión se define como el logaritmo binario de la proporció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 razón logarítmica de 1 , una tasa de expresión dividida a la mitad se puede describir con una razó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 el diagrama MA y el diagrama RA que rotan y escalan estos diagramas de dispersión de relación logarítmica. [45]
Teoría musical
En teoría musical , el intervalo o diferencia de percepción entre dos tonos está determinado 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 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 fino que una octava y que sea aditivo (como lo son los logaritmos) en lugar de multiplicativo (como la frecuencia las proporciones son). Es decir, si tonos x , y , y z forma una secuencia ascendente de tonos, entonces la medida del intervalo de x a y , más la medida del intervalo de desde y a z debe ser igual a la medida del intervalo de x a z . Tal medida viene dada por el centavo , que divide la octava en 1200 intervalos iguales ( 12 semitonos de 100 centavos cada uno). Matemáticamente, tonos dados con frecuencias f 1 y f 2 , el número de centavos en el intervalo de f 1 a f 2 es [46]
La milioctava se define de la misma manera, pero con un multiplicador de 1000 en lugar de 1200 . [47]
Programación deportiva
En juegos competitivos y deportes 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 requeridas para determinar un ganador. Por ejemplo, un torneo de 4 jugadores requiere log 2 4 = 2 rondas para determinar el ganador, un torneo de 32 equipos requiere log 2 32 = 5 rondas, etc. En este caso, para n jugadores / equipos donde n no es una potencia de 2, log 2 n se redondea ya que es necesario tener al menos una ronda en la que no jueguen todos los competidores restantes. Por ejemplo, log 2 6 es aproximadamente 2.585 , que se redondea a 3 , lo que indica que un torneo de 6 equipos requiere 3 rondas (o dos equipos se quedan fuera de la primera ronda o un equipo se queda fuera de 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 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
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 paradas) 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
Conversión de otras bases
Una manera fácil de calcular log 2 n en calculadoras que no tienen una función log 2 es usar el logaritmo natural ( ln ) o el logaritmo común ( log o log 10 ), que se encuentran en la mayoría de las calculadoras científicas . El cambio específico de las fórmulas de base logarítmica para esto son: [50] [53]
o aproximadamente
Redondeo de enteros
El logaritmo binario se puede convertir en una función a partir de números enteros y enteros redondeándolo hacia arriba o hacia abajo. Estas dos formas de logaritmo binario entero están relacionadas por esta fórmula:
- [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 ) .
- [54]
El logaritmo binario entero se puede interpretar como el índice de base cero del 1 bit más significativo de la entrada. En este sentido es el complemento de la operación find first set , 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 usar para encontrar rápidamente el logaritmo binario. Las funciones fls
y flsl
en 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 único entero n tal que 2 n ≤ 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 (2 - n x ) . [56] En otras palabras:
Para números de coma flotante normalizados , la parte entera viene dada por el exponente de coma flotante, [57] y para números enteros se puede determinar realizando una operación de conteo de ceros iniciales. [58]
La parte fraccionaria del resultado es log 2 y y se puede calcular de forma iterativa, utilizando solo multiplicaciones y divisiones elementales. [56] El algoritmo para calcular la parte fraccionaria se puede describir en pseudocódigo de la siguiente manera:
- Comience con un número real y en el intervalo semiabierto [1, 2) . Si y = 1 , entonces el algoritmo está hecho y la parte fraccionaria es cero.
- De lo contrario, eleve al cuadrado y repetidamente hasta que el resultado z se encuentre en el intervalo [2, 4) . Sea m el número de cuadraturas necesarias. Es decir, z = y 2 m con m elegido de manera que z esté en [2, 4) .
- Tomando el logaritmo de ambos lados y haciendo algo de álgebra:
- 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 es el número de cuadraturas requeridas en la i -ésima iteración del algoritmo:
En el caso especial en el que la parte fraccionaria en el paso 1 resulta ser cero, esta es una secuencia finita que termina en algún punto. En caso contrario, es una serie infinita que converge según la prueba de razón , ya que cada término es estrictamente menor que el anterior (ya que cada m i > 0 ). Para un uso práctico, esta serie infinita debe truncarse para alcanzar 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 1 + m 2 + ... + m i ) . [56]
Soporte de biblioteca de software
La log2
función está incluida en la norma funciones matemáticas C . La versión predeterminada de esta función toma argumentos de precisión doble, pero sus variantes permiten que el argumento sea de precisión simple o un doble largo . [59] En entornos informáticos que admiten números complejos y conversión de tipos implícitos, como MATLABlog2
, se permite que el argumento de la función sea un número negativo y devuelva uno complejo. [60]
Referencias
- ^ Groza, Vivian Shaw; Shelley, Susanne M. (1972), Precálculo matemático , Nueva York: Holt, Rinehart y Winston, p. 182, ISBN 978-0-03-077670-0.
- ^ 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 ampliada a potencias negativas aparece en la p. 249b.
- ^ Joseph, GG (2011), The Crest of the Peacock: Non-European Roots of Mathematics (3.a ed.), Princeton University Press, p. 352.
- ^ Ver, 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, 22 , Birkhäuser, p. 35, ISBN 978-3-0348-8037-4.
- ^ Euler, Leonhard (1739), "Capítulo 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.
- ^ 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.
- ^ Batschelet, E. (2012), Introducción a las matemáticas para científicos de la vida , Springer, p. 128, ISBN 978-3-642-96080-2.
- ^ Por ejemplo, Microsoft Excel proporciona la
IMLOG2
función para logaritmos binarios complejos: consulte Bourg, David M. (2006), Excel Scientific and Engineering Cookbook , O'Reilly Media, pág. 232, ISBN 978-0-596-55317-3. - ^ 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.
- ↑ Por ejemplo, esta es la notación utilizada en la Enciclopedia de Matemáticas y The Princeton Companion to Mathematics .
- ^ a b 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
- ^ a b Sedgewick, Robert ; Wayne, Kevin Daniel (2011), Algoritmos , Addison-Wesley Professional, pág. 185, ISBN 978-0-321-57351-3.
- ^ El Manual de estilo de Chicago (25ª ed.), University of Chicago Press, 2003, pág. 530.
- ^ a b Knuth, Donald E. (1997), Algoritmos fundamentales , El arte de la programación informática , 1 (3.a ed.), Addison-Wesley Professional, ISBN 978-0-321-63574-7, p. 11 . La misma notación estaba en la segunda edición de 1973 del mismo libro (p. 23) pero sin el crédito de Reingold.
- ^ Trucco, Ernesto (1956), "Una nota sobre el contenido informativo de los gráficos", Bull. Matemáticas. Biophys. , 18 (2): 129-135, doi : 10.1007 / BF02477836 , MR 0077919.
- ^ Mitchell, John N. (1962), "Multiplicación y división por computadora usando logaritmos binarios", Transacciones IRE en computadoras electrónicas , EC-11 (4): 512–517, doi : 10.1109 / TEC.1962.5219391.
- ^ Fiche, Georges; Hebuterne, Gerard (2013), Matemáticas para ingenieros , John Wiley & Sons, p. 152, ISBN 978-1-118-62333-6,
A continuación, y a menos que se indique lo contrario, la notación log x siempre representa el logaritmo en base 2 de x
. - ^ 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
. - ^ a b 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 .
- ^ a b c 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
- ^ Tietze, Ulrich; Schenk, Christoph (1999), Halbleiter-Schaltungstechnik (en alemán) (1ª reimpresión corregida, 11ª ed.), Springer Verlag , p. 1370 , ISBN 3-540-64192-0
- ^ Bauer, Friedrich L. (2009), Orígenes y fundamentos de la informática: en cooperación con el foro de museos Heinz Nixdorf , Springer Science & Business Media , p. 54, ISBN 978-3-642-02991-2.
- ^ Para DIN 1302 ver Brockhaus Enzyklopädie in zwanzig Bänden [ Enciclopedia Brockhaus en veinte volúmenes ] (en alemán), 11 , Wiesbaden: FA Brockhaus, 1970, p. 554, ISBN 978-3-7653-0000-4.
- ^ 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 811 del NIST, edición de 2008 - Segunda impresión (PDF) , NIST , p. 33.
- ^ 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 , pag. 18.
- ^ Van der Lubbe, Jan CA (1997), Teoría de la información , Cambridge University Press, p. 3, ISBN 978-0-521-46760-5.
- ^ 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
. - ^ Leiss, Ernst L. (2006), Compañero del programador para el análisis de algoritmos , CRC Press, p. 28, ISBN 978-1-4200-1170-8.
- ^ 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.
- ^ De manera equivalente, una familia con k elementos distintos tiene como máximo 2 k conjuntos distintos, con igualdad cuando es un conjunto de potencias.
- ^ 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.
- ^ Graham, Ronald L .; Rothschild, Bruce L .; Spencer, Joel H. (1980), Teoría de Ramsey , Wiley-Interscience, pág. 78.
- ^ Bayer, Dave ; Diaconis, Persi (1992), "Trailing the dovetail shuffle to its guarida", The Annals of Applied Probability , 2 (2): 294–313, doi : 10.1214 / aoap / 1177005705 , JSTOR 2959752 , MR 1161056.
- ^ Mehlhorn, Kurt ; Sanders, Peter (2008), "2.5 Un ejemplo: búsqueda binaria", Algoritmos y estructuras de datos: The Basic Toolbox (PDF) , Springer, págs. 34–36, ISBN 978-3-540-77977-3.
- ^ Roberts, Fred ; Tesman, Barry (2009), Combinatoria aplicada (2ª ed.), CRC Press, p. 206, ISBN 978-1-4200-9983-6.
- ^ 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.
- ^ Sedgewick y Wayne (2011) , p. 186 .
- ^ Cormen y col., P. 156; Goodrich y Tamassia, pág. 238.
- ^ Cormen y col., P. 276; Goodrich y Tamassia, pág. 159.
- ^ Cormen y col., Págs. 879–880; Goodrich y Tamassia, pág. 464.
- ^ Edmonds, Jeff (2008), Cómo pensar en algoritmos , Cambridge University Press, pág. 302, ISBN 978-1-139-47175-6.
- ^ Cormen y col., P. 844; Goodrich y Tamassia, pág. 279.
- ^ Cormen et al., Sección 28.2.
- ^ Causton, Helen; Quackenbush, John; Brazma, Alvis (2009), Microarray Gene Expression Data Analysis: A Beginner's Guide , John Wiley & Sons, págs. 49–50, ISBN 978-1-4443-1156-3.
- ^ Eidhammer, Ingvar; Barsnes, Harald; Eide, Geir Egil; Martens, Lennart (2012), Métodos estadísticos y computacionales para la cuantificación de proteínas por espectrometría de masas , John Wiley & Sons, p. 105, ISBN 978-1-118-49378-6.
- ^ a b Campbell, Murray; Greated, Clive (1994), The Musician's Guide to Acoustics , Oxford University Press, pág. 78, ISBN 978-0-19-159167-9.
- ^ Randel, Don Michael , ed. (2003), The Harvard Dictionary of Music (4ª ed.), The Belknap Press de Harvard University Press, p. 416, ISBN 978-0-674-01163-2.
- ^ 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.
- ^ Allen, Elizabeth; Triantaphillidou, Sophie (2011), El manual de fotografía , Taylor & Francis, p. 228, ISBN 978-0-240-52037-7.
- ^ a b Davis, Phil (1998), Más allá del sistema de zonas , CRC Press, p. 17, ISBN 978-1-136-09294-7.
- ^ Allen y Triantaphillidou (2011) , p. 235 .
- ^ Zwerman, Susan; Okun, Jeffrey A. (2012), Manual de la sociedad de efectos visuales: Flujo de trabajo y técnicas , CRC Press, p. 205, ISBN 978-1-136-13614-6.
- ^ Bauer, Craig P. (2013), Historia secreta: La historia de la criptología , CRC Press, p. 332, ISBN 978-1-4665-6186-1.
- ^ a b Warren Jr., Henry S. (2002), Hacker's Delight (1ª ed.), Addison Wesley , p. 215, ISBN 978-0-201-91465-8
- ^ FLS , la API del núcleo de Linux, kernel.org , recuperados 2010-10-17.
- ^ a b c d Majithia, JC; Levan, D. (1973), "Una nota sobre cálculos de logaritmos en base 2", Proceedings of the IEEE , 61 (10): 1519-1520, doi : 10.1109 / PROC.1973.9318.
- ^ 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.
- ^ 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.
- ^ "7.12.6.10 Las funciones log2", especificación ISO / IEC 9899: 1999 (PDF) , p. 226.
- ^ 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), "Encuentra 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