Введение

Экспонента степени двойки

В математике двоичный логарифм – это показатель степени, в которую необходимо возвести число 2, чтобы получить значение n. То есть, для любого действительного числа x,

Например, двоичный логарифм 1 равен 0, двоичный логарифм 2 равен 1, двоичный логарифм 4 равен 2, а двоичный логарифм 32 равен 5. Двоичный логарифм – это логарифм по основанию 2 и является обратной функцией к функции возведения в степень двойки. Помимо обозначения log2, альтернативным обозначением двоичного логарифма является lb (предпочтительное обозначение в стандартах ISO 3111 и ISO 80000-2). Исторически, первое применение двоичных логарифмов было в теории музыки Леонардом Эйлером: двоичный логарифм частотного отношения двух музыкальных тонов определяет количество октав, на которое эти тоны различаются. Двоичные логарифмы можно использовать для вычисления длины представления числа в двоичной системе счисления или количества битов, необходимых для кодирования сообщения в теории информации. В информатике они используются для определения количества шагов, необходимых для бинарного поиска и связанных с ним алгоритмов. Другие области, в которых двоичный логарифм часто применяется, включают комбинаторику, биоинформатику, разработку спортивных турниров и фотографию. Двоичные логарифмы включены в стандартные математические функции языка C и другие математические программные пакеты.

История

Степени двойки известны с древности; например, они встречаются в «Началах» Евклида, предложения IX.32 (о разложении степеней двойки на множители) и IX.36 (половина теоремы Евклида — Эйлера, о структуре чётных совершенных чисел). Двоичный логарифм степени двойки — это просто её позиция в упорядоченной последовательности степеней двойки. На этом основании Майклу Стифелю приписывают публикацию первой известной таблицы двоичных логарифмов в 1544 году. Его книга «Arithmetica Integra» содержит несколько таблиц, показывающих целые числа и соответствующие им степени двойки. Перестановка строк в этих таблицах позволяет интерпретировать их как таблицы двоичных логарифмов. Ранее Стифеля, джайнский математик Вирасена VIII века считается автором идеи, предшествовавшей двоичному логарифму. Концепция ардхачеды Вирасены определяется как число раз, которое данное число можно разделить на два без остатка. Это определение порождает функцию, совпадающую с двоичным логарифмом для степеней двойки, но отличающуюся для других целых чисел, дающую 2-адичный порядок, а не логарифм. Современная форма двоичного логарифма, применимого к любому числу (а не только к степеням двойки), была явно рассмотрена Леонардом Эйлером в 1739 году. Эйлер установил применение двоичных логарифмов к теории музыки задолго до того, как стало известно об их применении в теории информации и информатике. В рамках своей работы в этой области Эйлер опубликовал таблицу двоичных логарифмов целых чисел от 1 до 8 с точностью до семи десятичных знаков.

Обозначение

В математике двоичный логарифм числа n часто записывается как . Однако, для этой функции использовалось или предлагалось несколько других обозначений, особенно в прикладных областях. Некоторые авторы записывают двоичный логарифм как lg n, обозначение, указанное в Чикагском руководстве по стилю. Дональд Кнут связывает это обозначение с предложением Эдварда Рейнгольда, но его использование как в теории информации, так и в информатике восходит к периоду до начала деятельности Рейнгольда. Двоичный логарифм также записывается как log n с предварительным указанием, что основанием логарифма по умолчанию является 2. Другое обозначение, часто используемое для той же функции (особенно в немецкой научной литературе), — ld n, от латинского logarithmus dualis.

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

Количество цифр (бит) в двоичном представлении положительного целого числа n равно целочисленной части , то есть.

Биоинформатика

В биоинформатике микромассивы используются для измерения степени экспрессии различных генов в образце биологического материала. Различные уровни экспрессии гена часто сравниваются с помощью двоичного логарифма отношения уровней экспрессии: логарифмическое отношение двух уровней экспрессии определяется как двоичный логарифм отношения этих двух уровней. Двоичные логарифмы обеспечивают удобное сравнение уровней экспрессии: удвоенный уровень экспрессии можно описать логарифмическим отношением 1, уровень экспрессии, уменьшенный вдвое, можно описать логарифмическим отношением −1, а неизменный уровень экспрессии – логарифмическим отношением 0, например. Данные, полученные таким образом, часто визуализируются в виде диаграммы рассеяния, в которой одна или обе оси координат представляют собой двоичные логарифмы отношений интенсивностей, или в визуализациях, таких как MA-диаграмма и RA-диаграмма, которые поворачивают и масштабируют эти диаграммы рассеяния логарифмических отношений.

