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

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

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

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

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

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

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

История

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

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

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

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

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

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

\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 2 n$ . ^[10] Однако для этой функции использовались или предлагались несколько других обозначений, особенно в прикладных областях.

Некоторые авторы записывают двоичный логарифм как $lg n$ , ^[11]^[12] обозначения, перечисленные в Чикагском руководстве по стилю . ^[13] Дональд Кнут приписывает это обозначение предложению Эдварда Рейнгольда . ^[14] но его использование как в теории информации, так и в информатике началось еще до того, как Рейнгольд стал активным. ^[15]^[16] Двоичный логарифм также записывается как $log n$ с предварительным утверждением, что основанием по умолчанию для логарифма является $2$ . ^[17]^[18]^[19] Другое обозначение, которое часто используется для той же функции (особенно в немецкой научной литературе), — $ld n$ , ^[20]^[21]^[22] от латинского logarithmus Dualis ^[20] или логарифм диадис . ^[20] Стандарты DIN 1302 [ de ] , ISO 31-11 и ISO 80000-2 рекомендуют еще одно обозначение, $lb n$ . Согласно этим стандартам, $lg n$ не следует использовать для двоичного логарифма, поскольку вместо этого он зарезервирован для десятичного логарифма $log 10 n$ . ^[23]^[24]^[25]

Приложения

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

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

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

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

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

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

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

Каждое двоичное дерево с $n$ листьями имеет высоту не менее $log 2 n$ , при этом равенство достигается, когда $n$ является степенью двойки и дерево является полным двоичным деревом . ^[28] Соответственно, число Стралера речной системы с $n$ притоками не превышает $log 2 n + 1$ . ^[29]
Каждое семейство множеств, состоящее из $n$ различных наборов, имеет в своем объединении не менее $log 2 n$ элементов, причём равенство, если семейство является степенным множеством . ^[30]
Каждый частичный куб с $n$ вершинами имеет изометрическую размерность не менее $log 2 n$ и не более $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ 1/2 равенством , 2 ⁠ n log ребер, с n$ если частичный куб является графом гиперкуба . ^[31]
Согласно теореме Рэмси , каждый $n$ -вершинный неориентированный граф имеет либо клику , либо независимое множество логарифмического размера по $n$ . Точный размер, который может быть гарантирован, неизвестен, но лучшие известные границы его размера включают двоичные логарифмы. В частности, все графы имеют клику или независимое множество размером не менее $⁠ 1/2 o 2 ⁠ log 2 n (1 - o (1))$ и почти все графы не имеют клики или независимого множества размером больше $log 2 n (1 + (1))$ . ^[32]
На основе математического анализа модели случайных тасовок Гилберта-Шеннона-Ридса можно показать, что количество раз, которое нужно перетасовать $n$ -карточную колоду карт, используя перетасовку , чтобы получить распределение по перестановкам, близкое к равномерно случайный, приблизительно $⁠ 3 / 2 ⁠ журнал 2 п$ . Этот расчет лежит в основе рекомендации о том, что колоду из 52 карт следует тасовать семь раз. ^[33]

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

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

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

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

Быстрая сортировка по среднему времени и другие сортировки сравнением алгоритмы ^[38]
Поиск в сбалансированных двоичных деревьях поиска ^[39]
Возведение в степень возведением в степень ^[40]
Самая длинная возрастающая подпоследовательность ^[41]

Двоичные логарифмы также встречаются в показателях временных границ для некоторых алгоритмов «разделяй и властвуй» , таких как алгоритм Карацубы для умножения $n$ -битных чисел за время $O (n войти 23)$ , ^[42]и алгоритм Штрассена для умножения $матриц размера n \times n$ за время $На журнал 27)$ . ^[43] Появление двоичных логарифмов в этом времени выполнения можно объяснить, обратившись к основной теореме для повторений по принципу «разделяй и властвуй» .

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

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

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

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

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

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

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

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

Спортивное расписание

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

Фотография

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

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

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

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

Расчет

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

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

\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.

^[54]

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

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

^[54]

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

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

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

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

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

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

