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

График log ₂   x как функции положительного действительного числа x

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

$x=\log _{2}n\quad \Longleftrightarrow \quad 2^{x}=n.$

Например, двоичный логарифм числа 1 равен 0 , двоичный логарифм числа 2 равен 1 , двоичный логарифм числа 4 равен 2 , а двоичный логарифм числа 32 равен 5 .

Двоичный логарифм представляет собой логарифм по основанию 2 и является обратной функцией степени двойки . Помимо log ₂ , альтернативным обозначением двоичного логарифма является lb (обозначение, предпочтительное в ISO 31-11 и ISO 80000-2 ).

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

Двоичные логарифмы включены в стандартные математические функции C и другие пакеты математического программного обеспечения.

История

Основная статья: История логарифмов

Леонард Эйлер был первым, кто применил двоичные логарифмы в теории музыки в 1739 году.

Силы двойки известны с древности; например, они появляются в Евклида «Элементах» , «Реквизит». IX.32 (о факторизации степеней двойки) и IX.36 (половина теоремы Евклида–Эйлера , о строении четных совершенных чисел ). А двоичный логарифм степени двойки — это всего лишь его позиция в упорядоченной последовательности степеней двойки. На этом основании Майклу Стифелу приписывают публикацию первой известной таблицы двоичных логарифмов в 1544 году. Его книга «Арифметика Интегра» содержит несколько таблиц, в которых показаны целые числа с соответствующими степенями двойки. Перестановка строк этих таблиц позволяет интерпретировать их как таблицы двоичных логарифмов.

, живший раньше Стифеля джайнский математик VIII века Вирасена Предшественником двоичного логарифма считается Вирасены . Концепция ардхачеды определяется как количество раз, которое заданное число можно разделить на два без остатка. Это определение приводит к функции, совпадающей с двоичным логарифмом по степеням двойки: но для других целых чисел все по-другому: они дают 2-адический порядок, а не логарифм.

Современная форма двоичного логарифма, применимая к любому числу (а не только к степеням двойки), была подробно рассмотрена Леонардом Эйлером в 1739 году. Эйлер установил применение двоичных логарифмов в теории музыки задолго до того, как их приложения в теории информации и информатике стали известны. известен. В рамках своей работы в этой области Эйлер опубликовал таблицу двоичных логарифмов целых чисел от 1 до 8 с точностью до семи десятичных знаков.

Определение и свойства

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

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

$\log _{2}xy=\log _{2}x+\log _{2}y$

$\log _{2}{\frac {x}{y}}=\log _{2}x-\log _{2}y$

$\log _{2}x^{y}=y\log _{2}x.$

Подробнее см. в списке логарифмических тождеств .

Обозначения

В математике двоичный логарифм числа n часто записывается как log ₂   n . Однако для этой функции использовались или предлагались несколько других обозначений, особенно в прикладных областях.

Некоторые авторы записывают двоичный логарифм как lg n , обозначения, перечисленные в Чикагском руководстве по стилю . Дональд Кнут приписывает это обозначение предложению Эдварда Рейнгольда . но его использование как в теории информации, так и в информатике началось еще до того, как Рейнгольд стал активным. Двоичный логарифм также записывается как log n с предварительным утверждением, что основанием по умолчанию для логарифма является 2 . Другое обозначение, которое часто используется для той же функции (особенно в немецкой научной литературе), — ld n , от латинского logarithmus Dualis или логарифм диадис . Стандарты DIN 1302 , ISO 31-11 и ISO 80000-2 рекомендуют еще одно обозначение, lb n . Согласно этим стандартам, lg n не следует использовать для двоичного логарифма, поскольку вместо этого он зарезервирован для десятичного логарифма log ₁₀ n .

Приложения

См. Также: Удвоение времени

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

Количество цифр ( битов ) в двоичном представлении натурального числа n является целой частью 1 + log ₂   n , т.е.

$\lfloor \log _{2}n\rfloor +1.$

