math - logaritmicas - ¿Dónde puedo aprender sobre logaritmos?

logaritmos khan academy (19)

Escucho logaritmos mencionados bastante en el contexto de programación. Parecen ser la solución a muchos problemas y, sin embargo, parece que no puedo encontrar una forma de usarlos en el mundo real. He leído la entrada de Wikipedia y eso, francamente, no me deja nada sabio.

Entonces, ¿dónde puedo aprender sobre los problemas de programación del mundo real que resuelven los logaritmos? ¿Alguien tiene ejemplos de problemas que enfrentaron que se resolvieron implementando un logaritmo?

El único problema que puedo recordar es tener que calcular el producto de una columna en SQL. SQL Server no tiene una función agregada PRODUCT (), por lo que esto se logró usando una suma de los logaritmos (usando la función LOG10 ()) de cada valor. El principal inconveniente fue que todos los números en la columna tenían que ser positivos y no ser cero (no se puede calcular un logaritmo en un número negativo o cero).

El uso más obvio en cada ejemplo de programación es la precisión. En pocas palabras, considere almacenar enteros sin signo. ¿Cuántos bits necesitas para almacenar X? Bueno, el valor máximo que puede almacenar en n bits es 2 ^ n - 1, por lo que puede necesitar log_2 X + 1 bit para almacenar X. Ahora puede elegir short, int, word, long etc con facilidad.

He visto logaritmos usados para mostrar nubes de etiquetas. Esta es una página que lo explica:

Algoritmo de distribución de fuentes de Tag Cloud

Los logaritmos en la programación también se utilizan con frecuencia para describir la eficacia de un algoritmo que utiliza la notación Big O.

Por ejemplo, un algoritmo de búsqueda binaria tendría el peor escenario posible de O (log (n)) (en un conjunto ordenado), mientras que el peor caso de una búsqueda lineal es O (n)

Los logaritmos se usan con bastante frecuencia en cuadros y gráficos, cuando uno o ambos ejes cubren una amplia gama de valores.

Algunos fenómenos naturales se expresan mejor en una escala logarítmica; algunos ejemplos son los niveles de presión sonora ( SPL en dB) y la magnitud del terremoto ( escala de Richter ).

Otra forma de verlo es mirando la cantidad de multiplicadores base en un número. Estoy seguro de que puede ver cómo se relaciona todo esto en los siguientes ejemplos.

Decimal (base 10):

log10 (1) = 0, (10 ^ 0) = 1
log10 (10) = 1, (10 ^ 1) = 10
log10 (100) = 2, (10 ^ 2) = 100
log10 (1000) = 3, (10 ^ 3) = 1000
log10 (10000) = 4, (10 ^ 4) = 10000
log10 (100000) = 5, (10 ^ 5) = 100000

Binario (base 2):

log2 (1) = 0, (2 ^ 0) = 1
log2 (2) = 1, (2 ^ 1) = 2
log2 (4) = 2, (2 ^ 2) = 4
log2 (8) = 3, (2 ^ 3) = 8
log2 (16) = 4, (2 ^ 4) = 16
log2 (32) = 5, (2 ^ 5) = 32
log2 (64) = 6, (2 ^ 6) = 64
log2 (128) = 7, (2 ^ 7) = 128

Hexadecimal (base 16):

log16 (1) = 0, (16 ^ 0) = 1
log16 (16) = 1, (16 ^ 1) = 16
log16 (256) = 2, (16 ^ 2) = 256
log16 (4096) = 3, (16 ^ 3) = 4096
log16 (65536) = 4, (16 ^ 4) = 65536

Si quieres pensar en variables:

log N ( X ) = Y
( N ^ Y ) = X

Recomiendo e: La historia de un número para una buena base de la importancia de los logaritmos, su descubrimiento y relevancia para los fenómenos naturales.

Supongo que ha oído hablar de logaritmos con contextos para la consumación del tiempo.

Un ejemplo concreto serían los algoritmos de búsqueda. Dado un conjunto de datos ordenados (piense en una matriz ordenada de int), desea encontrar la clave de índice para un valor en esos datos. Podemos beneficiarnos del hecho de que la matriz está ordenada (1, 2, 6, 192, 404, 9595, 50000, por ejemplo). Digamos que queremos encontrar el índice al valor 2. Podemos minimizar nuestro espacio de búsqueda eliminando (ignorando) la mitad de la matriz en cada paso. Comenzamos esta búsqueda probando el valor en el medio de la matriz. Hay 7 valores en la matriz, luego hacemos que el índice 7/2 = 3.5 = 3 como int. array [3] es 192. El valor que buscamos es 2, por lo tanto, queremos continuar la búsqueda en la mitad inferior del espacio de búsqueda. Ignoramos completamente los índices 4, 5 y 6, ya que todos son más altos que 192 y, a su vez, también más altos que 2. Ahora tenemos un espacio de búsqueda que se parece a (1, 2, 6). Luego indexamos nuevamente en medio (proceso de repetición), y encontramos el 2 instantáneamente. La búsqueda está completa, el índice de 2 es 1.

