Двоичный логарифм - NiNa.Az

Двоичный логарифм — логарифм по основанию 2. Другими словами, двоичный логарифм числа ${\displaystyle b}$ есть решение уравнения ${\displaystyle 2^{x}=b.}$

График двоичного логарифма

Двоичный логарифм вещественного числа ${\displaystyle b}$ существует, если ${\displaystyle b>0.}$ Согласно стандарту ISO 31-11, он обозначается${\displaystyle \operatorname {lb} b,}$ ${\displaystyle \operatorname {lb} (b)}$ или ${\displaystyle \log _{2}b}$. Примеры:

${\displaystyle \operatorname {lb} 1=0;\,\operatorname {lb} 2=1;\,\operatorname {lb} 16=4}$

${\displaystyle \operatorname {lb} 0{,}5=-1;\,\operatorname {lb} {\frac {1}{256}}=-8}$

История

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

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

Алгебраические свойства

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

	Формула	Пример
Произведение	${\displaystyle \operatorname {lb} (xy)=\operatorname {lb} (x)+\operatorname {lb} (y)}$	${\displaystyle \operatorname {lb} (256)=\operatorname {lb} (16\cdot 16)=\operatorname {lb} (16)+\operatorname {lb} (16)=4+4=8}$
Частное от деления	${\displaystyle \operatorname {lb} \!\left({\frac {x}{y}}\right)=\operatorname {lb} (x)-\operatorname {lb} (y)}$	${\displaystyle \operatorname {lb} \left({\frac {1}{32}}\right)=\operatorname {lb} (1)-\operatorname {lb} (32)=0-5=-5}$
Степень	${\displaystyle \operatorname {lb} (x^{p})=p\operatorname {lb} (x)}$	${\displaystyle \operatorname {lb} (1024)=\operatorname {lb} (2^{10})=10\operatorname {lb} (2)=10}$
Корень	${\displaystyle \operatorname {lb} {\sqrt[{p}]{x}}={\frac {\operatorname {lb} (x)}{p}}}$	${\displaystyle \operatorname {lb} {\sqrt {8}}={\frac {1}{2}}\operatorname {lb} 8={\frac {3}{2}}=1{,}5}$

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

${\displaystyle \operatorname {lb} |xy|=\operatorname {lb} (|x|)+\operatorname {lb} (|y|),}$

${\displaystyle \operatorname {lb} \!\left|{\frac {x}{y}}\right|=\operatorname {lb} (|x|)-\operatorname {lb} (|y|),}$

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

${\displaystyle \operatorname {lb} (x_{1}x_{2}\dots x_{n})=\operatorname {lb} (x_{1})+\operatorname {lb} (x_{2})+\dots +\operatorname {lb} (x_{n})}$

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

${\displaystyle \operatorname {lb} x\approx 1{,}442695\ln x}$

${\displaystyle \operatorname {lb} x\approx 3{,}321928\lg x}$

Функция двоичного логарифма

Если рассматривать логарифмируемое число как переменную, мы получим функцию двоичного логарифма: ${\displaystyle y=\operatorname {lb} x}$. Она определена при всех ${\displaystyle x>0,}$ область значений: ${\displaystyle E(y)=(-\infty ;+\infty )}$. График этой функции часто называется логарифмикой, она обратна для функции ${\displaystyle y=2^{x}}$. Функция монотонно возрастает, непрерывна и дифференцируема всюду, где она определена. Производная для неё даётся формулой:

${\displaystyle {\frac {d}{dx}}\operatorname {lb} x={\frac {\operatorname {lb} e}{x}}}$

Ось ординат ${\displaystyle (x=0)}$ является вертикальной асимптотой, поскольку:

${\displaystyle \lim _{x\to 0+0}\operatorname {lb} x=-\infty }$

Применение

Теория информации

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

${\displaystyle b(N)=\lfloor \operatorname {lb} N\rfloor +1}$ (скобки обозначают целую часть числа)

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

Сложность рекурсивных алгоритмов

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

Комбинаторика

Если двоичное дерево содержит ${\displaystyle n}$ узлов, то его высота не меньше, чем ${\displaystyle \log _{2}n}$ (равенство достигается, если ${\displaystyle n}$ является степенью 2). Соответственно, число Стралера — Философова для речной системы с ${\displaystyle n}$ притоками не превышает${\displaystyle \log _{2}n+1}$.

Изометрическая размерность частичного куба с ${\displaystyle n}$ вершинами не меньше, чем ${\displaystyle \log _{2}n.}$ Число рёбер куба не более, чем ${\displaystyle {\frac {1}{2}}n\log _{2}n,}$ равенство имеет место, когда частичный куб является графом гиперкуба.

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

Другие применения

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

В теории музыки, чтобы решить вопрос о том, на сколько частей делить октаву, требуется отыскать рациональное приближение для ${\displaystyle \log _{2}{\frac {3}{2}}\approx 0{,}585.}$ Если разложить это число в непрерывную дробь, то третья подходящая дробь (7/12) позволяет обосновать классическое деление октавы на 12 полутонов.

Примечания

1. Иногда, особенно в немецких изданиях, двоичный логарифм обозначается ${\displaystyle \operatorname {ld} b}$ (от лат. 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, pp. 102–112, Архивировано 11 октября 2018, Дата обращения: 6 августа 2019 Источник  (неопр.). Дата обращения: 6 августа 2019. Архивировано 11 октября 2018 года..
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, pp. 142–143 Источник  (неопр.). Дата обращения: 6 августа 2019. Архивировано 23 мая 2021 года..
4. Выгодский М. Я. Справочник по элементарной математике, 1978, с. 187..
5. Логарифмическая функция. // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1982. — Т. 3. Архивировано 16 октября 2013 года.
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, p. 28, ISBN 978-1-4200-1170-8 Источник  (неопр.). Дата обращения: 6 августа 2019. Архивировано 12 августа 2020 года.
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, MR 1435732, Архивировано 7 октября 2015, Дата обращения: 6 августа 2019 Источник  (неопр.). Дата обращения: 6 августа 2019. Архивировано 7 октября 2015 года..
9. Eppstein, David (2005), The lattice dimension of a graph, European Journal of Combinatorics, 26 (5): 585–592, arXiv:cs.DS/0402028, doi:10.1016/j.ejc.2004.05.001, MR 2127682
10. Харин А. А. Организация и проведение соревнований. Методическое пособие. — Ижевск: УдГУ, 2011. — С. 27. Архивировано 24 июля 2020 года.
11. Шилов Г. Е. Простая гамма. Устройство музыкальной шкалы. Архивная копия от 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