Начните с действительного числа $y$ в полуоткрытом интервале $[1, 2)$ . Если $y = 1$ , то алгоритм завершен, и дробная часть равна нулю.
В противном случае возводите $y$ в квадрат несколько раз, пока результат $z$ не окажется в интервале $[2, 4)$ . Пусть $m$ — необходимое количество квадратов. То есть $z = y 2 м$ где $m$ выбрано так, что $z$ находится в $[2, 4)$ .
Логарифмируем обе части и занимаемся алгеброй: ${\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}}$
Еще раз $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 -(м 1 + м 2 + \dots + м я)$ . ^[56]

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

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

Ссылки

^ Гроза, Вивиан Шоу; Шелли, Сюзанна М. (1972), Предисчисление математики , Нью-Йорк: Холт, Райнхарт и Уинстон, стр. 182, ISBN 978-0-03-077670-0 .
^ Стифель, Майкл (1544 г.), Arithmetica integra (на латыни), стр. 31 . Копия той же таблицы с еще двумя записями приведена на стр. 237, а еще одна копия, расширенная до отрицательных степеней, появляется на стр. 249б.
^ Джозеф, Г.Г. (2011), Герб павлина: неевропейские корни математики (3-е изд.), Princeton University Press, стр. 352 .
^ См., например, Шпарлинский, Игорь (2013), Криптографические приложения аналитической теории чисел: нижние границы сложности и псевдослучайность , Прогресс в области информатики и прикладной логики, том. 22, Биркхойзер, с. 35, ISBN 978-3-0348-8037-4 .
^ Эйлер, Леонгард (1739), «Глава VII. В различные промежутки времени поступившие обращения», Испытание новой теории музыки, четко излагающей некоторые принципы гармонии (на латыни), Санкт-Петербургская Академия, стр. 102–112 .
^ Тегг, Томас (1829), «Двоичные логарифмы», Лондонская энциклопедия; или «Универсальный словарь науки, искусства, литературы и практической механики: включающий популярный взгляд на современное состояние знаний», том 4 , стр. 142–143 .
^ Батчелет, Э. (2012), Введение в математику для ученых-биологов , Springer, стр. 128, ISBN 978-3-642-96080-2 .
^ Например, Microsoft Excel предоставляет IMLOG2 функция для комплексных двоичных логарифмов: см. Бург, Дэвид М. (2006), Excel Scientific and Engineering Cookbook , O'Reilly Media, стр. 232, ISBN 978-0-596-55317-3 .
^ Колман, Бернард; Шапиро, Арнольд (1982), «11.4 Свойства логарифмов», Алгебра для студентов колледжей , Academic Press, стр. 334–335, ISBN 978-1-4832-7121-7 .
^ Например, это обозначение, используемое в Энциклопедии математики и Принстонском справочнике по математике .
^ Перейти обратно: ^а ^б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990], Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill, стр. 34, 53–54, ISBN 0-262-03293-7
^ Перейти обратно: ^а ^б Седжвик, Роберт ; Уэйн, Кевин Дэниэл (2011), Алгоритмы , Addison-Wesley Professional, стр. 185, ISBN 978-0-321-57351-3 .
^ Чикагское руководство по стилю (25-е изд.), University of Chicago Press, 2003, стр. 530 .
^ Перейти обратно: ^а ^б Кнут, Дональд Э. (1997), Фундаментальные алгоритмы , Искусство компьютерного программирования , том. 1 (3-е изд.), Addison-Wesley Professional, ISBN 978-0-321-63574-7 , с. 11 . Такое же обозначение было во втором издании той же книги 1973 года (стр. 23), но без упоминания Рейнгольда.
^ Тручко, Эрнесто (1956), «Заметки об информативности графиков», Bull. Математика. Биофиз. , 18 (2): 129–135, doi : 10.1007/BF02477836 , MR 0077919 .
^ Митчелл, Джон Н. (1962), «Компьютерное умножение и деление с использованием двоичных логарифмов», IRE Transactions on Electronic Computers , EC-11 (4): 512–517, doi : 10.1109/TEC.1962.5219391 .
^ Фиш, Жорж; Эбютерн, Жерар (2013), Математика для инженеров , John Wiley & Sons, стр. 152, ISBN 978-1-118-62333-6 , В дальнейшем, если не указано иное, обозначение $log x$ всегда означает логарифм по основанию $2$ от $x$ .
^ Обложка, Томас М .; Томас, Джой А. (2012), Элементы теории информации (2-е изд.), John Wiley & Sons , стр. 33, ISBN 978-1-118-58577-1 , Если не указано иное, мы будем приводить все логарифмы к основанию $2$ .
^ Перейти обратно: ^а ^б Гудрич, Майкл Т .; Тамассиа, Роберто (2002), Разработка алгоритмов: основы, анализ и примеры из Интернета , John Wiley & Sons, стр. 23. Одним из интересных и иногда даже удивительных аспектов анализа структур данных и алгоритмов является повсеместное присутствие логарифмов... По традиции в компьютерной литературе мы опускаем запись основания $b$ логарифма при $b = 2.$ .
^ Перейти обратно: ^а ^б ^с Тафель, Ханс Йорг (1971), обработку информации ( Введение в цифровую на немецком языке), Мюнхен: Carl Hanser Verlag , стр. 20–21, ISBN 3-446-10569-7
^ Титце, Ульрих; Шенк, Кристоф (1999), Semiconductor Circuit Technology (на немецком языке) (1-е исправленное переиздание, 11-е изд.), Springer Verlag , стр. 1370 , ISBN 3-540-64192-0
^ Бауэр, Фридрих Л. (2009), Истоки и основы вычислений: в сотрудничестве с Музейным форумом Хайнца Никсдорфа , Springer Science & Business Media , стр. 54, ISBN 978-3-642-02991-2 .
^ DIN 1302 см. ( Энциклопедия Брокгауза в двадцати томах на немецком языке), том. 11, Висбаден: Ф.А. Брокгауз, 1970, с. 554, ISBN 978-3-7653-0000-4 .
^ Для ISO 31-11 см. Томпсон, Эмблер; Тейлор, Барри М. (март 2008 г.), Руководство по использованию международной системы единиц (СИ) — Специальная публикация NIST 811, издание 2008 г. — Второе издание (PDF) , NIST , стр. 33 .
^ Для ISO 80000-2 см. «Количества и единицы измерения – Часть 2: Математические знаки и символы, используемые в естественных науках и технологиях» (PDF) , Международный стандарт ISO 80000-2 (1-е изд.), 1 декабря 2009 г., Раздел 12, Показательные и логарифмические функции , с. 18 .
^ Ван дер Люббе, Ян Калифорния (1997), Теория информации , Издательство Кембриджского университета, стр. 3, ISBN 978-0-521-46760-5 .
^ Стюарт, Ян (2015), Укрощение бесконечности , Quercus, стр. 120, ISBN 9781623654733 В высшей математике и естественных науках единственным важным логарифмом является натуральный логарифм .
^ Лейсс, Эрнст Л. (2006), Помощник программиста по анализу алгоритмов , CRC Press, стр. 28, ISBN 978-1-4200-1170-8 .
^ Деврой, Л. ; Крушевски, П. (1996), «О числе Хортона-Стралера для случайных попыток» , RAIRO Informatique Théorique et Applications , 30 (5): 443–456, doi : 10.1051/ita/1996300504431 , MR 1435732 .
^ Эквивалентно, семья с $k$ различными элементами имеет не более $2 к$ различные наборы с равенством, если это набор мощности.
^ Эппштейн, Дэвид (2005), «Размерность решетки графа», Европейский журнал комбинаторики , 26 (5): 585–592, arXiv : cs.DS/0402028 , doi : 10.1016/j.ejc.2004.05.001 , МР 2127682 , S2CID 7482443 .
^ Грэм, Рональд Л .; Ротшильд, Брюс Л .; Спенсер, Джоэл Х. (1980), Теория Рэмси , Wiley-Interscience, с. 78 .
^ Байер, Дэйв ; Диаконис, Перси (1992), «Следуя за ласточкиным хвостом к его логову», The Annals of Applied Probability , 2 (2): 294–313, doi : 10.1214/aoap/1177005705 , JSTOR 2959752 , MR 1161056 .
^ Мельхорн, Курт ; Сандерс, Питер (2008), «2.5 Пример – двоичный поиск», Алгоритмы и структуры данных: базовый набор инструментов (PDF) , Springer, стр. 34–36, ISBN 978-3-540-77977-3 .
^ Робертс, Фред ; Тесман, Барри (2009), Прикладная комбинаторика (2-е изд.), CRC Press, стр. 206, ISBN 978-1-4200-9983-6 .
^ Сипсер, Майкл (2012), «Пример 7.4», Введение в теорию вычислений (3-е изд.), Cengage Learning, стр. 277–278, ISBN 9781133187790 .
^ Седжвик и Уэйн (2011) , с. 186 .
^ Кормен и др. (2001) , с. 156; Гудрич и Тамассия (2002) , с. 238.
^ Кормен и др. (2001) , с. 276; Гудрич и Тамассия (2002) , с. 159.
^ Кормен и др. (2001) , с. 879–880; Гудрич и Тамассия (2002) , с. 464.
^ Эдмондс, Джефф (2008), Как думать об алгоритмах , издательство Кембриджского университета, стр. 302, ISBN 978-1-139-47175-6 .
^ Кормен и др. (2001) , с. 844; Гудрич и Тамассия (2002) , с. 279.
^ Кормен и др. (2001) , раздел 28.2.
^ Костон, Хелен; Квакенбуш, Джон; Бразма, Алвис (2009), Анализ данных экспрессии генов на микрочипах: руководство для начинающих , John Wiley & Sons, стр. 49–50, ISBN 978-1-4443-1156-3 .
^ Эйдхаммер, Ингвар; Барснес, Харальд; Эйде, Гейр Эгиль; Мартенс, Леннарт (2012), Вычислительные и статистические методы количественного определения белка с помощью масс-спектрометрии , John Wiley & Sons, стр. 105, ISBN 978-1-118-49378-6 .
^ Перейти обратно: ^а ^б Кэмпбелл, Мюррей; Грейтед, Клайв (1994), Путеводитель музыканта по акустике , Oxford University Press, стр. 78, ISBN 978-0-19-159167-9 .
^ Рэндел, Дон Майкл , изд. (2003), Гарвардский музыкальный словарь (4-е изд.), The Belknap Press of Harvard University Press, стр. 416, ISBN 978-0-674-01163-2 .
^ Франс, Роберт (2008), Введение в физическое воспитание и спортивную науку , Cengage Learning, стр. 282, ISBN 978-1-4180-5529-5 .
^ Аллен, Элизабет; Триантафиллиду, Софи (2011), Справочник фотографии , Тейлор и Фрэнсис, стр. 228, ISBN 978-0-240-52037-7 .
^ Перейти обратно: ^а ^б Дэвис, Фил (1998), За пределами зональной системы , CRC Press, стр. 17, ISBN 978-1-136-09294-7 .
^ Аллен и Триантафиллиду (2011) , с. 235 .
^ Цверман, Сьюзен; Окунь, Джеффри А. (2012), Справочник Общества визуальных эффектов: Рабочий процесс и методы , CRC Press, стр. 205, ISBN 978-1-136-13614-6 .
^ Бауэр, Крейг П. (2013), Тайная история: история криптологии , CRC Press, стр. 332, ISBN 978-1-4665-6186-1 .
^ Перейти обратно: ^а ^б Уоррен-младший, Генри С. (2002), Hacker's Delight (1-е изд.), Аддисон Уэсли , стр. 215, ISBN 978-0-201-91465-8
^ fls , API ядра Linux, kernel.org , получено 17 октября 2010 г.
^ Перейти обратно: ^а ^б ^с ^д Маджития, JC; Леван, Д. (1973), «Заметки о вычислениях логарифмов по основанию 2», Proceedings of the IEEE , 61 (10): 1519–1520, doi : 10.1109/PROC.1973.9318 .
^ Стивенсон, Ян (2005), «9.6 Функции Fast Power, Log2 и Exp2», Производственный рендеринг: проектирование и реализация , Springer-Verlag, стр. 270–273, ISBN 978-1-84628-085-6 .
^ Уоррен-младший, Генри С. (2013) [2002], «11-4: Целочисленный логарифм» , Hacker's Delight (2-е изд.), Аддисон Уэсли – Pearson Education, Inc. , стр. 291, ISBN 978-0-321-84268-8 , 0-321-84268-5 .
^ «7.12.6.10 Функции log2», спецификация ISO/IEC 9899:1999 (PDF) , стр. 226 .
^ Редферн, Даррен; Кэмпбелл, Колин (1998), Справочник по Matlab® 5 , Springer-Verlag, стр. 141, ISBN 978-1-4612-2170-8 .

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

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