Este es un ejemplo muy pequeño, pero muestra cómo funciona un algoritmo de este tipo.

Para 16 valores, debe buscar al máximo 4 veces. Para 32 valores, busca máx. 5 veces, 64 valores 6 veces, etc. 1048576 valores se buscan en 20 pasos. Esto es mucho más rápido que tener que comparar cada elemento en la matriz por separado. Por supuesto, esto solo funciona para colecciones ordenadas de datos.

Un ejemplo, de muchos: calcular intereses compuestos a una tasa muy pequeña con una gran cantidad de períodos.

Puede hacerlo de la manera más directa, incluso usando una exponenciación rápida, pero la precisión puede verse afectada, debido a la forma en que se almacenan los flotadores y al calcular s * r, la potencia n todavía toma operaciones O (ln (n)).

Con los logaritmos, es algo más preciso.

A = ln (s * r potencia n) = ln (s) + n * ln (r)
Dos búsquedas en su base de datos de logaritmo le dan ln (s) y ln (r), con ln (r) comienzan muy pequeñas y las flotantes funcionan con su mejor precisión cerca de 0 result = exp (A), una búsqueda inversa aquí.

También es la única manera realmente eficiente si trabajas con exponentes no enteros, para extraer raíces cúbicas, por ejemplo.

Una de las aplicaciones más "geniales" de los logaritmos que he encontrado es el almacenamiento en espiral . Es una tabla hash que le permite dividir un cubo a la vez a medida que crece la tabla, reubicando menos de la mitad de los registros en ese depósito en el mismo cubo nuevo. A diferencia del hashing lineal, donde el rendimiento varía cíclicamente y todos los cubos tienden a dividirse más o menos al mismo tiempo, el hashing en espiral permite un crecimiento agradable y suave de la mesa.

Fue publicado hace unos 30 años por GNN Martin, del que no he podido aprender mucho además del hecho de que él también inventó Range Encoding . ¡Parece un tipo inteligente! No he podido obtener una copia de su trabajo original, pero el artículo de Per-Åke Larson "Tablas dinámicas hash" tiene una descripción muy clara.

Vea el Open Courseware de MIT: Introducción a los Algoritmos . Educacion gratuita Increíble.

Una función logarítmica es simplemente la inversa de una función exponencial, en el mismo sentido en que la resta es la inversa de la suma. Justo como esta ecuación:

a = b + c

establece el mismo hecho que esta ecuación:

a - c = b

esta ecuación:

b ** p = x

(donde ** está aumentando a una potencia) establece el mismo hecho que esta ecuación:

log [base b] (x) = p

Aunque b puede ser cualquier número (por ejemplo, log [base 10] (10,000) = 4 ) la base "natural" para Matemáticas es e (2.718281828 ...) sobre la cual ver aquí .

Los logaritmos "comunes", usados más en ingeniería, usan una base de 10. Una interpretación rápida y sucia (énfasis en sucio) del logaritmo común (base 10) de algún número x es que es uno menos que el número de dígitos decimales requeridos para expresar números del tamaño de x .

Desmitificar el Logaritmo Natural (ln) en BetterExplained es lo mejor que he encontrado. Borra los conceptos de la base y lo ayuda a comprender los conceptos subyacentes. Después de eso, todo parece un juego de niños.

Aquí hay algunos sitios que he usado:

Utilicé logaritmos para calcular la apreciación anual de una casa para determinar si el vendedor estaba siendo justo.

Ecuaciones de apreciación de la casa

Aquí está la ecuación básica:

Precio anterior = p
Nuevo precio = n
Tasa de apreciación = r
Años de apreciación = y

p * (1 + r)^y = n

Entonces, si el precio de hace 6 años era de $ 191,000 (revisando el sitio de su auditor de couty) y el precio de venta es de $ 284,000, ¿cuál es la tasa de revalorización (que no tomaría en cuenta ningún costo de mejora único)?