В теории информации определение количества собственной информации и информационной энтропии часто выражается с помощью двоичного логарифма, что соответствует определению бита как фундаментальной единицы информации . С помощью этих единиц теорема Шеннона-Хартли выражает информационную емкость канала как двоичный логарифм его отношения сигнал/шум плюс единица. Однако натуральный логарифм и nat также используются в альтернативных обозначениях этих определений.

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

для 16 игроков на выбывание Турнирная сетка со структурой полного бинарного дерева . Высота дерева (количество туров турнира) представляет собой двоичный логарифм количества игроков, округленный до целого числа.

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

• Каждое двоичное дерево с n листьями имеет высоту не менее log ₂   n , при этом равенство достигается, когда n является степенью двойки и дерево является полным двоичным деревом . Соответственно, число Стралера речной системы с n притоками не превышает log ₂   n + 1 .
• Каждое семейство множеств, состоящее из n различных наборов, имеет в своем объединении не менее log ₂   n элементов, причём равенство, если семейство является степенным множеством .
• Каждый частичный куб с n вершинами имеет изометрическую размерность не менее log ₂   n и не более 1/2 с равенством , n n log ₂   ребер , если частичный куб является графом гиперкуба .
• Согласно теореме Рэмси , каждый n -вершинный неориентированный граф имеет либо клику , либо независимое множество логарифмического размера по n . Точный размер, который может быть гарантирован, неизвестен, но лучшие известные границы его размера включают двоичные логарифмы. В частности, все графы имеют клику или независимое множество размером не менее 1/2 почти все графы не имеют и log ₂   n (1 − o (1)) клики или независимого множества размером больше 2 log ₂   n (1 + o (1)) .
• На основе математического анализа модели случайных тасовок Гилберта-Шеннона-Ридса можно показать, что количество раз, которое нужно перетасовать n -карточную колоду карт, используя перетасовку , чтобы получить распределение по перестановкам, близкое к равномерно случайный, приблизительно 3/2 ​ ​ журнал ₂   н . Этот расчет лежит в основе рекомендации о том, что колоду из 52 карт следует тасовать семь раз.

Вычислительная сложность

Бинарный поиск в отсортированном массиве - алгоритм, временная сложность которого включает двоичные логарифмы.

Двоичный логарифм также часто появляется при анализе алгоритмов . не только из-за частого использования арифметики двоичных чисел в алгоритмах, но и потому, что двоичные логарифмы встречаются при анализе алгоритмов, основанных на двустороннем ветвлении. Если задача изначально имеет n вариантов решения, и каждая итерация алгоритма уменьшает количество вариантов в два раза, то количество итераций, необходимых для выбора одного варианта, снова является неотъемлемой частью log ₂   n . Эта идея используется при анализе нескольких алгоритмов и структур данных . Например, при двоичном поиске размер решаемой задачи уменьшается вдвое с каждой итерацией, и поэтому требуется примерно log ₂   n для получения решения задачи размера n итераций . Аналогично, идеально сбалансированное двоичное дерево поиска, содержащее n элементов, имеет высоту log ₂ ( n + 1) − 1 .

Время работы алгоритма обычно выражается в виде большой буквы O , которая используется для упрощения выражений за счет исключения их постоянных множителей и членов младшего порядка. Поскольку логарифмы в разных системах счисления отличаются друг от друга только постоянным коэффициентом, можно также сказать, что алгоритмы, работающие за время O (log ₂   n ) , работают, скажем, за время O (log ₁₃ n ) . Поэтому основание логарифма в таких выражениях, как O (log n ) или O ( n log n ), не имеет значения и может быть опущено. Однако для логарифмов, которые появляются в показателе степени ограниченного времени, основание логарифма нельзя опускать. Например, О (2 ^{войти ₂   н} ) не то же самое, что O (2 ^{н в} ), потому что первое равно O ( n ) , а второе — O ( n ^0.6931... ) .

Алгоритмы со временем работы O ( n log n ) иногда называют линеарифмическими . Некоторые примеры алгоритмов со временем работы O (log n ) или O ( n log n ) :

