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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Применение

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

• Выгодский М. Я. Справочник по элементарной математике. — изд. 25-е. — М.: Наука, 1978. — ISBN 5-17-009554-6.
• Корн Г., Корн Т. Справочник по математике (для научных работников и инженеров). — М.: Наука, 1973. — 720 с.
• Фихтенгольц Г. М. Курс дифференциального и интегрального исчисления. — изд. 6-е. — М.: Наука, 1966. — 680 с.

Ссылки

• Таблица двоичных логарифмов целых чисел от 1 до 100. Архивная копия от 12 августа 2019 на Wayback Machine