[1] Гроза, Вивиан Шоу; Шелли, Сюзанна М. (1972), Предисчисление математики , Нью-Йорк: Холт, Райнхарт и Уинстон, стр. 182, ISBN 978-0-03-077670-0 .

[2] Стифель, Майкл (1544 г.), Arithmetica integra (на латыни), стр. 31 . Копия той же таблицы с еще двумя записями приведена на стр. 237, а еще одна копия, расширенная до отрицательных степеней, появляется на стр. 249б.

[3] Джозеф, Г.Г. (2011), Герб павлина: неевропейские корни математики (3-е изд.), Princeton University Press, стр. 352 .

[4] См., например, Шпарлинский, Игорь (2013), Криптографические приложения аналитической теории чисел: нижние границы сложности и псевдослучайность , Прогресс в области информатики и прикладной логики, том. 22, Биркхойзер, с. 35, ISBN 978-3-0348-8037-4 .

[5] Эйлер, Леонгард (1739), «Глава VII. В различные промежутки времени поступившие обращения», Испытание новой теории музыки, четко излагающей некоторые принципы гармонии (на латыни), Санкт-Петербургская Академия, стр. 102–112 .

[6] Тегг, Томас (1829), «Двоичные логарифмы», Лондонская энциклопедия; или «Универсальный словарь науки, искусства, литературы и практической механики: включающий популярный взгляд на современное состояние знаний», том 4 , стр. 142–143 .

