Где я могу узнать о логарифмах? [закрытый]

Логарифмическая функция является просто инверсией показательной функции в том же смысле, что вычитание является инверсией дополнения. Так же, как это уравнение:

a = b + c

состояния тот же факт как это уравнение:

a - c = b

это уравнение:

b ** p = x

(где ** возводит в степень) указывает тот же факт как это уравнение:

log [base b] (x) = p

, Хотя b может быть любое число (например, log [base 10] (10,000) = 4) "естественная" база для Математики e (2.718281828...), о который посмотрите здесь .

"Общие" логарифмы, используемые больше в разработке, используют основу 10. Быстрое-и-грязное (акцент на грязный) интерпретация общего (базируются 10) логарифм некоторого номера x - то, что это - то меньше, чем количество десятичных цифр, требуемых выражать, нумерует размер x.

Как пример того, о чем говорит Chris, алгоритм, который изменяет сложность на основе числа битов в значении (вероятно), собирается описать эффективность O (журнал (n)).

Другой повседневный пример экспонент (и следовательно логарифмы) находится в формате IEEE числа с плавающей точкой .

Одно из более "прохладных" приложений логарифмов, которые я нашел, Спиральное устройство хранения данных . Это - хеш-таблица, которая позволяет Вам разделять один блок за один раз, когда таблица растет, перемещая меньше чем половину записей в том блоке к тому же, новом блоке. В отличие от линейного хеширования, где производительность варьируется циклически и все блоки имеют тенденцию быть разделенными примерно в то же время, спиральное хеширование позволяет хороший, гладкий рост таблицы.

Это было опубликовано приблизительно 30 лет назад G. N. N. Martin, о котором я не смог узнать много помимо того, что он также изобрел Диапазон, Кодирующий . Походит на умного парня! Я не смог получить копию его исходной статьи, но На - Г … ke статья Larson "Динамические хеш-таблицы" имеет очень четкое описание.

Самое очевидное использование в каждом примере программирования является точностью. Помещенный просто, рассмотрите целые числа без знака хранения. Сколько битов необходимо сохранить X? Ну, максимальное значение, которое можно сохранить в n битах, 2^n - 1, таким образом, можно быть нужен log_2 X + 1 бит для хранения X. Теперь можно выбрать короткий, международный, слово, долго и т.д. легко.

Логарифмы используются довольно часто в диаграммах и графиках, когда одна или обе оси покрывают большой спектр значений.

Некоторые природные явления лучше всего выражаются на логарифмическом масштабе; некоторыми примерами являются уровни звукового давления ( SPL в дБ) и величина землетрясения ( шкала Рихтера ).

Выезд MIT Открывает Courseware: Введение в Алгоритмы . Свободный educations. Потрясающий.

Один пример, из многих: Вычисление составных процентов на очень маленьком уровне с большим количеством периодов.

можно сделать это самый простой путь, даже с помощью быстрого возведения в степень, но точность может пострадать, из-за способа, которым хранятся плавания, и вычисление s * r питание n все еще берет O (ln (n)) операции.

С логарифмами, это несколько более точно.

А = ln (s * r питание n) = ln (s) + n * ln (r)
Два поиска в Вашей базе данных логарифма дают Вам, ln (s) и ln (r), с ln (r) начинаются очень маленький, и плавающая работа над их лучшей точностью около 0 результатов = exp (A), обратный поиск здесь.

Это - также единственный действительно эффективный путь, если Вы работаете с экспонентами нецелого числа, для извлечения кубических корней, например.

Многие (многие!) отношения в реальном мире являются логарифмическими. Например, меня не удивило бы, если распределение очков репутации на Переполнении стека , регистрируются нормальный . У подавляющего большинства пользователей будет множество репутации 1, и у горстки людей будет недосягаемо высокая репутация. При применении логарифмического преобразования к тому распределению это, вероятно, была бы почти линейная зависимость. Быстрое сканирование https://stackoverflow.com/users? page=667 показывает это, чтобы быть верным.

Вы могли бы быть более знакомы с Длинный Хвост понятие, которое является приложением логарифмического распределения.

Я рекомендую e: История Номера для хорошей основы важности логарифмов, их исследования и отношения к природным явлениям.

Другой способ посмотреть на него смотрит на количество основных множителей в числе. Я уверен, что Вы видите, как это все имеет отношение в следующих примерах.

