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

Двоичный логарифм — это математическая функция, обратная к возведению числа 2 в степень. Двоичный логарифм числа \(x\) (обозначается \(\log_2 x\) или \(\operatorname{lb} x\)) равен показателю степени, в которую нужно возвести 2, чтобы получить \(x\). Иными словами, если \(2^y = x\), то \(y = \log_2 x\). Функция определена для положительных вещественных чисел \(x > 0\) и принимает вещественные значения.

Определение и обозначения

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

• \(\log_2 x\) — наиболее распространённое обозначение.
• \(\operatorname{lb} x\) (от лат. logarithmus binarius) — стандартное обозначение в международной системе ISO 80000-2.
• \(\operatorname{lg} x\) — в некоторых русскоязычных учебниках и в информатике (однако в других контекстах \(\lg\) может означать десятичный логарифм).
• \(\operatorname{ld} x\) (от англ. logarithmus dualis) — встречается в немецкоязычной литературе.

История

Понятие логарифма впервые было введено шотландским математиком Джоном Непером в начале XVII века. Однако Непер использовал логарифмы по основанию, близкому к \(1/e\), а не по основанию 2. Двоичный логарифм как самостоятельная функция получил развитие в связи с задачами, связанными с двоичной системой счисления и теорией информации.

В 1928 году американский инженер и математик Ральф Хартли предложил использовать двоичный логарифм для количественной оценки информации в сообщениях. В 1948 году Клод Шеннон в своей основополагающей статье «Математическая теория связи» заложил основы теории информации, где двоичный логарифм стал основной мерой количества информации (бит).

Свойства

Двоичный логарифм наследует все основные свойства логарифмической функции:

• Основное логарифмическое тождество: \(2^{\log_2 x} = x\).
• Логарифм произведения: \(\log_2 (x \cdot y) = \log_2 x + \log_2 y\).
• Логарифм частного: \(\log_2 \frac{x}{y} = \log_2 x - \log_2 y\).
• Логарифм степени: \(\log_2 (x^p) = p \cdot \log_2 x\).
• Переход к другому основанию: \(\log_2 x = \frac{\log_a x}{\log_a 2}\) для любого положительного \(a \neq 1\).
• Монотонность: функция \(\log_2 x\) строго возрастает на интервале \((0, +\infty)\).
• Значения в ключевых точках: \(\log_2 1 = 0\), \(\log_2 2 = 1\), \(\log_2 4 = 2\), \(\log_2 0.5 = -1\).

Применение

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

Теория информации и кодирование

В теории информации количество информации в битах, содержащееся в сообщении, определяется через двоичный логарифм вероятности события. Формула Шеннона для энтропии \(H\) дискретного источника:

\[ H = -\sum_{i=1}^{n} p_i \log_2 p_i \]

где \(p_i\) — вероятность \(i\)-го события. Единица измерения — бит.

Информатика и вычислительная техника

• Глубина рекурсии и сложность алгоритмов: Двоичный логарифм часто встречается в оценке времени выполнения алгоритмов (например, бинарный поиск имеет сложность \(O(\log_2 n)\)). Количество шагов для поиска элемента в отсортированном массиве из \(n\) элементов равно \(\lceil \log_2 n \rceil\).
• Представление чисел: Количество бит, необходимое для представления целого неотрицательного числа \(N\) в двоичной системе, равно \(\lfloor \log_2 N \rfloor + 1\).
• Размер адресного пространства: Адресация памяти в компьютерах основана на степенях двойки; например, 32-битная адресация позволяет адресовать \(2^{32}\) байт, что равно 4 ГБ.
• Структуры данных: Высота сбалансированного бинарного дерева поиска с \(n\) узлами равна \(O(\log_2 n)\).

Музыка и акустика

В музыкальной теории двоичный логарифм используется для расчёта частот нот в равномерно темперированном строе. Частота \(f_n\) ноты на \(n\) полутонов выше эталонной \(f_0\) вычисляется по формуле:

\[ f_n = f_0 \cdot 2^{n/12} \]

Отсюда число полутонов между двумя частотами: \(n = 12 \cdot \log_2 (f_2 / f_1)\).

Экономика и финансы

В экономике двоичный логарифм может применяться для моделирования процессов с удвоением (например, время удвоения капитала при сложном проценте). Если вклад растёт с годовой ставкой \(r\), то время удвоения \(T\) в годах приближённо равно \(\frac{\log_2 2}{\log_2 (1+r)} \approx \frac{0.693}{r}\) (правило 70), но точное выражение использует натуральный логарифм.

Другие области

• Фотография: Значения диафрагмы (f-числа) и выдержки часто изменяются в два раза, что соответствует изменению экспозиции на 1 ступень. Двоичный логарифм используется для расчёта экспозиционного числа (EV).
• Биология: Модели роста популяций, где численность удваивается за определённые промежутки времени (например, бактерии в идеальной среде).
• Физика: Закон Фехнера в психофизике утверждает, что ощущение пропорционально логарифму интенсивности стимула; в некоторых контекстах используется двоичный логарифм.

Вычисление

Двоичный логарифм может быть вычислен с помощью различных методов:

• Аналитически: Для чисел, являющихся целыми степенями двойки, значение логарифма — целое число (например, \(\log_2 32 = 5\)).
• Через натуральный логарифм: \(\log_2 x = \frac{\ln x}{\ln 2}\).
• Через десятичный логарифм: \(\log_2 x = \frac{\lg x}{\lg 2}\).
• Алгоритмически: В программировании часто используется итеративный метод деления числа на 2 до получения 1 (для целых чисел) или разложение в ряд Тейлора (для вещественных). В процессорах x86 есть инструкция FYL2X для вычисления логарифма по любому основанию.
• Таблицы: До появления электронных вычислителей использовались таблицы двоичных логарифмов.

Таблица значений

Ниже приведены значения двоичного логарифма для некоторых часто встречающихся чисел:

Связь с другими логарифмами

Двоичный логарифм связан с натуральным логарифмом (по основанию \(e\)) и десятичным логарифмом (по основанию 10) через константы:

• \(\log_2 e \approx 1.442695\)
• \(\log_2 10 \approx 3.321928\)
• \(\ln 2 \approx 0.693147\)
• \(\lg 2 \approx 0.301030\)

Источники

1. Клод Шеннон. «Математическая теория связи» (1948).
2. Ральф Хартли. «Передача информации» (1928).
3. ISO 80000-2:2019 «Величины и единицы. Часть 2: Математика».
4. Дональд Кнут. «Искусство программирования», том 1: Основные алгоритмы.
5. И. Н. Бронштейн, К. А. Семендяев. «Справочник по математике для инженеров и учащихся втузов».