• Быстрая сортировка по среднему времени и другие сортировки сравнением алгоритмы
• Поиск в сбалансированных двоичных деревьях поиска
• Возведение в степень возведением в степень
• Самая длинная возрастающая подпоследовательность

Двоичные логарифмы также встречаются в показателях временных границ для некоторых алгоритмов «разделяй и властвуй» , таких как алгоритм Карацубы для умножения n -битных чисел за время O ( n ^{журнал ₂ 3} ) , и алгоритм Штрассена для умножения матриц размера n × n за время На ​ ​ ^{журнал ₂ 7} ) . Появление двоичных логарифмов в этом времени выполнения можно объяснить, обратившись к основной теореме для повторений по принципу «разделяй и властвуй» .

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

Микрочип . примерно на 8700 генов Скорости экспрессии этих генов сравниваются с использованием двоичных логарифмов.

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

Точки данных, полученные таким способом, часто визуализируются в виде диаграммы рассеяния , в которой одна или обе оси координат представляют собой двоичные логарифмы отношений интенсивностей, или в таких визуализациях, как график MA и график RA , которые вращают и масштабируют эти диаграммы рассеяния логарифмических отношений.

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

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

Для изучения систем настройки и других аспектов теории музыки, которые требуют более тонких различий между тонами, полезно иметь меру размера интервала, которая меньше октавы и является аддитивной (как логарифмы), а не мультипликативной (как частота). соотношения есть). То есть, если тона x , y и z образуют восходящую последовательность тонов, то размер интервала от x до y плюс размер интервала от y до z должен равняться размеру интервала от x до z . Такую меру дает цент , делящий октаву на 1200 равных интервалов ( 12 полутонов по 100 центов каждый). Математически для данных тонов с частотами f ₁ и f ₂ количество центов в интервале от f ₁ до f ₂ равно

$\left|1200\log _{2}{\frac {f_{1}}{f_{2}}}\right|.$

Миллиоктава определяется таким же образом , но с множителем 1000 вместо 1200 .

Расписание занятий спортом

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

Фотография

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

$\log _{2}{\frac {N^{2}}{t}}$

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

Двоичные логарифмы (выраженные как стопы) также используются в денситометрии для выражения динамического диапазона светочувствительных материалов или цифровых датчиков.

Расчет

НР-35 Научный калькулятор (1972 г.). Клавиши log и ln находятся в верхнем ряду; нет ключа журнала ₂ .

Конвертация из других баз

Простой способ вычислить log ₂   n на калькуляторах , которые не имеют функции log _2, — это использовать функции натурального логарифма ( ln ) или десятичного логарифма ( log или log ₁₀ ), которые имеются в большинстве научных калькуляторов . Чтобы изменить основание логарифма с е или 10 на 2, можно использовать формулы :

$\log _{2}n={\frac {\ln n}{\ln 2}}={\frac {\log _{10}n}{\log _{10}2}},$

или приблизительно

$\log _{2}n\approx 1.442695\ln n\approx 3.321928\log _{10}n.$

Целочисленное округление

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

$\lfloor \log _{2}(n)\rfloor =\lceil \log _{2}(n+1)\rceil -1,{\text{ if }}n\geq 1.$

Определение можно расширить, определив $\lfloor \log _{2}(0)\rfloor =-1$. Расширенная таким образом, эта функция связана с количеством ведущих нулей 32-битного беззнакового двоичного представления x , nlz( x ) .

$\lfloor \log _{2}(n)\rfloor =31-\operatorname {nlz} (n).$

Целочисленный двоичный логарифм можно интерпретировать как отсчитываемый от нуля индекс старшего 1 бита во входных данных. В этом смысле это дополнение к операции поиска первого набора , которая находит индекс младшего 1 бита. Многие аппаратные платформы включают поддержку поиска количества ведущих нулей или эквивалентных операций, которые можно использовать для быстрого нахождения двоичного логарифма. fls и flsl функции в ядре Linux а в некоторых версиях библиотеки программного обеспечения libc также вычисляется двоичный логарифм (округленный до целого числа плюс один).

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

