Двоичный логарифм

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
График двоичного логарифма

Двоичный логарифмлогарифм по основанию 2. Другими словами, двоичный логарифм числа есть решение уравнения

Двоичный логарифм вещественного числа существует, если Согласно стандарту ISO 31-11, он обозначается[1] или . Примеры:

История[править | править код]

Исторически двоичные логарифмы нашли своё первое применение в теории музыки, когда Леонард Эйлер установил: двоичный логарифм отношения частот двух музыкальных тонов равен количеству октав, которое отделяет один тон от другого. Эйлер также опубликовал таблицу двоичных логарифмов целых чисел от 1 до 8 с точностью до семи десятичных знаков[2][3].

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

Алгебраические свойства[править | править код]

В нижеследующей таблице предполагается, что все значения положительны[4]:

Формула Пример
Произведение
Частное от деления
Степень
Корень

Существует очевидное обобщение приведенных формул на случай, когда допускаются отрицательные переменные, например:

Формула для логарифма произведения без труда обобщается на произвольное количество сомножителей:

Связь двоичного, натурального и десятичного логарифмов:

Функция двоичного логарифма[править | править код]

Если рассматривать логарифмируемое число как переменную, мы получим функцию двоичного логарифма: . Она определена при всех область значений: . График этой функции часто называется логарифмикой, она обратна для функции . Функция монотонно возрастает, непрерывна и дифференцируема всюду, где она определена. Производная для неё даётся формулой[5]:

Ось ординат является вертикальной асимптотой, поскольку:

Применение[править | править код]

Теория информации[править | править код]

Двоичный логарифм натурального числа позволяет определить число цифр во внутреннем компьютерном (битовом) представлении этого числа:

(скобки обозначают целую часть числа)

Информационная энтропия — мера количества информации, также основана на двоичном логарифме

Сложность рекурсивных алгоритмов[править | править код]

Оценка асимптотической сложности рекурсивных алгоритмов, основанных на принципе «разделяй и властвуй»[6] — таких, как быстрая сортировка, быстрое преобразование Фурье, двоичный поиск и т. п.

Комбинаторика[править | править код]

Если двоичное дерево содержит узлов, то его высота не меньше, чем (равенство достигается, если является степенью 2)[7]. Соответственно, число Стралера — Философова для речной системы с притоками не превышает[8] .

Изометрическая размерность частичного куба с вершинами не меньше, чем Число рёбер куба не более, чем равенство имеет место, когда частичный куб является графом гиперкуба[9].

Согласно теореме Рамсея, неориентированный граф с вершинами содержит либо клику, либо независимое множество, размер которого логарифмически зависит от Точный размер этого множества неизвестен, но наилучшие в настоящий момент оценки содержат двоичные логарифмы.

Другие применения[править | править код]

Число кругов игры по олимпийской системе равно двоичному логарифму от числа участников соревнований[10].

В теории музыки, чтобы решить вопрос о том, на сколько частей делить октаву, требуется отыскать рациональное приближение для Если разложить это число в непрерывную дробь, то третья подходящая дробь (7/12) позволяет обосновать классическое деление октавы на 12 полутонов[11].

Примечания[править | править код]

  1. Иногда, особенно в немецких изданиях, двоичный логарифм обозначается (от лат. logarithmus dyadis), см. Bauer, Friedrich L. Origins and Foundations of Computing: In Cooperation with Heinz Nixdorf MuseumsForum. — Springer Science & Business Media, 2009. — P. 54. — ISBN 978-3-642-02991-2.
  2. Euler, Leonhard (1739), "Chapter VII. De Variorum Intervallorum Receptis Appelationibus", Tentamen novae theoriae musicae ex certissismis harmoniae principiis dilucide expositae, Saint Petersburg Academy, с. 102—112, <http://eulerarchive.maa.org/pages/E033.html> .
  3. Tegg, Thomas (1829), "Binary logarithms", London encyclopaedia; or, Universal dictionary of science, art, literature and practical mechanics: comprising a popular view of the present state of knowledge, Volume 4, с. 142–143, <https://books.google.com/books?id=E-ZTAAAAYAAJ&pg=PA142> .
  4. Выгодский М. Я. Справочник по элементарной математике, 1978, с. 187..
  5. Логарифмическая функция. // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1982. — Т. 3.
  6. Harel, David; Feldman, Yishai A. Algorithmics: the spirit of computing. — New York: Addison-Wesley, 2004. — P. 143. — ISBN 978-0-321-11784-7.
  7. Leiss, Ernst L. (2006), A Programmer's Companion to Algorithm Analysis, CRC Press, с. 28, ISBN 978-1-4200-1170-8, <https://books.google.com/books?id=E6BNGFQ6m_IC&pg=RA2-PA28> 
  8. Devroye, L. & Kruszewski, P. (1996), "On the Horton–Strahler number for random tries", RAIRO Informatique Théorique et Applications Т. 30 (5): 443—456, doi:10.1051/ita/1996300504431, <https://eudml.org/doc/92635> .
  9. Eppstein, David (2005), "The lattice dimension of a graph", European Journal of Combinatorics Т. 26 (5): 585–592, DOI 10.1016/j.ejc.2004.05.001 
  10. Харин А. А. Организация и проведение соревнований. Методическое пособие. — Ижевск: УдГУ, 2011. — С. 27.
  11. Шилов Г. Е. Простая гамма. Устройство музыкальной шкалы. М.: Физматгиз, 1963. 20 с. Серия «Популярные лекции по математике», выпуск 37.

Литература[править | править код]

Ссылки[править | править код]