Русская Википедия:Двоичный логарифм

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Файл:Binary logarithm plot with ticks.svg

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

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

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

<math>\operatorname{lb} 1=0;\, \operatorname{lb} 2=1;\, \operatorname{lb} 16=4</math>

<math>\operatorname{lb} 0{,}5=-1;\, \operatorname{lb} \frac{1}{256}=-8</math>

История

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

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

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

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

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

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

<math>\operatorname{lb} |x y| = \operatorname{lb} (|x|) + \operatorname{lb} (|y|),</math>

<math>\operatorname{lb} \!\left|\frac x y \right| = \operatorname{lb} (|x|) - \operatorname{lb} (|y|),</math>

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

<math> \operatorname{lb}(x_1 x_2 \dots x_n) = \operatorname{lb} (x_1) + \operatorname{lb} (x_2) + \dots + \operatorname{lb} (x_n)</math>

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

<math>\operatorname{lb} x \approx 1{,}442695 \ln x</math>

<math>\operatorname{lb} x \approx 3{,}321928 \lg x</math>

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

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

<math>\frac {d} {dx} \operatorname{lb} x = \frac {\operatorname{lb} e} {x}</math>

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

<math>\lim_{x \to 0+0} \operatorname{lb} x = - \infty</math>

Применение

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

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

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

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

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

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

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

Если двоичное дерево содержит <math>n</math> узлов, то его высота не меньше, чем <math>\log_2 n</math> (равенство достигается, если <math>n</math> является степенью 2). Соответственно, число Стралера — Философова для речной системы с <math>n</math> притоками не превышает <math>\log_2 n + 1</math>.

Изометрическая размерность частичного куба с <math>n</math> вершинами не меньше, чем <math>\log_2 n.</math> Число рёбер куба не более, чем <math>\frac12 n\log_2 n,</math> равенство имеет место, когда частичный куб является графом гиперкуба.

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

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

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

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

Литература

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

Ссылки

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