Двоичный логарифм — логарифм по основанию 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 полутонов .

Примечания

Литература

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

Ссылки

• от 12 августа 2019 на Wayback Machine