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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

$\mathrm{lb}(x_1{x}_2\dots x_n)=\mathrm{lb}(x_1)+\mathrm{lb}(x_2)+\dots +\mathrm{lb}(x_n)$

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

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

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

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

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

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

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

$\underset{x\to 0+0}{\lim }\mathrm{lb}x=-\mathrm{\infty }$

Применение

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

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

$b(N)=\lfloor \mathrm{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 полутонов.

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Книга

Ссылки

• Таблица двоичных логарифмов целых чисел от 1 до 100. Шаблон:Wayback