Десятичное число (базируются 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

Двоичный файл (базируются 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

Шестнадцатеричный (базируются 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

, Если Вы хотите думать в переменных:

• журнал N ( X ) = Y
• ( N^Y) = X

Логарифмы в программировании также часто используются в описании эффективности алгоритма с помощью Большая нотация .

O, Например, алгоритм двоичного поиска имел бы худший вариант развития событий O (журнал (n)) (на отсортированном наборе), тогда как худший случай линейного поиска является O (n)

Я видел логарифмы, используемые для отображения облаков тегов. Это - страница, которая объясняет это:

Алгоритм распределения

Я предполагаю, что Вы услышали о логарифмах с контекстами к завершению времени.

примером бетона А были бы алгоритмы поиска. Учитывая ряд заказанных данных (думают сортированный массив интервала), Вы хотите найти индексный ключ к значению в тех данных. Мы можем извлечь выгоду из того, что массив отсортирован (1, 2, 6, 192, 404, 9595, 50000, например). Скажем, мы мы хотим найти индекс к значению 2. Мы можем минимизировать наше пространство поиска путем отбора (игнорирование) половины массива каждый шаг. Мы запускаем этот поиск путем тестирования значения в середину массива. Существует 7 значений в массиве, мы затем делаем индекс 7/2 = 3.5 = 3, поскольку международный массив [3] равняется 192. Значение, которое мы ищем, равняется 2, поэтому мы хотим продолжить поиск в более низкой половине пространства поиска. Мы полностью игнорируем индекс 4, 5, 6, так как они все выше, чем 192, и в свою очередь также выше затем 2. Теперь у нас есть пространство поиска, которое похоже (1, 2, 6). Мы затем индексируем в середину снова (повторный процесс), и мы находим 2 немедленно. Поиск завершен, индекс к 2 равняется 1.

Это - очень небольшой пример, но он показывает, как такой алгоритм работает.

Для 16 значений, необходимо искать в максимальные 4 раза. Для 32 значений Вы ищете макс. 5 раз, 64 значения 6 раз и так далее.. 1 048 576 значений ищутся на 20 шагах. Это намного более быстро, чем необходимость сравнить каждый объект в массиве отдельно. Конечно, это только работает на отсортированные наборы данных.

Единственная проблема, которую я могу вспомнить, должна вычислить продукт столбца в SQL. SQL Server не имеет ПРОДУКТА () агрегатной функцией, таким образом, это было выполнено с помощью суммы логарифмов (использующий LOG10 () функция) каждого значения. Основной недостаток состоял в том, что все числа в столбце должны были быть положительными и ненулевыми (Вы не можете вычислить логарифм на отрицательное число или нуль).

Журналы являются типом метаарифметики. Это - образ мыслей каждого числа как (возможно зафиксированный) основа, повышенная до экспоненты. Операции выполняются на одних только экспонентах. Это означает, что можно сделать умножение и разделение путем выполнения дополнения и вычитания журналов. Другими словами, Вы помещаете свои данные в пространство журнала, выполняете комплект арифметики и задерживаете его в пространство нежурнала. Если потеря точности с плавающей точкой и издержки преобразования в или из пространства журнала являются дешевыми, то у Вас может быть полная победа вовремя.

Один гладкий прием, который можно сделать с журналами, вычисляют количество символов, которые возьмет число при печати путем взятия log-base-2 числа и разделите его на log-base-10 (2), который является постоянным временем по сравнению с рядом, умножается.

В моем собственном исследовании я натолкнулся на несколько полезных ресурсов:

раздел логарифмов Академии Хана

Это - потрясающий набор уроков по логарифмам. Этот комментарий от 6-го классника подводит итог его приятно:

Огромное спасибо. На этой неделе мой учитель по математике сказал мне бросать вызов мне, таким образом, я попробовал логарифмы. Сначала я был похож, 'Я не могу сделать этого, это слишком твердо'. Затем я посмотрел видео, и теперь они - даже забава! Я нахожусь в 6-м классе, мой учитель по математике впечатлен. Я не могу в полной мере отблагодарить Вас.

Тест Ruby № 105: Матчи Турнира

Эта статья содержат хороший пример использования основы 2 журнала для определения количества раундов, требуемых завершать турнир нокаута, учитывая x команды.

Обладающее интуицией Руководство По Показательным функциям & E

превосходное, интуитивное (как Вы ожидали бы, учитывая заголовок), руководство по [1 120] e, основа натурального логарифма. Много иллюстраций и примеров делает это драгоценным камнем статьи.