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

Показатель степени двойки

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

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

${\displaystyle 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 году.

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

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

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

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

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

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

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

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

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

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

Обозначение

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

Некоторые авторы записывают двоичный логарифм как lg n , ^{[11] [12]} обозначение, указанное в The Chicago Manual of Style . ^[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 не следует использовать для двоичного логарифма, поскольку вместо этого он зарезервирован для десятичного логарифма log ₁₀ n . ^{[23] [24] [25]}

Приложения

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

Число цифр ( бит ) в двоичном представлении положительного целого числа n равно целой части 1 + log ₂  n , т.е. ^[12]

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

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

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

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

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

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

Сложность вычислений

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

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

Время выполнения алгоритма обычно выражается в нотации big O , которая используется для упрощения выражений путем опускания их постоянных множителей и членов низшего порядка. Поскольку логарифмы в разных основаниях отличаются друг от друга только постоянным множителем, можно также сказать, что алгоритмы, которые выполняются за время O (log ₂  n ) , работают, скажем, за время O (log ₁₃ n ) . Основание логарифма в таких выражениях, как O (log n ) или O ( n log n ) , поэтому не имеет значения и может быть опущено. ^{[11] [36]} Однако для логарифмов, которые появляются в показателе степени временного ограничения, основание логарифма не может быть опущено. Например, O (2 ^{log ₂  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 ₂  3} ) ^[42] и алгоритм Штрассена для умножения матриц n × n за время O ( n ^{log ₂  7} ) ^[43] . Появление двоичных логарифмов в этих временах выполнения можно объяснить ссылкой на основную теорему для рекуррентных уравнений «разделяй и властвуй» .

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

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

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

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

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

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

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

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

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

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

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

Фотография

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

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

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

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

Расчет

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

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

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

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

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

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

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

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

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

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

${\displaystyle \lfloor \log _{2}(n)\rfloor =31-\operatorname {nlz} (n).}$^[54]

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

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

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

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

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

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

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

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

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

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

Ссылки

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), Криптографические приложения аналитической теории чисел: нижние границы сложности и псевдослучайность, Progress in Computer Science and Applied Logic, т. 22, Birkhäuser, стр. 35, ISBN 978-3-0348-8037-4.
5. Эйлер, Леонард (1739), «Глава VII. De Variorum Intervallorum Receptis Appelationibus», Tentamen novae theoriae musicae ex certissismisharmoniae principiis dilucid expositae (на латыни), Санкт-Петербургская Академия, стр. 102–112.
6. Тегг, Томас (1829), «Двоичные логарифмы», Лондонская энциклопедия; или Универсальный словарь науки, искусства, литературы и практической механики: включающий популярный взгляд на современное состояние знаний, том 4, стр. 142–143.
7. Батшелет, Э. (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, стр. 232, ISBN 978-0-596-55317-3.
9. Колман, Бернард; Шапиро, Арнольд (1982), «11.4 Свойства логарифмов», Алгебра для студентов колледжей, Academic Press, стр. 334–335, ISBN 978-1-4832-7121-7.
10. Например, эта нотация используется в «Энциклопедии математики» и «Принстонском справочнике по математике» .
11. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990], Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill, стр. 34, 53–54, ISBN 0-262-03293-7
12. Седжвик, Роберт ; Уэйн, Кевин Дэниел (2011), Алгоритмы, Addison-Wesley Professional, стр. 185, ISBN 978-0-321-57351-3.
13. Чикагское руководство по стилю (25-е изд.), Издательство Чикагского университета, 2003, стр. 530.
14. Knuth, Donald E. (1997), Фундаментальные алгоритмы , Искусство программирования , т. 1 (3-е изд.), Addison-Wesley Professional, ISBN 978-0-321-63574-7, стр. 11. Та же самая запись была во 2-м издании той же книги 1973 года (стр. 23), но без указания автора Рейнгольда.
15. Трукко, Эрнесто (1956), «Заметка об информационном содержании графиков», Bull. Math. Biophys. , 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.
19. Goodrich, Michael T. ; Tamassia, Roberto (2002), Algorithm Design: Foundations, Analysis, and Internet Examples , John Wiley & Sons, стр. 23, Одним из интересных и порой даже удивительных аспектов анализа структур данных и алгоритмов является повсеместное присутствие логарифмов... Как это принято в компьютерной литературе, мы опускаем написание основания b логарифма, когда b  = 2 .
20. Tafel, Ханс Йорг (1971), Einführung in die digitale Datenverarbeitung [ Введение в цифровую обработку информации ] (на немецком языке), Мюнхен: Carl Hanser Verlag , стр. 20–21, ISBN 3-446-10569-7
21. Титце, Ульрих; Шенк, Кристоф (1999), Halbleiter-Schaltungstechnik (на немецком языке) (1-е исправленное переиздание, 11-е изд.), Springer Verlag , стр. 1370, ISBN 3-540-64192-0
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, Висбаден: Ф.А. Брокгауз, 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), Теория информации, Cambridge University Press, стр. 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 ^k различных множеств, с равенством, когда оно является множеством мощности.
31. Эппштейн, Дэвид (2005), «Размерность решетки графа», Европейский журнал комбинаторики , 26 (5): 585–592, arXiv : cs.DS/0402028 , doi : 10.1016/j.ejc.2004.05.001, MR  2127682, S2CID  7482443.
32. Грэм, Рональд Л.; Ротшильд , Брюс Л.; Спенсер , Джоэл Х. (1980), Теория Рамсея , Wiley-Interscience, стр. 78.
33. Байер, Дэйв ; Диаконис, Перси (1992), «По следам ласточкина хвоста в его логово», Анналы прикладной вероятности , 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.
38. Кормен и др. (2001), с. 156; Гудрич и Тамассия (2002), с. 238.
39. Кормен и др. (2001), с. 276; Гудрич и Тамассия (2002), с. 159.
40. Кормен и др. (2001), с. 879–880; Гудрич и Тамассия (2002), с. 464.
41. Эдмондс, Джефф (2008), Как думать об алгоритмах, Cambridge University Press, стр. 302, ISBN 978-1-139-47175-6.
42. Кормен и др. (2001), с. 844; Гудрич и Тамассия (2002), с. 279.
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.
46. Кэмпбелл, Мюррей; Грейтед, Клайв (1994), Руководство музыканта по акустике, Oxford University Press, стр. 78, ISBN 978-0-19-159167-9.
47. Рэндел, Дон Майкл , ред. (2003), Гарвардский музыкальный словарь (4-е изд.), 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.
50. Davis, Phil (1998), Beyond the Zone System, 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.
54. Warren Jr., Henry S. (2002), Hacker's Delight (1-е изд.), Addison Wesley , стр. 215, ISBN 978-0-201-91465-8
55. fls, API ядра Linux, kernel.org , получено 17 октября 2010 г.
56. Majithia, JC; Levan, D. (1973), "Заметка о вычислениях логарифмов по основанию 2", Труды IEEE , 61 (10): 1519–1520, doi :10.1109/PROC.1973.9318.
57. Стивенсон, Ян (2005), «9.6 Быстрые функции Power, Log2 и Exp2», Production Rendering: Design and Implementation, Springer-Verlag, стр. 270–273, ISBN 978-1-84628-085-6.
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.

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

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