Двійковий логарифм

В математиці, двійковий логарифм (log₂n) це степінь, до якого треба піднести число 2, щоб отримати значення n. Тобто, для будь-якого дійсного числа x, виконується еквівалентність

Графік log₂x як функції додатних дійсних чисел x

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

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

Бінарний логарифм це логарифм за основою 2. Функція двійкового логарифма є оберненою функцією функції степеня двійки. Разом із звичайним позначенням log₂, існують альтернативні позначення двійкового логарифма такі як: lg, ld, lb, і (із попереднім узгодженням, що за замовчуванням основою позначеного так логарифма є 2) log.

Історично, перше застосування двійкових логарифмів сталося в теорії музики, його використав Леонард Ейлер: двійковий логарифм відношення частот двох музичних тонів дає можливість розрахувати кількість октав, на які відрізняються ці тони. Двійкові логарифми можна застосувати для розрахунку довжини представлення числа в двійковій системі числення, або кількість бітів, необхідних аби закодувати повідомлення в теорії інформації. В комп'ютерних науках, вони використовуються для підрахунку кількості кроків, які треба здійснити при двійковому пошуку і подібних алгоритмах. Інші області, в яких часто використовується двійковий логарифм, це: комбінаторика, біоінформатика, планування спортивних турнірів, і фотографія.

Бінарні логарифми входять до стандартних математичних функцій мови програмування C та до інших математичних програмних пакетів.

Цілу частину двійкового логарифма можна знайти здійснивши операцію пошук першої одиниці над цілим числом, або через пошук експоненти значення з рухомою комою.

Історія

Докладніше: Історія логарифмів

Леонард Ейлер був першим, хто застосував двійкові логарифми в теорії музики, у 1739.

Степені двійки були відомі і використовувалися ще з античних часів; наприклад вони є в Euclid's Elements, Книга IX.32 (про факторизацію степенів двійки) і IX.36 (в частині ^[en], про структуру парних досконалих чисел). А двійковий логарифм степеня двійки позначав позицію в упорядкованій послідовності степенів двійки.

На цій основі, Михаель Штифель створив і опублікував першу відому таблицю двійкових логарифмів в 1544. Його книга Arthmetica Integra містила декілька таблиць, які впорядковували цілі числа із відповідними їхніми степенями двійки. Якщо розвернути навпаки рядки цих таблиць їх можна інтерпретувати як таблиці двійкових логарифмів.

Раніше за Штифеля, у 8-му столітті Джайнійському математику ^[en] створив попередника двійкового логарифма. Концепція Вірасена, що називалася ardhacheda визначалася як кількість разів, при яких задане число можна поділити порівну на два. Це визначення приводить до функції, яка за змістом збігається з двійковим логарифмом за основою два, але відрізняється для інших цілих, і дає ^[en], а не логарифм.

Сучасна форма двійкового логарифма, що застосовується до будь-якого числа (не лише степені двійки) була в явному вигляді розглянута Леонардом Ейлером в 1739. Ейлер започаткував використання двійкових логарифмів в теорії музики, задовго до їхнього більш значимого використання в теорії інформації і комп'ютерних науках. Як частину своєї роботи в цій сфері, Ейлер опублікував таблицю логарифмів для цілих чисел від 1 до 8, з точністю до сьомого десяткового знаку точності.

Визначення і властивості

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

Як і для інших логарифмів, двійковий логарифм задовольняє наступним рівнянням, які можуть використовуватись для спрощення формул, які поєднують двійкові логарифми із множенням або зведенням в ступінь:

