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

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

График 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 году.

Силы двойки известны с древности; например, они появляются в «Элементах» Евклида , «Реквизит». IX.32 (о факторизации степеней двойки) и IX.36 (половина теоремы Евклида–Эйлера , о строении четных совершенных чисел ). А двоичный логарифм степени двойки — это всего лишь его позиция в упорядоченной последовательности степеней двойки. На этом основании Майклу Стифелу приписывают публикацию первой известной таблицы двоичных логарифмов в 1544 году. Его книга «Арифметика Интегра» содержит несколько таблиц, в которых показаны целые числа с соответствующими степенями двойки. Перестановка строк этих таблиц позволяет интерпретировать их как таблицы двоичных логарифмов. ^{[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]} — обозначение, указанное в Чикагском руководстве по стилю . ^[13] Дональд Кнут приписывает это обозначение предложению Эдварда Рейнгольда , ^[14] но его использование как в теории информации, так и в информатике датируется еще до того, как Рейнгольд стал активным. ^{[15] [16]} Двоичный логарифм также записывается как log n с предварительным утверждением, что основанием по умолчанию для логарифма является  2 . ^{[17] [18] [19]} Другое обозначение, которое часто используется для той же функции (особенно в немецкой научной литературе), — это ld n , ^{[20] [21] [22]} от латинского logarithmus Dualis ^[20] или logarithmus yadis. . ^[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]

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

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

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

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

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

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

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

Время работы алгоритма обычно выражается в виде большой буквы 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]

Расчет

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

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

Простой способ вычислить log ₂  n на калькуляторах , которые не имеют функции log _2, — это использовать функции натурального логарифма ( 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 бита во входных данных. В этом смысле это дополнение к операции поиска первого набора , которая находит индекс младшего 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. Версия этой функции по умолчанию принимает аргументы двойной точности, но ее варианты позволяют аргументу иметь одинарную точность или быть длинным двойным . ^[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, vol. 22, Биркхойзер, с. 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, p. 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-е изд.), University of Chicago Press, 2003, стр. 530.
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..
19. Гудрич, Майкл Т .; Тамассиа, Роберто (2002), Разработка алгоритмов: основы, анализ и примеры из Интернета , 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), Истоки и основы вычислений: в сотрудничестве с Музейным форумом Хайнца Никсдорфа, 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), «Размерность решетки графа», European Journal of Combinatorics , 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), «Следуя за ласточкиным хвостом к его логову», Анналы прикладной вероятности , 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-е изд.), 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.
50. Дэвис, Фил (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. Уоррен-младший, Генри С. (2002), Hacker's Delight (1-е изд.), Аддисон Уэсли , стр. 215, ISBN 978-0-201-91465-8
55. fls, API ядра Linux, kernel.org , получено 17 октября 2010 г.
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.
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.

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

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