191,000 * (1 + r)^6 = 284,000 (1 + r)^6 = 284,000 / 191,000 = 1.486 Using a property of exponents and logarithms… 6 ( log (1 + r) ) = log 1.486 log (1 + r) = (log 1.486) / 6 = 0.02866 Using another property of exponents and logarithms… 10 0.02866 = 1 + r 1.068 = 1 + r r = 1.068 – 1 = 0.068 = 6.8% (kind of high!)

Para determinar qué precio razonable sería ... use 4% y permita las mejoras que hayan realizado (que deberían figurar en el id. Web eran importantes ... pero no incluiría la remodelación de baño / cocina, etc.)

191,000 * (1 + 0.04)^6 = n n = 241,675 + reasonable cost of improvement which of course will depreciate over time and should not represent 100% of the cost of the improvement

Supongamos que tiene $ 1000 y está en una cuenta de ahorros con un 2,4% de interés.

¿Cuántos años tienes que esperar hasta que tengas $ 2000 para comprar una computadora portátil nueva?

1000 × 1.024 ^x = 2000

1.024 ^x = 2

x = log _1.024 2 = 29.23 años

Los registros son un tipo de meta-aritmética. Es una forma de pensar en cada número como una base (posiblemente fija) elevada a un exponente. Las operaciones se realizan únicamente en los exponentes. Esto significa que puede hacer multiplicaciones y divisiones haciendo sumas y restas de los registros. En otras palabras, coloque sus datos en el espacio de registro, realice un conjunto de aritmética y vuelva a colocarlo en un espacio que no sea de registro. Si la pérdida de precisión en punto flotante y la sobrecarga de transformar dentro o fuera del espacio de registro es barata, entonces puede obtener una ganancia global a tiempo.

Un truco hábil que puede hacer con los registros es calcular el número de caracteres que tomará un número cuando se imprime tomando el log-base-2 del número y divídalo por el log-base-10 (2), que es el tiempo constante comparado con un conjunto de multiplicaciones

En mi propia investigación encontré algunos recursos útiles:

Sección de logaritmos de Khan Academy

Este es un gran conjunto de lecciones sobre logaritmos. Este comentario de un alumno de 6to grado lo resume muy bien:

Muchas gracias. Esta semana, mi maestra de matemáticas me dijo que me desafiara, así que probé logaritmos. Al principio yo estaba como, ''No puedo hacer esto, es muy difícil''. Luego vi el video, ¡y ahora incluso son divertidos! Estoy en sexto grado, mi maestra de matemáticas está impresionada. No puedo agradecerte lo suficiente.

Ruby Quiz # 105: enfrentamientos de torneos

Este artículo contiene un buen ejemplo del uso de un registro de base 2 para determinar el número de rondas necesarias para completar un torneo de eliminación directa con x equipos.

Una guía intuitiva para las funciones exponenciales y E

Un excelente, intuitivo (como era de esperar, dado el título), guía para e , la base del logaritmo natural. Muchas ilustraciones y ejemplos hacen de esta joya un artículo.

Desmitificando el Logaritmo Natural (ln)

Esta es la continuación del artículo sobre e y analiza el logaritmo natural (ln) que, usando la explicación intuitiva dada en el artículo, "le da el tiempo necesario para alcanzar un cierto nivel de crecimiento".

En realidad, hay un montón de buen contenido en el sitio Better Explained . Verdaderamente, un recurso espléndido.

Otra herramienta con la que me había encontrado antes pero que me olvidé por completo es Instacalc . Parece ser por la misma persona, Kalid Azad, quien crea el sitio Better Explained. Es una herramienta realmente útil al hackear con las matemáticas.

Como un ejemplo de lo que Chris está hablando, un algoritmo que cambia la complejidad basado en el número de bits en un valor (probablemente) tendrá una eficiencia descrita por O (log (n)).

Otro ejemplo cotidiano de exponentes (y, por lo tanto, logaritmos) está en el formato de números de punto flotante IEEE .

Muchas (¡muchas!) Relaciones en el mundo real son logarítmicas. Por ejemplo, no me sorprendería si la distribución de los puntajes de reputación en Desbordamiento de pila es logarítmica normal . La gran mayoría de los usuarios tendrán puntajes de reputación de 1 y un puñado de personas tendrá una reputación increíblemente alta. Si aplica una transformación logarítmica a esa distribución, probablemente sería casi una relación lineal. Un análisis rápido de https://.com/users?page=667 muestra que esto es cierto.

Es posible que esté más familiarizado con el concepto de The Long Tail , que es una aplicación de la distribución logarítmica.