Двоичный логарифм
Двоичный логарифм — логарифм по основанию 2. Другими словами, двоичный логарифм числа [math]\displaystyle{ b }[/math] есть решение уравнения [math]\displaystyle{ 2^x=b. }[/math]
Двоичный логарифм вещественного числа [math]\displaystyle{ b }[/math] существует, если [math]\displaystyle{ b\gt 0. }[/math] Согласно стандарту ISO 31-11, он обозначается[1] [math]\displaystyle{ \operatorname{lb} b, }[/math] [math]\displaystyle{ \operatorname{lb} (b) }[/math] или [math]\displaystyle{ \log_2 b }[/math]. Примеры:
- [math]\displaystyle{ \operatorname{lb} 1=0;\, \operatorname{lb} 2=1;\, \operatorname{lb} 16=4 }[/math]
- [math]\displaystyle{ \operatorname{lb} 0{,}5=-1;\, \operatorname{lb} \frac{1}{256}=-8 }[/math]
История
Исторически двоичные логарифмы нашли своё первое применение в теории музыки, когда Леонард Эйлер установил: двоичный логарифм отношения частот двух музыкальных тонов равен количеству октав, которое отделяет один тон от другого. Эйлер также опубликовал таблицу двоичных логарифмов целых чисел от 1 до 8 с точностью до семи десятичных знаков[2][3].
С созданием информатики выяснилось, что двоичные логарифмы необходимы для определения количества битов, требующихся для кодирования сообщения. Другие области, в которых часто используется двоичный логарифм, включают комбинаторику, биоинформатику, криптографию, проведение спортивных турниров и фотографию. Стандартная функция для вычисления двоичного логарифма предусмотрена во многих распространённых системах программирования.
Алгебраические свойства
В нижеследующей таблице предполагается, что все значения положительны[4]:
| Формула | Пример | |
|---|---|---|
| Произведение | [math]\displaystyle{ \operatorname{lb}(x y) = \operatorname{lb} (x) + \operatorname{lb} (y) }[/math] | [math]\displaystyle{ \operatorname{lb} (256) = \operatorname{lb}(16 \cdot 16) = \operatorname{lb} (16) + \operatorname{lb} (16) = 4 + 4 = 8 }[/math] |
| Частное от деления | [math]\displaystyle{ \operatorname{lb} \!\left(\frac x y \right) = \operatorname{lb} (x) - \operatorname{lb} (y) }[/math] | [math]\displaystyle{ \operatorname{lb} \left(\frac{1}{32}\right) = \operatorname{lb} (1) - \operatorname{lb} (32) = 0 - 5 = -5 }[/math] |
| Степень | [math]\displaystyle{ \operatorname{lb}(x^p) = p \operatorname{lb} (x) }[/math] | [math]\displaystyle{ \operatorname{lb} (1024) = \operatorname{lb} (2^{10}) = 10 \operatorname{lb} (2) = 10 }[/math] |
| Корень | [math]\displaystyle{ \operatorname{lb} \sqrt[p]{x} = \frac {\operatorname{lb} (x)} p }[/math] | [math]\displaystyle{ \operatorname{lb} \sqrt{8} = \frac{1}{2}\operatorname{lb} 8 = \frac{3}{2} = 1{,}5 }[/math] |
Существует очевидное обобщение приведенных формул на случай, когда допускаются отрицательные переменные, например:
- [math]\displaystyle{ \operatorname{lb} |x y| = \operatorname{lb} (|x|) + \operatorname{lb} (|y|), }[/math]
- [math]\displaystyle{ \operatorname{lb} \!\left|\frac x y \right| = \operatorname{lb} (|x|) - \operatorname{lb} (|y|), }[/math]
Формула для логарифма произведения без труда обобщается на произвольное количество сомножителей:
- [math]\displaystyle{ \operatorname{lb}(x_1 x_2 \dots x_n) = \operatorname{lb} (x_1) + \operatorname{lb} (x_2) + \dots + \operatorname{lb} (x_n) }[/math]
Связь двоичного, натурального и десятичного логарифмов:
- [math]\displaystyle{ \operatorname{lb} x \approx 1{,}442695 \ln x }[/math]
- [math]\displaystyle{ \operatorname{lb} x \approx 3{,}321928 \lg x }[/math]
Функция двоичного логарифма
Если рассматривать логарифмируемое число как переменную, мы получим функцию двоичного логарифма: [math]\displaystyle{ y = \operatorname{lb} x }[/math]. Она определена при всех [math]\displaystyle{ x\gt 0, }[/math] область значений: [math]\displaystyle{ E(y)=(-\infty; + \infty ) }[/math]. График этой функции часто называется логарифмикой, она обратна для функции [math]\displaystyle{ y=2^x }[/math]. Функция монотонно возрастает, непрерывна и дифференцируема всюду, где она определена. Производная для неё даётся формулой[5]:
- [math]\displaystyle{ \frac {d} {dx} \operatorname{lb} x = \frac {\operatorname{lb} e} {x} }[/math]
Ось ординат [math]\displaystyle{ (x=0) }[/math] является вертикальной асимптотой, поскольку:
- [math]\displaystyle{ \lim_{x \to 0+0} \operatorname{lb} x = - \infty }[/math]
Применение
Теория информации
Двоичный логарифм натурального числа [math]\displaystyle{ N }[/math] позволяет определить число цифр [math]\displaystyle{ b(N) }[/math] во внутреннем компьютерном (битовом) представлении этого числа:
- [math]\displaystyle{ b(N) = \lfloor \operatorname{lb} N \rfloor + 1 }[/math] (скобки обозначают целую часть числа)
Информационная энтропия — мера количества информации, также основана на двоичном логарифме
Сложность рекурсивных алгоритмов
Оценка асимптотической сложности рекурсивных алгоритмов, основанных на принципе «разделяй и властвуй»[6] — таких, как быстрая сортировка, быстрое преобразование Фурье, двоичный поиск и т. п.
Комбинаторика
Если двоичное дерево содержит [math]\displaystyle{ n }[/math] узлов, то его высота не меньше, чем [math]\displaystyle{ \log_2 n }[/math] (равенство достигается, если [math]\displaystyle{ n }[/math] является степенью 2)[7]. Соответственно, число Стралера — Философова для речной системы с [math]\displaystyle{ n }[/math] притоками не превышает[8] [math]\displaystyle{ \log_2 n + 1 }[/math].
Изометрическая размерность частичного куба с [math]\displaystyle{ n }[/math] вершинами не меньше, чем [math]\displaystyle{ \log_2 n. }[/math] Число рёбер куба не более, чем [math]\displaystyle{ \frac12 n\log_2 n, }[/math] равенство имеет место, когда частичный куб является графом гиперкуба[9].
Согласно теореме Рамсея, неориентированный граф с [math]\displaystyle{ n }[/math] вершинами содержит либо клику, либо независимое множество, размер которого логарифмически зависит от [math]\displaystyle{ n. }[/math] Точный размер этого множества неизвестен, но наилучшие в настоящий момент оценки содержат двоичные логарифмы.
Другие применения
Число кругов игры по олимпийской системе равно двоичному логарифму от числа участников соревнований[10].
В теории музыки, чтобы решить вопрос о том, на сколько частей делить октаву, требуется отыскать рациональное приближение для [math]\displaystyle{ \log_2 \frac {3}{2} \approx 0{,}585. }[/math] Если разложить это число в непрерывную дробь, то третья подходящая дробь (7/12) позволяет обосновать классическое деление октавы на 12 полутонов[11].
Примечания
- ↑ Иногда, особенно в немецких изданиях, двоичный логарифм обозначается [math]\displaystyle{ \operatorname{ld} b }[/math] (от лат. 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.
- ↑ 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> Архивная копия от 11 октября 2018 на Wayback Machine.
- ↑ 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> Архивная копия от 23 мая 2021 на Wayback Machine.
- ↑ Выгодский М. Я. Справочник по элементарной математике, 1978, с. 187..
- ↑ Логарифмическая функция. // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1982. — Т. 3.
- ↑ Harel, David; Feldman, Yishai A. Algorithmics: the spirit of computing. — New York: Addison-Wesley, 2004. — P. 143. — ISBN 978-0-321-11784-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> Архивная копия от 12 августа 2020 на Wayback Machine
- ↑ 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> Архивная копия от 7 октября 2015 на Wayback Machine.
- ↑ 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
- ↑ Харин А. А. Организация и проведение соревнований. Методическое пособие. — Ижевск: УдГУ, 2011. — С. 27.
- ↑ Шилов Г. Е. Простая гамма. Устройство музыкальной шкалы. Архивная копия от 22 февраля 2014 на Wayback Machine М.: Физматгиз, 1963. 20 с. Серия «Популярные лекции по математике», выпуск 37.
Литература
- Выгодский М. Я. Справочник по элементарной математике. — изд. 25-е. — М.: Наука, 1978. — ISBN 5-17-009554-6.
- Корн Г., Корн Т. Справочник по математике (для научных работников и инженеров). — М.: Наука, 1973. — 720 с.
- Фихтенгольц Г. М. Курс дифференциального и интегрального исчисления. — изд. 6-е. — М.: Наука, 1966. — 680 с.
Ссылки
- Таблица двоичных логарифмов целых чисел от 1 до 100. Архивная копия от 12 августа 2019 на Wayback Machine