${\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 дорівнюватиме цілій частині числа 1 + log₂n.

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

В теорії інформації, визначення кількості власної інформації та інформаційна ентропія часто задаються за допомогою двійкового логарифма, тим самим представляючи біт як фундаментальну одиницю інформації. Однак, в альтернативних представленнях цих визначень також використовують натуральний логарифм і нат.

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

Хоча натуральний логарифм є більш важливим ніж двійковий логарифм для багатьох галузей чистої математики, таких як теорія чисел і математичний аналіз, двійковий логарифм має ряд застосувань в комбінаториці:

• Кожне двійкове дерево кожне n листя має висоту принаймні в log₂n, і стає рівним цьому значенню, коли n є степенем двійки, а саме дерево є (повним двійковим деревом). Відповідно, число Стрехлера річкової системи із n притоками буде щонайбільше дорівнювати log₂n + 1.
• Кожне сімейство множин з n різними наборами має принаймні log₂n елементів в купі, і буде рівністю коли це сімейство становить булеан.
• Кожен частковий куб із n вершинами має ізометричну розмірність щонайменше в log₂n, і має не більше ніж 1/2 n log₂n ребер, при чому рівність буде, якщо частковий куб є графом гіперкуба.
• Відповідно до Теореми Рамсея, кожний неорієнтований граф з n-вершин має або кліку або незалежну множину з розміром в логарифмічній залежності із n. Точний розмір гарантовано не відомий, але найкраща відома межа цього розміру застосовує двійковий логарифм. Зокрема, всі графи мають кліку або незалежну множину розміром принаймні в 1/2 log₂n (1 − o(1)) і майже всі графи не мають кліки або незалежної множини більшого розміру ніж 2 log₂n (1 + o(1)).
• Із теорії математичного аналізу ^[en] для випадкового тасування кар, можна визначити число разів необхідних при тасуванні колоди з n-карт, використовуючи метод каскадного тасування, аби отримати кількість перестановок, що будуть близкі до рівномірного розподілу, і це значення приблизно дорівнює 3/2 log₂n. Цей підрахунок дав основу для рекомендації, що колода з 52-карт повинна перемішуватись сім разів.

Обчислювальна складність

Двійковий пошук в відсортованому масиві, часова складність алгоритму розраховується за допомогою двійкових логарифмів

Двійковий логарифм також часто фігурує в аналізі алгоритмів, не тільки через часте використання двійкової арифметики в алгоритмах, а й тому, що двійкові логарифми зустрічаються при аналізі алгоритмів, заснованих на двонаправлених розгалуженнях. Якщо задача початково має n варіантів шляху вирішення, а кожна ітерація алгоритму зменшує кількість варіантів в два рази, тоді кількість ітерацій, необхідних аби завершити пошук на одному з варіантів знову таки є цілою частиною від log₂n. Цей підхід використовується при аналізі багатьох алгоритмів і структур даних. Наприклад, при двійковому пошуку, об'єм задачі, що розв'язується змешнується навпіл при кожній ітерації, і таким чином приблизно log₂n ітерацій необхідно здійснити або отримати задачу розміром 1, що означає, що задачу можна вирішити за скінченний передбачений час. Аналогічно, ідеально збалансоване дерево двійкового пошуку, яке містить n елементів має висоту log₂(n + 1) − 1.

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

Алгоритми з часом виконання O(n log n) іноді називають ^[en]. Прикладами алгоритмів із часом виконання O(log n) або O(n log n) є:

• Швидке сортування і інші алгоритми сортування порівняннями
• Пошук в збалансованому двійковому дереві пошуку
• Швидке піднесення до степеня
• Задача пошуку найбільшої зростаючої підпослідовності

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

В теорії музики, інтервал або різниця сприйняття між двома тонами визначається відношенням їх частот. Інтервали, що утворені за допомогою співвідношення раціональних чисел із малими чисельниками і знаменниками сприймаються особливо милозвучно. Найпростішим і найважливішим із таких інтервалів є октава, що має співвідношення частот 2:1. Кількість октав, на які відрізняються звукові тони дорівнюють двійковому логарифму від співвідношення їх частот.

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

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

^[en] визначається тим самим способом, але матиме множник 1000 замість 1200.

Фотографія

У фотографії, ^[en] вимірюється як двійковий логарифм від кількості світла, яке досягає плівки або сенсору зображення, у відповідності до закону Вебера-Фехнера, який описує логарифмічний характер сприйняття світла зоровою системою людини. Один крок зміни експозиції є однією одиницею логарифмічної шкали за основою-2. Більш точно, значення експозиції фотографії визначається як

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

де N це f-число діафрагми, яке вимірює апертуру лінзи під час експозиції, а t це тривалість експозиції в секундах.

Двійкові логарифми також використовуються в ^[en], щоб оцінити динамічний діапазон світлочутливого матеріалу або цифрового сенсора.

Обчислення

Інженерний калькулятор (1974). Кнопки ln і log знаходяться в другому рядку; немає кнопки log₂.

Перетворення із інших основ

Простим способом розрахувати значення log₂n на калькуляторі, який не має функції log₂, це використати натуральний логарифм (ln), звичайний логарифм (log або log₁₀), які можна знайти в багатьох ^[en]. Для цього існує формула (зміна основи логарифма):

${\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.}$

Примітки

1. Groza, Vivian Shaw; Shelley, Susanne M. (1972), , New York: Holt, Rinehart and Winston, с. 182, ISBN , архів оригіналу за 3 липня 2021, процитовано 9 грудня 2016.
2. Stifel, Michael (1544), (Latin) , с. 31, архів оригіналу за 16 лютого 2022, процитовано 9 грудня 2016. Копія тієї самої таблиці з двома додатковими записами згадується на с. 237, і інша копія розширена до від'ємних значень знаходиться на с. 249b.
3. Joseph, G. G. (2011), (вид. 3rd), Princeton University Press, с. 352, архів оригіналу за 17 червня 2016, процитовано 9 грудня 2016.
4. See, e.g., Shparlinski, Igor (2013), , Progress in Computer Science and Applied Logic, т. 22, Birkhäuser, с. 35, ISBN , архів оригіналу за 29 червня 2016, процитовано 9 грудня 2016.
5. (1739), Chapter VII. De Variorum Intervallorum Receptis Appelationibus, (Latin) , Saint Petersburg Academy, с. 102—112, архів оригіналу за 11 жовтня 2018, процитовано 9 грудня 2016.
6. Tegg, Thomas (1829), Binary logarithms, , с. 142—143, архів оригіналу за 23 травня 2021, процитовано 9 грудня 2016.
7. Batschelet, E. (2012), , Springer, с. 128, ISBN , архів оригіналу за 10 червня 2016, процитовано 8 грудня 2016.
8. Наприклад, Microsoft Excel надає функцію IMLOG2 для комплексних двійкових логарифмів: див. Bourg, David M. (2006), , O'Reilly Media, с. 232, ISBN , архів оригіналу за 25 квітня 2016, процитовано 8 грудня 2016.
9. Kolman, Bernard; Shapiro, Arnold (1982), 11.4 Properties of Logarithms, , Academic Press, с. 334—335, ISBN , архів оригіналу за 13 травня 2016, процитовано 8 грудня 2016.
10. ; Wayne, Kevin Daniel (2011), , Addison-Wesley Professional, с. 185, ISBN , архів оригіналу за 23 грудня 2016, процитовано 8 грудня 2016.
11. Van der Lubbe, Jan C. A. (1997), , Cambridge University Press, с. 3, ISBN , архів оригіналу за 3 жовтня 2016, процитовано 8 грудня 2016.
12. Stewart, Ian (2015), , Quercus, с. 120, ISBN , архів оригіналу за 29 червня 2016, процитовано 9 грудня 2016, in advanced mathematics and science the only logarithm of importance is the natural logarithm.
13. Leiss, Ernst L. (2006), , CRC Press, с. 28, ISBN , архів оригіналу за 12 серпня 2020, процитовано 9 грудня 2016.
14. ; Kruszewski, P. (1996), , RAIRO Informatique Théorique et Applications, 30 (5): 443—456, MR 1435732, архів оригіналу за 7 жовтня 2015, процитовано 9 грудня 2016.
15. Equivalently, a family with k distinct elements has at most 2^k distinct sets, with equality when it is a power set.
16. Eppstein, David (2005), The lattice dimension of a graph, European Journal of Combinatorics, 26 (5): 585—592, arXiv:cs.DS/0402028, doi:10.1016/j.ejc.2004.05.001, MR 2127682.
17. Graham, Ronald L.; ; (1980), Ramsey Theory, Wiley-Interscience, с. 78.
18. ; (1992), Trailing the dovetail shuffle to its lair, The Annals of Applied Probability, 2 (2): 294—313, doi:10.1214/aoap/1177005705, JSTOR 2959752, MR 1161056.
19. Knuth, Donald E. (1997), The Art of Computer Programming, Volume 1: Fundamental Algorithms (вид. 3rd), Addison-Wesley Professional, ISBN , p. 11.
20. Mehlhorn, Kurt; (2008), 2.5 An example – binary search, (PDF), Springer, с. 34—36, ISBN , архів оригіналу (PDF) за 22 грудня 2016, процитовано 9 грудня 2016.
21. Roberts, Fred; Tesman, Barry (2009), (вид. 2nd), CRC Press, с. 206, ISBN , архів оригіналу за 3 травня 2016, процитовано 9 грудня 2016.
22. Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN ..
23. (2012), Example 7.4, (вид. 3rd), Cengage Learning, с. 277—278, ISBN , архів оригіналу за 10 червня 2016, процитовано 9 грудня 2016.
24. Sedgewick та Wayne, (2011), p. 186 [ 23 грудня 2016 у Wayback Machine.].
25. Cormen et al., p. 156; Goodrich & Tamassia, p. 238.
26. Cormen et al., p. 276; Goodrich & Tamassia, p. 159.
27. Cormen et al., pp. 879–880; Goodrich & Tamassia, p. 464.
28. Edmonds, Jeff (2008), , Cambridge University Press, с. 302, ISBN , архів оригіналу за 23 травня 2021, процитовано 9 грудня 2016.
29. Campbell, Murray; Greated, Clive (1994), , Oxford University Press, с. 78, ISBN , архів оригіналу за 23 грудня 2016, процитовано 9 грудня 2016.
30. , ред. (2003), (вид. 4th), The Belknap Press of Harvard University Press, с. 416, ISBN , архів оригіналу за 4 травня 2016, процитовано 9 грудня 2016.
31. Allen, Elizabeth; Triantaphillidou, Sophie (2011), , Taylor & Francis, с. 228, ISBN , архів оригіналу за 3 жовтня 2016, процитовано 9 грудня 2016.
32. Davis, Phil (1998), , CRC Press, с. 17, ISBN , архів оригіналу за 23 грудня 2016, процитовано 9 грудня 2016.
33. Allen та Triantaphillidou, (2011), p. 235 [ 13 травня 2016 у Wayback Machine.].
34. Zwerman, Susan; Okun, Jeffrey A. (2012), , CRC Press, с. 205, ISBN , архів оригіналу за 23 травня 2021, процитовано 9 грудня 2016.
35. Bauer, Craig P. (2013), , CRC Press, с. 332, ISBN , архів оригіналу за 23 травня 2021, процитовано 9 грудня 2016.

Посилання

• Weisstein, Eric W. Binary Logarithm(англ.) на сайті Wolfram MathWorld.
• Anderson, Sean Eron (12 грудня 2003), , Bit Twiddling Hacks, Stanford University, архів оригіналу за 8 січня 2020, процитовано 25 листопада 2015
• Feynman and the Connection Machine [ 4 березня 2016 у Wayback Machine.]