[7] Батчелет, Э. (2012), Введение в математику для ученых-биологов , Springer, стр. 128, ISBN 978-3-642-96080-2 .

[8] Например, Microsoft Excel предоставляет IMLOG2 функция для комплексных двоичных логарифмов: см. Бург, Дэвид М. (2006), Excel Scientific and Engineering Cookbook , O'Reilly Media, стр. 232, ISBN 978-0-596-55317-3 .

[9] Колман, Бернард; Шапиро, Арнольд (1982), «11.4 Свойства логарифмов», Алгебра для студентов колледжей , Academic Press, стр. 334–335, ISBN 978-1-4832-7121-7 .

[10] Например, это обозначение, используемое в Энциклопедии математики и Принстонском справочнике по математике .

[clrs-11] Перейти обратно: ^а ^б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990], Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill, стр. 34, 53–54, ISBN 0-262-03293-7

[sw11-12] Перейти обратно: ^а ^б Седжвик, Роберт ; Уэйн, Кевин Дэниэл (2011), Алгоритмы , Addison-Wesley Professional, стр. 185, ISBN 978-0-321-57351-3 .

[13] Чикагское руководство по стилю (25-е изд.), University of Chicago Press, 2003, стр. 530 .

[knuth-14] Перейти обратно: ^а ^б Кнут, Дональд Э. (1997), Фундаментальные алгоритмы , Искусство компьютерного программирования , том. 1 (3-е изд.), Addison-Wesley Professional, ISBN 978-0-321-63574-7 , с. 11 . Такое же обозначение было во втором издании той же книги 1973 года (стр. 23), но без упоминания Рейнгольда.

