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

График

log 2 x

как функция положительного действительного числа

x

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

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

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

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

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

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

История [ править ]

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

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

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

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

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

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

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

{\ Displaystyle \ журнал _ {2} ху = \ журнал _ {2} х + \ журнал _ {2} у}

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

{\ displaystyle \ 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] или logarithmus dyadis . ^[20] Стандарты DIN 1302 [ de ] , ISO 31-11 и ISO 80000-2 рекомендуют еще одно обозначение, $lb n$ . Согласно этим стандартам, $lg n$ не следует использовать для двоичного логарифма, так как вместо этого он зарезервирован для $журнала$ общего логарифма. $10 п$ . ^[23]^[24]^[25]

Приложения [ править ]

Теория информации [ править ]

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

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

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

Комбинаторика [ править ]

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

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

Каждое двоичное дерево с $n$ листьями имеет высоту не менее $log 2 n$ , с равенством, когда $n$ является степенью двойки, а дерево является полным двоичным деревом . ^[28] Соответственно, число Штралера для речной системы с $n$ притоками не превышает $log 2 n + 1$ . ^[29]
Каждое семейство наборов с $n$ различными наборами имеет по крайней мере $log 2 n$ элементов в своем объединении с равенством, когда семейство является степенным набором . ^[30]
Каждый частичный куб с $n$ вершинами имеет изометрическую размерность не менее $log 2 n$ и не более $1 / 2 n log 2 n$ ребер, с равенством, когда частичный куб является графом гиперкуба . ^[31]
Согласно теореме Рамсея , каждый неориентированный граф с $n$ вершинами имеет либо клику, либо независимое множество логарифмического по $n$ размера . Точный размер, который может быть гарантирован, неизвестен, но наилучшие известные оценки его размера включают двоичные логарифмы. В частности, все графы имеют клику или независимое множество размером не менее $1 / 2 log 2 n (1 - o (1)),$ и почти все графы не имеют клики или независимого набора размером больше $2 log 2 n (1 + o (1))$ . ^[32]
С помощью математического анализа модели случайного тасования Гилберта – Шеннона – Ридса можно показать, что сколько раз нужно перетасовать колоду из $n$ карт с помощью тасования карт , чтобы получить распределение перестановок, близкое к равномерно случайный, составляет приблизительно $3 / 2 журнал 2 п$ . Этот расчет является основанием для рекомендации перетасовать колоды из 52 карт семь раз. ^[33]

Вычислительная сложность [ править ]

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

Двоичный логарифм также часто появляется в анализе алгоритмов , ^[19] не только из-за частого использования двоичного числа арифметики в алгоритмах, но и потому , что двоичные логарифмы возникают при анализе алгоритмов , основанных на двух направлениях ветвления. ^[14] Если проблема изначально имеет $n$ вариантов решения, и каждая итерация алгоритма уменьшает количество вариантов в два раза, то количество итераций, необходимых для выбора одного варианта, снова является неотъемлемой частью $log 2. п$ . Эта идея используется при анализе нескольких алгоритмов и структур данных . Например, в бинарном поискеразмер решаемой проблемы уменьшается вдвое с каждой итерацией, и поэтому для получения решения задачи размера $n$ требуется примерно $log 2 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]Однако для логарифмов, которые появляются в показателе степени привязки по времени, основание логарифма не может быть опущено. Например, $O (2 log 2 n)$ не то же самое, что $O (2 ln n),$ потому что первое равно $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 log 23)$ , ^[42] и алгоритм Штрассена для умножения $n \times n$ матриц за время $O (n log 27)$ . ^[43] Появление двоичных логарифмов в этих временах выполнения можно объяснить ссылкой на основную теорему для повторений "разделяй и властвуй"..

Биоинформатика [ править ]

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

В биоинформатики , микрочипы используются для измерения того, насколько сильно отличаются гены экспрессируются в образце биологического материала. Различные скорости экспрессии гена часто сравнивают, используя двоичный логарифм отношения скоростей экспрессии: логарифм отношения двух скоростей экспрессии определяется как двоичный логарифм отношения двух скоростей. Двоичные логарифмы позволяют удобно сравнивать скорости экспрессии: удвоенная скорость экспрессии может быть описана логарифмическим соотношением $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]

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

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

