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

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

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

Двоичный логарифм числа $b$ существует, если $~b>0.$ Он обозначается $~\operatorname{lb} b$ (согласно ISO 31-11), $~\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]:

	Формула	Пример
Произведение	$\operatorname{lb}(x y) = \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} |x y| = \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 )$. График этой кривой часто называется логарифмикой^[2].

Функция монотонно возрастает, непрерывна и дифференцируема всюду, где она определена. Производная для неё даётся формулой:

$\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$ (скобки обозначают целую часть числа)

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

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

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

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

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

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

См. также

• Бит
• Десятичный логарифм.
• Натуральный логарифм.

Литература

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

Ссылки

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

Примечания

1. ↑ Выгодский М. Я. Справочник по элементарной математике, 1978, с. 187.
2. ↑ Логарифмическая функция. // Математическая энциклопедия (в 5 томах). — М.: Советская Энциклопедия, 1982. — Т. 3.
3. ↑ Harel, David; Feldman, Yishai A. Algorithmics: the spirit of computing. — New York: Addison-Wesley, 2004. — P. 143. — ISBN 978-0-321-11784-7
4. ↑ Шилов Г. Е. Простая гамма. Устройство музыкальной шкалы. М.: Физматгиз, 1963. 20 с. Серия «Популярные лекции по математике», выпуск 37.