Для общего положительного действительного числа двоичный логарифм может быть вычислен в двух частях. Сначала вычисляется целая часть , $\lfloor \log _{2}x\rfloor$(называемая характеристикой логарифма). Это сводит проблему к той, где аргумент логарифма находится в ограниченном диапазоне, интервале [1, 2) , упрощая второй шаг вычисления дробной части (мантиссы логарифма). Для любого x > 0 существует единственное целое число n такое, что 2 ^н ≤ х < 2 ^{п +1} или, что то же самое, 1 ≤ 2 ^{− п} х < 2 . Теперь целая часть логарифма равна просто n , а дробная часть — log ₂ (2 ^{− п} Икс ) . Другими словами:

$\log _{2}x=n+\log _{2}y\quad {\text{where }}y=2^{-n}x{\text{ and }}y\in [1,2)$

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

Дробная часть результата равна log ₂   y и может быть вычислена итеративно, используя только элементарное умножение и деление. Алгоритм вычисления дробной части можно описать в псевдокоде следующим образом:

1. Начните с действительного числа y в полуоткрытом интервале [1, 2) . Если y = 1 , то алгоритм завершен, и дробная часть равна нулю.
2. квадрат В противном случае возводите y в несколько раз, пока результат z не окажется в интервале [2, 4) . Пусть m — необходимое количество квадратов. То есть z = y ^{2 м} где m выбрано так, что z находится в [2, 4) .
3. Логарифмируем обе части и занимаемся алгеброй:
   $${\begin{aligned}\log _{2}z&=2^{m}\log _{2}y\\\log _{2}y&={\frac {\log _{2}z}{2^{m}}}\\&={\frac {1+\log _{2}(z/2)}{2^{m}}}\\&=2^{-m}+2^{-m}\log _{2}(z/2).\end{aligned}}$$
4. Еще раз z /2 — действительное число из интервала [1, 2) . Вернитесь к шагу 1 и вычислите двоичный логарифм z /2, используя тот же метод.

Результат этого выражается следующими рекурсивными формулами, в которых $m_{i}$ — количество возведений в квадрат, необходимое на i -й итерации алгоритма:

$${\begin{aligned}\log _{2}x&=n+2^{-m_{1}}\left(1+2^{-m_{2}}\left(1+2^{-m_{3}}\left(1+\cdots \right)\right)\right)\\&=n+2^{-m_{1}}+2^{-m_{1}-m_{2}}+2^{-m_{1}-m_{2}-m_{3}}+\cdots \end{aligned}}$$

В частном случае, когда дробная часть на шаге 1 оказывается равной нулю, это конечная последовательность, заканчивающаяся в некоторой точке. В противном случае это бесконечный ряд по , сходящийся критерию отношения , поскольку каждый член строго меньше предыдущего (поскольку каждое m _i > 0 ). Для практического использования этот бесконечный ряд необходимо усечь, чтобы получить приблизительный результат. Если ряд усекается после i -го члена, то ошибка результата меньше 2 ^{-( м ₁ + м ₂ + ⋯ + м _я )} .

Поддержка библиотеки программного обеспечения

The log2Функция включена в стандартные математические функции C. Версия этой функции по умолчанию принимает аргументы двойной точности, но ее варианты позволяют аргументу иметь одинарную точность или быть длинным двойным . В вычислительных средах, поддерживающих комплексные числа и неявное преобразование типов, таких как MATLAB, аргумент log2 функция может быть отрицательным числом , возвращающим комплексное число.

Внешние ссылки

• Вайсштейн, Эрик В. , «Двоичный логарифм» , MathWorld
• Андерсон, Шон Эрон (12 декабря 2003 г.), «Найдите логарифмическую базу 2 N-битного целого числа за операции O(lg(N))» , Bit Twiddling Hacks , Стэнфордский университет , получено 25 ноября 2015 г.
• Фейнман и машина соединений