[15] Тручко, Эрнесто (1956), «Заметки об информативности графиков», Bull. Математика. Биофиз. , 18 (2): 129–135, doi : 10.1007/BF02477836 , MR 0077919 .

[16] Митчелл, Джон Н. (1962), «Компьютерное умножение и деление с использованием двоичных логарифмов», IRE Transactions on Electronic Computers , EC-11 (4): 512–517, doi : 10.1109/TEC.1962.5219391 .

[17] Фиш, Жорж; Эбютерн, Жерар (2013), Математика для инженеров , John Wiley & Sons, стр. 152, ISBN 978-1-118-62333-6 , В дальнейшем, если не указано иное, обозначение $log x$ всегда означает логарифм по основанию $2$ от $x$ .

[18] Обложка, Томас М .; Томас, Джой А. (2012), Элементы теории информации (2-е изд.), John Wiley & Sons , стр. 33, ISBN 978-1-118-58577-1 , Если не указано иное, мы будем приводить все логарифмы к основанию $2$ .

[gt02-19] Перейти обратно: ^а ^б Гудрич, Майкл Т .; Тамассиа, Роберто (2002), Разработка алгоритмов: основы, анализ и примеры из Интернета , John Wiley & Sons, стр. 23. Одним из интересных и иногда даже удивительных аспектов анализа структур данных и алгоритмов является повсеместное присутствие логарифмов... По традиции в компьютерной литературе мы опускаем запись основания $b$ логарифма при $b = 2.$ .