Расписание занятий спортом [ править ]

В соревновательных играх и видах спорта, в которых участвуют два игрока или команды в каждой игре или матче, двоичный логарифм указывает количество раундов, необходимых в турнире с одним выбыванием, необходимых для определения победителя. Например, для турнира из $4$ игроков требуется $журнал 2 4 = 2$ раунда для определения победителя, для турнира из $32$ команд требуется $журнал 2 32 = 5$ раундов и т. Д. В этом случае для $n$ игроков / команд, где $n$ не является степенью of 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]

Расчет [ править ]

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

Конверсия из других баз [ править ]

Простой способ вычислить $log 2 n$ на калькуляторах , не имеющих функции $log 2,$ - это использовать функции натурального логарифма ( $ln$ ) или десятичного логарифма ( $log$ или $log 10$ ), которые можно найти на большинстве научных калькуляторов . Конкретные формулы изменения базовых формул логарифма для этого: ^[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]

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

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

^[54]

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

Итерационное приближение [ править ]

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

Результат этого выражается следующими рекурсивными формулами, в которых - количество квадратов, необходимых для i-й итерации алгоритма: $m_{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 - (m 1 + m 2 + ... + m i)$ .^[56]

Поддержка программных библиотек [ править ]

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

Ссылки [ править ]

^ Гроза, Вивиан Шоу; Шелли, Сюзанна М. (1972), Математика Precalculus , Нью-Йорк: Холт, Райнхарт и Уинстон, стр. 182, ISBN 978-0-03-077670-0.
^ Стифель, Майкл (1544), Arithmetica integ (на латыни), стр. 31 год. Копия той же таблицы с еще двумя записями отображается на стр. 237, а другая копия, расширенная до отрицательных степеней, появляется на стр. 249b.
^ Джозеф, GG (2011), Гребень павлина: неевропейские корни математики (3-е изд.), Princeton University Press, стр. 352.
^ См., Например, Шпарлински, Игорь (2013), Криптографические приложения аналитической теории чисел: нижние границы сложности и псевдослучайность , Progress in Computer Science and Applied Logic, 22 , Birkhäuser, p. 35, ISBN 978-3-0348-8037-4.
^ Эйлер, Леонард (1739), «Глава VII. De Variorum Intervallorum Receptis Appelationibus», Tentamen novae theoriae musicae ex certissismisharmoniae Principiis dilucide expositae (на латыни), Санкт-Петербургская академия, стр. 102–112.
^ Тегг, Томас (1829), «Двоичные логарифмы», Лондонская энциклопедия; или, Универсальный словарь науки, искусства, литературы и практической механики: содержащий популярный взгляд на современное состояние знаний, Том 4 , стр. 142–143.
^ Batschelet, E. (2012), Введение в математику для жизни ученых , Springer, стр. 128, ISBN 978-3-642-96080-2.
^ Например, Microsoft Excel предоставляетIMLOG2функцию сложных двоичных логарифмов: см. Bourg, David M. (2006), Excel Scientific and Engineering Cookbook , O'Reilly Media, p. 232, ISBN 978-0-596-55317-3.
^ Колман, Бернард; Шапиро, Арнольд (1982), "11.4 Свойства логарифмов", Алгебра для студентов колледжей , Academic Press, стр. 334–335, ISBN 978-1-4832-7121-7.
^ Например, это обозначение, используемое в Энциклопедии математики и The Princeton Companion to Mathematics .
^ а б Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001) [1990], Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill, стр. 34, 53–54, ISBN 0-262-03293-7
^ a b Седжвик, Роберт ; Уэйн, Кевин Дэниел (2011), Алгоритмы , Addison-Wesley Professional, стр. 185, ISBN 978-0-321-57351-3.
↑ Чикагское руководство по стилю (25-е изд.), University of Chicago Press, 2003, p. 530.
^ a b Knuth, Дональд Э. (1997), Фундаментальные алгоритмы , Искусство компьютерного программирования , 1 (3-е изд.), Addison-Wesley Professional, ISBN 978-0-321-63574-7, стр. 11 . Такие же обозначения были во втором издании той же книги 1973 г. (стр. 23), но без упоминания Рейнгольда.
^ Trucco, Эрнесто (1956), "Примечание об информационном содержании графиков", Bull. Математика. Биофиз. , 18 (2): 129-135, DOI : 10.1007 / BF02477836 , МР 0077919 .
^ Mitchell, Джон Н. (1962), "Компьютерное умножение и деление с использованием двоичных логарифмов", IRE Сделка по электронно - вычислительным машинам , 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.$ .
^ a b Гудрич, Майкл Т .; Тамассия, Роберто (2002), Разработка алгоритмов: основы, анализ и примеры в Интернете , John Wiley & Sons, стр. 23, один из интересных и порой даже неожиданных аспектов анализа структур данных и алгоритмов являются повсеместным присутствием логарифмов ... Как это принято в вычислительной литературе мы не писать базовые $б$ логарифма при $б$ $= 2$ .
^ a b c Tafel, Hans Jörg (1971), Einführung in die digitale Datenverarbeitung [ Введение в цифровую обработку информации ] (на немецком языке), Мюнхен: Карл Хансер Верлаг , стр. 20–21, ISBN 3-446-10569-7
^ Титце, Ульрих; Шенк, Кристоф (1999), Halbleiter-Schaltungstechnik (на немецком языке) (1-е исправленное переиздание, 11-е изд.), Springer Verlag , стр. 1370 , ISBN 3-540-64192-0
^ Бауэр, Фридрих Л. (2009), Истоки и основы вычислений: в сотрудничестве с Heinz Nixdorf MuseumsForum , Springer Science & Business Media , стр. 54, ISBN 978-3-642-02991-2.
^ Для DIN 1302 см. Brockhaus Enzyklopädie in zwanzig Bänden [ Двадцать томов энциклопедии Брокгауза ] (на немецком языке), 11 , Wiesbaden: FA Brockhaus, 1970, p. 554, ISBN 978-3-7653-0000-4.
^ Для ISO 31-11 см. Thompson, Ambler; Тейлор, Барри М. (март 2008 г.), Руководство по использованию Международной системы единиц (СИ) - Специальная публикация NIST 811, издание 2008 г. - Второй выпуск (PDF) , NIST , стр. 33 .
^ Для ISO 80000-2 см. «Величины и единицы - Часть 2: Математические знаки и символы, используемые в естественных науках и технологиях» (PDF) , Международный стандарт ISO 80000-2 (1-е изд.), 1 декабря 2009 г., Раздел 12, Экспоненциальные и логарифмические функции, с. 18 .
^ Ван дер Люббе, Jan CA (1997), Теория информации , Cambridge University Press, стр. 3, ISBN 978-0-521-46760-5.
↑ Стюарт, Ян (2015), Укрощение бесконечного , Quercus, стр. 120, ISBN 9781623654733, в высшей математике и естественных науках единственным важным логарифмом является натуральный логарифм.
^ Leiss, Эрнст Л. (2006), Companion программиста для алгоритма анализа , CRC Press, стр. 28, ISBN 978-1-4200-1170-8.
^ Devroye, L .; Крушевский, P. (1996), "О числе Хортона-Strahler для случайных попыток" , RAIRO Informatique Théorique и их приложения , 30 (5): 443-456, DOI : 10,1051 / ит / 1996300504431 , МР 1435732 .
^ Эквивалентно, семья с $k$ различными элементами имеет не более $2 k$ различных наборов с равенством, когда это набор мощности.
^ Эппштейн, Дэвид (2005), «Решеточная размерность графа», European Journal of Combinatorics , 26 (5): 585–592, arXiv : cs.DS / 0402028 , doi : 10.1016 / j.ejc.2004.05.001 , Руководство по ремонту 2127682 .
^ Грэм, Рональд Л .; Ротшильд, Брюс Л .; Спенсер, Джоэл Х. (1980), Теория Рэмси , Wiley-Interscience, стр. 78.
^ Байер, Дэйв ; Diaconis, Persi (1992), "Скользящий в форме ласточкина хвоста перетасовать в его логове", Анналы прикладной вероятности , 2 (2): 294-313, DOI : 10,1214 / aoap / 1177005705 , JSTOR 2959752 , МР 1161056 .
^ Мельхорн, Курт ; Сандерс, Питер (2008), «Пример 2.5 - двоичный поиск», Алгоритмы и структуры данных: The Basic Toolbox (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 .
^ Кормен и др., Стр. 156; Гудрич и Тамассия, стр. 238.
^ Кормен и др., Стр. 276; Гудрич и Тамассия, стр. 159.
^ Корменадр, стр 879-880..; Гудрич и Тамассия, стр. 464.
^ Эдмондс, Джефф (2008), Как думать об алгоритмах , Cambridge University Press, стр. 302, ISBN 978-1-139-47175-6.
^ Кормен и др., Стр. 844; Гудрич и Тамассия, стр. 279.
^ Кормен и др., Раздел 28.2.
^ Каустон, Хелен; Quackenbush, Джон; Brazma, Alvis (2009), Анализ данных экспрессии генов на микрочипах: руководство для начинающих , John Wiley & Sons, стр. 49–50, ISBN 978-1-4443-1156-3.
^ Эйдхаммер, Ингвар; Барснес, Харальд; Эйде, Гейр Эгиль; Мартенс, Леннарт (2012), Вычислительные и статистические методы количественного определения белка с помощью масс-спектрометрии , John Wiley & Sons, стр. 105, ISBN 978-1-118-49378-6.
^ а б Кэмпбелл, Мюррей; Greated, Клайв (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.
^ a b Дэвис, Фил (1998), За пределами системы зон , CRC Press, стр. 17, ISBN 978-1-136-09294-7.
^ Аллен и Триантафиллиду (2011) , стр. 235 .
^ Цверман, Сьюзен; Окунь, Джеффри А. (2012), Справочник Общества визуальных эффектов: Рабочий процесс и методы , CRC Press, стр. 205, ISBN 978-1-136-13614-6.
Перейти ↑ Bauer, Craig P. (2013), Secret History: The Story of Cryptology , CRC Press, p. 332, ISBN 978-1-4665-6186-1.
^ a b Уоррен-младший, Генри С. (2002), Hacker's Delight (1-е изд.), Addison Wesley , p. 215, ISBN 978-0-201-91465-8
^ fls , API ядра Linux, kernel.org , получено 17 октября 2010 г.
^ a b c d Majithia, JC; Леван, Д. (1973), "Замечание о базовых 2-логарифмических вычислений", Труды IEEE , 61 (10): 1519-1520, DOI : 10,1109 / PROC.1973.9318.
↑ Stephenson, Ian (2005), «9.6 Fast Power, Log2 и Exp2 Functions», Production Rendering: Design and Implementation , Springer-Verlag, pp. 270–273, ISBN. 978-1-84628-085-6.
↑ Уоррен-младший, Генри С. (2013) [2002], «11-4: Целочисленный логарифм» , Hacker's Delight (2-е изд.), Addison Wesley - 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), Математика Precalculus , Нью-Йорк: Холт, Райнхарт и Уинстон, стр. 182, ISBN 978-0-03-077670-0.

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

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

[4] См., Например, Шпарлински, Игорь (2013), Криптографические приложения аналитической теории чисел: нижние границы сложности и псевдослучайность , Progress in Computer Science and Applied Logic, 22 , Birkhäuser, p. 35, ISBN 978-3-0348-8037-4.

[5] Эйлер, Леонард (1739), «Глава VII. De Variorum Intervallorum Receptis Appelationibus», Tentamen novae theoriae musicae ex certissismisharmoniae Principiis dilucide expositae (на латыни), Санкт-Петербургская академия, стр. 102–112.

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

[7] Batschelet, E. (2012), Введение в математику для жизни ученых , Springer, стр. 128, ISBN 978-3-642-96080-2.

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

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

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

[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, p. 530.

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

[15] Trucco, Эрнесто (1956), "Примечание об информационном содержании графиков", Bull. Математика. Биофиз. , 18 (2): 129-135, DOI : 10.1007 / BF02477836 , МР 0077919 .

[16] Mitchell, Джон Н. (1962), "Компьютерное умножение и деление с использованием двоичных логарифмов", IRE Сделка по электронно - вычислительным машинам , 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, один из интересных и порой даже неожиданных аспектов анализа структур данных и алгоритмов являются повсеместным присутствием логарифмов ... Как это принято в вычислительной литературе мы не писать базовые $б$ логарифма при $б$ $= 2$ .

[Tafel_1971-20] Tafel, Hans Jörg (1971), Einführung in die digitale Datenverarbeitung [ Введение в цифровую обработку информации ] (на немецком языке), Мюнхен: Карл Хансер Верлаг , стр. 20–21, ISBN 3-446-10569-7

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

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

[23] Для DIN 1302 см. Brockhaus Enzyklopädie in zwanzig Bänden [ Двадцать томов энциклопедии Брокгауза ] (на немецком языке), 11 , Wiesbaden: FA Brockhaus, 1970, p. 554, ISBN 978-3-7653-0000-4.

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

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

[26] Ван дер Люббе, Jan CA (1997), Теория информации , Cambridge University Press, стр. 3, ISBN 978-0-521-46760-5.

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

[28] Leiss, Эрнст Л. (2006), Companion программиста для алгоритма анализа , CRC Press, стр. 28, ISBN 978-1-4200-1170-8.

[29] Devroye, L .; Крушевский, P. (1996), "О числе Хортона-Strahler для случайных попыток" , RAIRO Informatique Théorique и их приложения , 30 (5): 443-456, DOI : 10,1051 / ит / 1996300504431 , МР 1435732 .

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

[31] Эппштейн, Дэвид (2005), «Решеточная размерность графа», European Journal of Combinatorics , 26 (5): 585–592, arXiv : cs.DS / 0402028 , doi : 10.1016 / j.ejc.2004.05.001 , Руководство по ремонту 2127682 .

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

[33] Байер, Дэйв ; Diaconis, Persi (1992), "Скользящий в форме ласточкина хвоста перетасовать в его логове", Анналы прикладной вероятности , 2 (2): 294-313, DOI : 10,1214 / aoap / 1177005705 , JSTOR 2959752 , МР 1161056 .

[34] Мельхорн, Курт ; Сандерс, Питер (2008), «Пример 2.5 - двоичный поиск», Алгоритмы и структуры данных: The Basic Toolbox (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 .

[38] Кормен и др., Стр. 156; Гудрич и Тамассия, стр. 238.

[39] Кормен и др., Стр. 276; Гудрич и Тамассия, стр. 159.

[40] Корменадр, стр 879-880..; Гудрич и Тамассия, стр. 464.

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

[42] Кормен и др., Стр. 844; Гудрич и Тамассия, стр. 279.

[43] Кормен и др., Раздел 28.2.

[44] Каустон, Хелен; Quackenbush, Джон; Brazma, Alvis (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] а б Кэмпбелл, Мюррей; Greated, Клайв (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] Перейти ↑ Bauer, Craig P. (2013), Secret History: The Story of Cryptology , CRC Press, p. 332, ISBN 978-1-4665-6186-1.

[Warren_2002-54] Уоррен-младший, Генри С. (2002), Hacker's Delight (1-е изд.), Addison Wesley , p. 215, ISBN 978-0-201-91465-8

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

[ml73-56] Majithia, JC; Леван, Д. (1973), "Замечание о базовых 2-логарифмических вычислений", Труды IEEE , 61 (10): 1519-1520, DOI : 10,1109 / PROC.1973.9318.

[57] Stephenson, Ian (2005), «9.6 Fast Power, Log2 и Exp2 Functions», Production Rendering: Design and Implementation , Springer-Verlag, pp. 270–273, ISBN. 978-1-84628-085-6.

[Warren_2013-58] Уоррен-младший, Генри С. (2013) [2002], «11-4: Целочисленный логарифм» , Hacker's Delight (2-е изд.), Addison Wesley - 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.