Теория музыки

В теории музыки интервал или воспринимаемая разница между двумя тонами определяется отношением их частот. Интервалы, основанные на отношениях рациональных чисел с небольшими числителями и знаменателями, воспринимаются как особенно благозвучные. Самый простой и важный из этих интервалов – октава, отношение частот которой равно 2:1. Количество октав, на которое различаются два тона, равно двоичному логарифму их отношения частот. Для изучения систем строя и других аспектов теории музыки, требующих более тонких различий между тонами, полезно иметь меру размера интервала, которая меньше октавы и является аддитивной (как логарифмы), а не мультипликативной (как отношения частот). То есть, если тоны x, y и z образуют восходящую последовательность, то мера интервала от x до y плюс мера интервала от y до z должны равняться мере интервала от x до z. Такую меру предоставляет цент, который делит октаву на 1200 равных интервалов (12 полутонов по 100 центов каждый). Математически, для тонов с частотами f1 и f2, количество центов в интервале от f1 до f2 равно…

Расписание спортивных соревнований

В соревновательных играх и спортивных состязаниях, в которых в каждой игре или матче участвуют два игрока или команды, бинарный логарифм указывает количество раундов, необходимых в турнире на выбывание для определения победителя. Например, турнир из 4 игроков требует раундов для определения победителя, турнир из 32 команд требует раундов и так далее. В этом случае, для n игроков/команд, где n не является степенью двойки, число раундов округляется в большую сторону, поскольку необходимо, чтобы хотя бы в одном раунде не все оставшиеся участники играли. Например, log₂6 приблизительно равен 2.585, что округляется до 3, указывая на то, что турнир из 6 команд требует 3 раунда (либо две команды пропускают первый раунд, либо одна команда пропускает второй раунд). То же количество раундов также необходимо для определения явного победителя в турнире по швейцарской системе.

Фотография

В фотографии значения экспозиции измеряются в бинарном логарифме количества света, достигающего пленки или сенсора, в соответствии с законом Вебера — Фехнера, описывающим логарифмическую реакцию человеческой зрительной системы на свет. Один стоп экспозиции — это одна единица в логарифмической шкале с основанием 2. Более точно, значение экспозиции фотографии определяется как

где N — число f, измеряющее диафрагму объектива во время экспозиции, а t — количество секунд экспозиции. Бинарные логарифмы (выраженные в стопах) также используются в денситометрии для выражения динамического диапазона светочувствительных материалов или цифровых сенсоров.

Закругление целых чисел

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

Определение можно расширить, определив "Расширенный" следующим образом. Эта функция связана с количеством ведущих нулей в 32-битном беззнаковом двоичном представлении числа x, обозначаемым nlz(x). В некоторых версиях программной библиотеки libc также вычисляется бинарный логарифм (округленный до целого числа и увеличенный на единицу).

Итеративная приближенность

Для общего положительного действительного числа двоичный логарифм можно вычислить в два этапа. Сначала вычисляется целая часть (называемая характеристикой логарифма). Это сводит задачу к вычислению логарифма аргумента, находящегося в ограниченном диапазоне, интервале [1, 2), что упрощает второй этап – вычисление дробной части (мантиссы логарифма). Для любого x > 0 существует единственное целое число n, такое что 2^n ≤ x < 2^(n+1), или, эквивалентно, 1 ≤ 2^(-n)x < 2. Тогда целая часть логарифма равна n, а дробная часть равна log2(2^(-n)x). Для целых чисел она может быть определена с помощью операции подсчёта ведущих нулей. Дробную часть результата можно вычислить итеративно, используя только элементарные операции умножения и деления. В вычислительных средах, поддерживающих комплексные числа и неявное преобразование типов, таких как MATLAB, аргументом функции log2 может быть отрицательное число, в результате чего возвращается комплексное число.