[Tafel_1971-20] Перейти обратно: ^а ^б ^с Тафель, Ханс Йорг (1971), обработку информации ( Введение в цифровую на немецком языке), Мюнхен: Carl Hanser Verlag , стр. 20–21, ISBN 3-446-10569-7

[Tietze_Schenk_1999-21] Титце, Ульрих; Шенк, Кристоф (1999), Semiconductor Circuit Technology (на немецком языке) (1-е исправленное переиздание, 11-е изд.), Springer Verlag , стр. 1370 , ISBN 3-540-64192-0

[Bauer_2009-22] Бауэр, Фридрих Л. (2009), Истоки и основы вычислений: в сотрудничестве с Музейным форумом Хайнца Никсдорфа , Springer Science & Business Media , стр. 54, ISBN 978-3-642-02991-2 .

[23] DIN 1302 см. ( Энциклопедия Брокгауза в двадцати томах на немецком языке), том. 11, Висбаден: Ф.А. Брокгауз, 1970, с. 554, ISBN 978-3-7653-0000-4 .

[24] Для ISO 31-11 см. Томпсон, Эмблер; Тейлор, Барри М. (март 2008 г.), Руководство по использованию международной системы единиц (СИ) — Специальная публикация NIST 811, издание 2008 г. — Второе издание (PDF) , NIST , стр. 33 .

[25] Для ISO 80000-2 см. «Количества и единицы измерения – Часть 2: Математические знаки и символы, используемые в естественных науках и технологиях» (PDF) , Международный стандарт ISO 80000-2 (1-е изд.), 1 декабря 2009 г., Раздел 12, Показательные и логарифмические функции , с. 18 .

[26] Ван дер Люббе, Ян Калифорния (1997), Теория информации , Издательство Кембриджского университета, стр. 3, ISBN 978-0-521-46760-5 .

[27] Стюарт, Ян (2015), Укрощение бесконечности , Quercus, стр. 120, ISBN 9781623654733 В высшей математике и естественных науках единственным важным логарифмом является натуральный логарифм .

[28] Лейсс, Эрнст Л. (2006), Помощник программиста по анализу алгоритмов , CRC Press, стр. 28, ISBN 978-1-4200-1170-8 .

[29] Деврой, Л. ; Крушевски, П. (1996), «О числе Хортона-Стралера для случайных попыток» , RAIRO Informatique Théorique et Applications , 30 (5): 443–456, doi : 10.1051/ita/1996300504431 , MR 1435732 .

[30] Эквивалентно, семья с $k$ различными элементами имеет не более $2 к$ различные наборы с равенством, если это набор мощности.

[31] Эппштейн, Дэвид (2005), «Размерность решетки графа», Европейский журнал комбинаторики , 26 (5): 585–592, arXiv : cs.DS/0402028 , doi : 10.1016/j.ejc.2004.05.001 , МР 2127682 , S2CID 7482443 .

[32] Грэм, Рональд Л .; Ротшильд, Брюс Л .; Спенсер, Джоэл Х. (1980), Теория Рэмси , Wiley-Interscience, с. 78 .

[33] Байер, Дэйв ; Диаконис, Перси (1992), «Следуя за ласточкиным хвостом к его логову», The Annals of Applied Probability , 2 (2): 294–313, doi : 10.1214/aoap/1177005705 , JSTOR 2959752 , MR 1161056 .

[34] Мельхорн, Курт ; Сандерс, Питер (2008), «2.5 Пример – двоичный поиск», Алгоритмы и структуры данных: базовый набор инструментов (PDF) , Springer, стр. 34–36, ISBN 978-3-540-77977-3 .

[35] Робертс, Фред ; Тесман, Барри (2009), Прикладная комбинаторика (2-е изд.), CRC Press, стр. 206, ISBN 978-1-4200-9983-6 .

[36] Сипсер, Майкл (2012), «Пример 7.4», Введение в теорию вычислений (3-е изд.), Cengage Learning, стр. 277–278, ISBN 9781133187790 .

[37] Седжвик и Уэйн (2011) , с. 186 .

[FOOTNOTECormenLeisersonRivestStein2001156GoodrichTamassia2002238-38] Кормен и др. (2001) , с. 156; Гудрич и Тамассия (2002) , с. 238.

[FOOTNOTECormenLeisersonRivestStein2001276GoodrichTamassia2002159-39] Кормен и др. (2001) , с. 276; Гудрич и Тамассия (2002) , с. 159.

