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

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

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

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

$\mathrm{lb}<!--\; \; -->1=0;\mathrm{lb}<!--\; \; -->2=1;\mathrm{lb}<!--\; \; -->16=4$$\operatorname{lb} 1=0;\, \operatorname{lb} 2=1;\, \operatorname{lb} 16=4$

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

ИсторияПравить

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

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

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

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

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

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

$\mathrm{lb}<!--\; \; -->|xy|=\mathrm{lb}<!--\; \; -->(|x|)+\mathrm{lb}<!--\; \; -->(|y|),$$\operatorname{lb} |x y| = \operatorname{lb} (|x|) + \operatorname{lb} (|y|),$ 

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

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

$\mathrm{lb}<!--\; \; -->(x_1{x}_2\dots <!--\; \dots \; -->x_n)=\mathrm{lb}<!--\; \; -->(x_1)+\mathrm{lb}<!--\; \; -->(x_2)+\cdots <!--\; \cdots \; -->+\mathrm{lb}<!--\; \; -->(x_n)$$\operatorname{lb}(x_1 x_2 \dots x_n) = \operatorname{lb} (x_1) + \operatorname{lb} (x_2) + \dots + \operatorname{lb} (x_n)$ 

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

$\mathrm{lb}<!--\; \; -->x\approx <!--\; \approx \; -->\mathrm{1,442}695\ln <!--\; \; -->x$$\operatorname{lb} x \approx 1{,}442695 \ln x$ 

$\mathrm{lb}<!--\; \; -->x\approx <!--\; \approx \; -->\mathrm{3,321}928\lg <!--\; \; -->x$$\operatorname{lb} x \approx 3{,}321928 \lg x$ 

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

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

$\frac{d}{dx}\mathrm{lb}<!--\; \; -->x=\frac{\mathrm{lb}<!--\; \; -->e}{x}$$\frac {d} {dx} \operatorname{lb} x = \frac {\operatorname{lb} e} {x}$ 

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

$\underset{x\to <!--\; \to \; -->0+0}{lim}\mathrm{lb}<!--\; \; -->x=-<!--\; -\; -->\mathrm{\infty <!--\; \infty \; -->}$$\lim_{x \to 0+0} \operatorname{lb} x = - \infty$ 

ПрименениеПравить

Теория информацииПравить

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

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

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

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

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

КомбинаторикаПравить

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

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

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

Другие примененияПравить

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

В теории музыки, чтобы решить вопрос о том, на сколько частей делить октаву, требуется отыскать рациональное приближение для ${\log }_2<!--\; \; -->\frac{3}{2}\approx <!--\; \approx \; -->\mathrm{0,585.}$$\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