[FOOTNOTECormenLeisersonRivestStein2001879–880GoodrichTamassia2002464-40] Кормен и др. (2001) , с. 879–880; Гудрич и Тамассия (2002) , с. 464.

[41] Эдмондс, Джефф (2008), Как думать об алгоритмах , издательство Кембриджского университета, стр. 302, ISBN 978-1-139-47175-6 .

[FOOTNOTECormenLeisersonRivestStein2001844GoodrichTamassia2002279-42] Кормен и др. (2001) , с. 844; Гудрич и Тамассия (2002) , с. 279.

[FOOTNOTECormenLeisersonRivestStein2001section_28.2.-43] Кормен и др. (2001) , раздел 28.2.

[44] Костон, Хелен; Квакенбуш, Джон; Бразма, Алвис (2009), Анализ данных экспрессии генов на микрочипах: руководство для начинающих , John Wiley & Sons, стр. 49–50, ISBN 978-1-4443-1156-3 .

[45] Эйдхаммер, Ингвар; Барснес, Харальд; Эйде, Гейр Эгиль; Мартенс, Леннарт (2012), Вычислительные и статистические методы количественного определения белка с помощью масс-спектрометрии , John Wiley & Sons, стр. 105, ISBN 978-1-118-49378-6 .

[mga-46] Перейти обратно: ^а ^б Кэмпбелл, Мюррей; Грейтед, Клайв (1994), Путеводитель музыканта по акустике , Oxford University Press, стр. 78, ISBN 978-0-19-159167-9 .

[47] Рэндел, Дон Майкл , изд. (2003), Гарвардский музыкальный словарь (4-е изд.), The Belknap Press of Harvard University Press, стр. 416, ISBN 978-0-674-01163-2 .

[48] Франс, Роберт (2008), Введение в физическое воспитание и спортивную науку , Cengage Learning, стр. 282, ISBN 978-1-4180-5529-5 .

[49] Аллен, Элизабет; Триантафиллиду, Софи (2011), Справочник фотографии , Тейлор и Фрэнсис, стр. 228, ISBN 978-0-240-52037-7 .

[btzs-50] Перейти обратно: ^а ^б Дэвис, Фил (1998), За пределами зональной системы , CRC Press, стр. 17, ISBN 978-1-136-09294-7 .

[51] Аллен и Триантафиллиду (2011) , с. 235 .

[52] Цверман, Сьюзен; Окунь, Джеффри А. (2012), Справочник Общества визуальных эффектов: Рабочий процесс и методы , CRC Press, стр. 205, ISBN 978-1-136-13614-6 .

[53] Бауэр, Крейг П. (2013), Тайная история: история криптологии , CRC Press, стр. 332, ISBN 978-1-4665-6186-1 .

[Warren_2002-54] Перейти обратно: ^а ^б Уоррен-младший, Генри С. (2002), Hacker's Delight (1-е изд.), Аддисон Уэсли , стр. 215, ISBN 978-0-201-91465-8

[55] s , API ядра Linux, kernel.org , получено 17 октября 2010 г.

[ml73-56] Перейти обратно: ^а ^б ^с ^д Маджития, JC; Леван, Д. (1973), «Заметки о вычислениях логарифмов по основанию 2», Proceedings of the IEEE , 61 (10): 1519–1520, doi : 10.1109/PROC.1973.9318 .

[57] Стивенсон, Ян (2005), «9.6 Функции Fast Power, Log2 и Exp2», Производственный рендеринг: проектирование и реализация , Springer-Verlag, стр. 270–273, ISBN 978-1-84628-085-6 .

[Warren_2013-58] Уоррен-младший, Генри С. (2013) [2002], «11-4: Целочисленный логарифм» , Hacker's Delight (2-е изд.), Аддисон Уэсли – Pearson Education, Inc. , стр. 291, ISBN 978-0-321-84268-8 , 0-321-84268-5 .

[59] «7.12.6.10 Функции log2», спецификация ISO/IEC 9899:1999 (PDF) , стр. 226 .

[60] Редферн, Даррен; Кэмпбелл, Колин (1998), Справочник по Matlab® 5 , Springer-Verlag, стр. 141, ISBN 978-1-4612-2170-8 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]

[56]

[57]

[58]

[59]

[60]