Двійковий логарифм Зміст Історія | Визначення і властивості | Застосування | Обчислення | Примітки | Посилання | Навігаційне менюPrecalculus mathematicsArithmetica integraThe Crest of the PeacockCryptographic Applications of Analytic Number Theory: Complexity Lower Bounds and PseudorandomnessChapter VII. De Variorum Intervallorum Receptis AppelationibusBinary logarithmsIntroduction to Mathematics for Life ScientistsExcel Scientific and Engineering Cookbook11.4 Properties of LogarithmsAlgorithmsInformation TheoryTaming the InfiniteA Programmer's Companion to Algorithm AnalysisOn the Horton–Strahler number for random tries14357322127682cs.DS/040202810.1016/j.ejc.2004.05.0012959752116105610.1214/aoap/1177005705p. 112.5 An example – binary searchApplied CombinatoricsExample 7.4p. 186How to Think About AlgorithmsThe Musician's Guide to AcousticsThe Harvard Dictionary of MusicThe Manual of PhotographyBeyond the Zone Systemp. 235Visual Effects Society Handbook: Workflow and TechniquesSecret History: The Story of CryptologyBinary LogarithmFind the log base 2 of an N-bit integer in O(lg(N)) operationsFeynman and the Connection Machine
Двійкова арифметикаЧисленняЛогарифми
математицілогарифмє оберненою функцієюстепені двійкитеорії музикиЛеонард Ейлероктавдвійковій системі численнябіттеорії інформаціїкомп’ютерних наукахдвійковому пошукукомбінаторикубіоінформатикутурнірівфотографіюматематичних функцій мови програмування Cfind first setз рухомою комоюСтепені двійкиEuclid's ElementsфакторизаціюЕвклідово-Ейлерової теоремидосконалих чиселМихаель ШтифельціліДжайнійськомуВірасена2-адичний порядокЛеонардом Ейлеромобернену функціюстепені двійкидійсних чиселнатуральним логарифмомкомплексного логарифмукомплексних чиселбітдвійковому представленніцілій частинівласної інформаціїінформаційна ентропіянатуральний логарифмнаттеорія чиселматематичний аналізкомбінаториціаналізі алгоритмівалгоритмівструктур данихдвійковому пошукудерево двійкового пошукунотації Ландаулінійно-логарифмічнимитеорії музикиінтервалраціональних чиселоктавамузичного строюцентупівтонівМіліоктавафотографіїзначення експозиціїзакону Вебера-Фехнераf-число діафрагмиапертуруденситометріїдинамічний діапазонкалькуляторінатуральний логарифмзвичайний логарифмінженерних калькуляторахформулазміна основи логарифму
Двійковий логарифм
Перейти до навігації
Перейти до пошуку
Графік log2x як функції додатних дійсних чисел x
В математиці, двійковий логарифм (log2n) це степінь, до якої треба піднести число 2, щоб отримати значення n. І це, для будь-якого дійсного числа x,
- x=log2n⟺2x=n.displaystyle x=log _2nquad Longleftrightarrow quad 2^x=n.
Наприклад, двійковий логарифм числа 1 є 0, двійковий логарифм від 2 є 1, двійковий логарифм від 4 дорівнює 2, а двійковий логарифм від 32 це 5.
Бінарний логарифм це логарифм за основою 2. Функція двійкового логарифму є є оберненою функцією функції степені двійки. Разом із звичайним позначенням log2, існують альтернативні позначення бінарного логарифму такі як: lg, ld, lb, і (із попереднім узгодженням, що за умовчанням основою позначеного так логарифму є 2) log.
Історично, перше застосування двійковий логарифм знайшло в теорії музики, його використав Леонард Ейлер: двійковий логарифм відношення частот двох музичних тонів дає розрахувати кількість октав, на які відрізняються ці тони. Двійковий логарифм можна застосувати для розрахунку довжини представлення числа в двійковій системі числення, або кількість біт, необхідних аби закодувати повідомлення в теорії інформації. В комп’ютерних науках, вони використовуються для підрахунку кількості кроків, які треба здійснити при двійковому пошуку і подібних алгоритмах. Інші області, в яких часто використовується двійковий логарифм, це: комбінаторику, біоінформатику, планування спортивних турнірів, і фотографію.
Бінарні логарифми включено до стандартних математичних функцій мови програмування C і до інших математичних програмних пакетів.
Цілу частину двійкового логарифму можна знайти здійснивши операцію find first set над цілим числом, або шляхом пошуку експоненти значення з рухомою комою.
Зміст
1 Історія
2 Визначення і властивості
3 Застосування
3.1 Теорія інформації
3.2 Комбінаторика
3.3 Обчислювальна складність
3.4 Теорія музики
3.5 Фотографія
4 Обчислення
4.1 Перетворення із інших основ
5 Примітки
6 Посилання
Історія |
Леонард Ейлер був першим, хто застосував двійкові логарифми в теорії музики, у 1739.
Степені двійки були відомі і використовувались ще з античних часів; наприклад вони присутні в Euclid's Elements, Книга IX.32 (про факторизацію степенів двійки) і IX.36 (в частині Евклідово-Ейлерової теореми, про структуру парних досконалих чисел).
А двійковий логарифм степені двійки позначав позицію в впорядкованій послідовності степенів двійки.
На основі цього, Михаель Штифель створив і опублікував першу відому таблицю двійкових логарифмів в 1544. Його книга Arthmetica Integra містила декілька таблиць, які впорядковували цілі числа із відповідними їхніми степенями двійки. Якщо розвернути навпаки рядки цих таблиць їх можна інтерпретувати як таблиці двійкових логарифмів.[1][2]
Раніше за Штифеля, у 8-му столітті Джайнійському математику Вірасена створив попередника двійкового логарифма. Концепція Вірасена, що називалася ardhacheda визначалася як кількість разів, при яких задане число можна поділити порівну на два. Це визначення приводить до функції, яка за змістом співпадає з двійковим логарифмом за основою два,[3] але відрізняється для інших цілих, і дає 2-адичний порядок, а не логарифм.[4]
Сучасна форма двійкового логарифму, що застосовується до будь-якого числа (не лише степені двійки) була в явному вигляді розглянута Леонардом Ейлером в 1739. Ейлер започаткував використання двійкових логарифмів в теорії музики, задовго до їхнього більш значимого використання в теорії інформації і комп’ютерних науках. Як частину своєї роботи в цій сфері, Ейлер опублікував таблицю логарифмів для цілих чисел від 1 до 8, з точністю до сьомого десяткового знаку точності.[5][6]
Визначення і властивості |
Функцію двійкового логарифму можна визначити як обернену функцію від функції степені двійки, що строго зростає в області додатних дійсних чисел і таким чином має одну єдину зворотню функцію.[7]
Альтернативним шляхом, її можна визначити як ln n/ln 2, де ln є натуральним логарифмом, визначений одним із своїх стандартних способів. Використання комплексного логарифму в такому визначення дозволяє розширити застосування двійкового логарифму для комплексних чисел.[8]
Як і для інших логарифмів, двійковий логарифм задовольняє наступним рівнянням, які можуть використовуватись для спрощення формул, які поєднують двійкові логарифми із множенням або зведенням в ступінь:[9]
- log2xy=log2x+log2ydisplaystyle log _2xy=log _2x+log _2y
- log2xy=log2x−log2ydisplaystyle log _2frac xy=log _2x-log _2y
- log2xy=ylog2x.displaystyle log _2x^y=ylog _2x.
Застосування |
Теорія інформації |
Кількість розрядів (біт) в двійковому представленні додатного цілого n дорівнюватиме цілій частині числа 1 + log2n.[10]
- ⌊log2n⌋+1.displaystyle lfloor log _2nrfloor +1.,
В теорії інформації, визначення кількості власної інформації та інформаційна ентропія часто задаються за допомогою двійкового логарифму, тим самим представляючи біт як фундаментальну одиницю інформації. Однак, в альтернативних представленнях цих визначень також використовують натуральний логарифм і нат.[11]
Комбінаторика |
Хоча натуральний логарифм є більш важливим ніж двійковий логарифм для багатьох галузей чистої математики, таких як теорія чисел і математичний аналіз,[12] двійковий логарифм має ряд застосувань в комбінаториці:
- Кожне двійкове дерево кожне n листя має висоту принаймні в log2n, і стає рівним цьому значенню, коли n є степенем двійки, а саме дерево є повним двійковим деревом.[13] Відповідно, число Стрехлера річкової системи із n притоками буде щонайбільше дорівнювати log2n + 1.[14]
- Кожне сімейство множин з n різними наборами має принаймні log2n елементів в купі, і буде рівністю коли це сімейство становить булеан.[15]
- Кожен частковий куб із n вершинами має ізометричну розмірність щонайменше в log2n, і має не більше ніж 12 n log2n ребер, при чому рівність буде, якщо частковий куб є графом гіперкубу.[16]
- Відповідно до Теореми Рамсея, кожний неорієнтований граф з n-вершин має або кліку або незалежну множину з розміром в логарифмічній залежності із n. Точний розмір гарантовано не відомий, але найкраща відома межа цього розміру застосовує двійковий логарифм. Зокрема, всі графи мають кліку або незалежну множину розміром принаймні в 12 log2n (1 − o(1)) і майже всі графи не мають кліки або незалежної множини більшого розміру ніж 2 log2n (1 + o(1)).[17]
- Із теорії математичного аналізу модель Гільберта-Шеннона-Рідса для випадкового тасування кар, можна визначити число разів необхідних при тасуванні колоди з n-карт, використовуючи метод riffle shuffle[en], аби отримати кількість перестановок, що будуть близкі до рівномірного розподілу, і це значення приблизно дорівнює 32 log2n. Цей підрахунок дав основу для рекомендації, що колода з 52-карт повинна перемішуватись сім разів.[18]
Обчислювальна складність |
Двійковий пошук в відсортованому масиві, часова складність алгоритму розраховується за допомогою двійкових логарифмів
Двійковий логарифм також часто фігурує в аналізі алгоритмів, не тільки через часте використання двійкової арифметики в алгоритмах, а й тому, що двійкові логарифми зустрічаються при аналізі алгоритмів, заснованих на двонаправлених розгалуженнях.[19] Якщо задача початково має n варіантів шляху вирішення, а кожна ітерація алгоритму зменшує кількість варіантів в два рази, тоді кількість ітерацій, необхідних аби завершити пошук на одному з варіантів знову таки є цілою частиною від log2n. Цей підхід використовується при аналізі багатьох алгоритмів і структур даних. Наприклад, при двійковому пошуку, об’єм задачі, що розв’язується змешнується навпіл при кожній ітерації, і таким чином приблизно log2n ітерацій необхідно здійснити або отримати задачу розміром 1, що означає, що задачу можна вирішити за скінченний передбачений час.[20] Аналогічно, ідеально збалансоване дерево двійкового пошуку, яке містить n елементів має висоту log2(n + 1) − 1.[21]
Час роботи алгоритму зазвичай виражають в нотації Ландау (велике О), яка використовується для спрощення виразів не указуючи постійних складових і членів нижчого порядку. Оскільки логарифми з різними основами відрізняються один від одного лише на сталу величину, про алгоритми, які виконуються за час O(log2n) також можна казати, що вони виконуються за O(log13n) часу. Основу логарифму в виразах такого вигляду як O(log n) або O(n log n) можна не вказувати.[22][23] Однак, якщо логарифм вказується в показнику степеня при розрахунку часу, основою логарифму не можна нехтувати і треба вказувати. Наприклад, O(2log2n) не те саме, що O(2ln n) оскільки останнє буде дорівнювати O(n) а перший вираз - O(n0.6931...).
Алгоритми з часом виконання O(n log n) іноді називають лінійно-логарифмічними.[24] Прикладами алгоритмів із часом виконання O(log n) або O(n log n) є:
Швидке сортування і інші алгоритми сортування порівняннями[25]- Пошук в збалансованому двійковому дереві пошуку[26]
Швидке піднесення до степеня[27]
Задача пошуку найбільшої зростаючої підпослідовності[28]
Теорія музики |
В теорії музики, інтервал або різниця сприйняття між двома тонами визначається відношенням їх частот. Інтервали, що утворені за допомогою співвідношення раціональних чисел із малими чисельниками і знаменниками сприймаються особливо милозвучно. Найпростішим і найважливішим із таких інтервалів є октава, що має співвідношення частот 2:1. Кількість октав, на які відрізняються звукові тони дорівнюють двійковому логарифму від співвідношення їх частот.[29]
При вивченні музичного строю і інших аспектів музичної теорії, які потребують кращого розрізнення між тонами, ж зручним мати міру розміру інтервалу меншу за октаву із властивістю адитивності (чим є логарифми), а не мультиплікативності (яким є співвідношення частот). Таким чином, якщо тони x, y, і z утворюють зростаючу послідовність тонів, то міра інтервалу від x до y плюс міра інтервалу від y до z повинні дорівнювати мірі інтервалу від x до z. Така міра задається за допомогою центу, який поділяє октаву на 1200 рівних інтервалів (12 півтонів, що містять 100 центів кожен). Математично, якщо дані тони із частотами f1 і f2, кількість центів в інтервалі від f1 до f2 становитиме [29]
- |1200log2f1f2|.displaystyle left
Міліоктава визначається тим самим способом, але матиме множник 1000 замість 1200.[30]
Фотографія |
У фотографії, значення експозиції вимірюється як двійковий логарифм від кількості світла, яке досягає плівки або сенсору зображення, у відповідності до закону Вебера-Фехнера, який описує логарифмічний характер сприйняття світла зоровою системою людини. Один крок зміни експозиції є однією одиницею логарифмічної шкали за основою-2.[31][32] Більш точно, значення експозиції фотографії визначається як
- log2N2tdisplaystyle log _2frac N^2t
де N це f-число діафрагми, яке вимірює апертуру лінзи під час експозиції, а t це тривалість експозиції в секундах.[33]
Двійкові логарифми також використовуються в денситометрії, щоб оцінити динамічний діапазон світлочутливого матеріалу або цифрового сенсора.[34]
Обчислення |
Інженерний калькулятор TI SR-50 (1974). Кнопки ln і log знаходяться в другому рядку; немає кнопки log2.
Перетворення із інших основ |
Простим способом розрахувати значення log2n на калькуляторі, який не має функції log2, це використати натуральний логарифм (ln), звичайний логарифм (log або log10), які можна знайти в багатьох інженерних калькуляторах. Для цього існує формула зміна основи логарифму:[32][35]
- log2n=lnnln2=log10nlog102,displaystyle log _2n=frac ln nln 2=frac log _10nlog _102,
або наближено
- log2n≈1.442695lnn≈3.321928log10n.displaystyle log _2napprox 1.442695ln napprox 3.321928log _10n.
Примітки |
↑
Groza, Vivian Shaw; Shelley, Susanne M. (1972). Precalculus mathematics. New York: Holt, Rinehart and Winston. с. 182. ISBN 978-0-03-077670-0. .
↑ Stifel, Michael (1544). Arithmetica integra (Latin). с. 31. . Копія тієї самої таблиці з двома додатковими записами згадується на с. 237, і інша копія розширена до від’ємних значень знаходиться на с. 249b.
↑ Joseph, G. G. (2011). The Crest of the Peacock (вид. 3rd). Princeton University Press. с. 352. .
↑ See, e.g., Shparlinski, Igor (2013). Cryptographic Applications of Analytic Number Theory: Complexity Lower Bounds and Pseudorandomness. Progress in Computer Science and Applied Logic 22. Birkhäuser. с. 35. ISBN 978-3-0348-8037-4. .
↑ Euler, Leonhard (1739). Chapter VII. De Variorum Intervallorum Receptis Appelationibus. Tentamen novae theoriae musicae ex certissismis harmoniae principiis dilucide expositae (Latin). Saint Petersburg Academy. с. 102–112. .
↑ Tegg, Thomas (1829). Binary logarithms. London encyclopaedia; or, Universal dictionary of science, art, literature and practical mechanics: comprising a popular view of the present state of knowledge, Volume 4. с. 142–143. .
↑ Batschelet, E. (2012). Introduction to Mathematics for Life Scientists. Springer. с. 128. ISBN 978-3-642-96080-2. .
↑ Наприклад, Microsoft Excel надає функціюIMLOG2для комплексних двійкових логарифмів: див. Bourg, David M. (2006). Excel Scientific and Engineering Cookbook. O'Reilly Media. с. 232. ISBN 978-0-596-55317-3. .
↑ Kolman, Bernard; Shapiro, Arnold (1982). 11.4 Properties of Logarithms. Algebra for College Students. Academic Press. с. 334–335. ISBN 978-1-4832-7121-7. .
↑ Sedgewick, Robert; Wayne, Kevin Daniel (2011). Algorithms. Addison-Wesley Professional. с. 185. ISBN 978-0-321-57351-3. .
↑ Van der Lubbe, Jan C. A. (1997). Information Theory. Cambridge University Press. с. 3. ISBN 978-0-521-46760-5. .
↑ Stewart, Ian (2015). Taming the Infinite. Quercus. с. 120. ISBN 9781623654733. «in advanced mathematics and science the only logarithm of importance is the natural logarithm» .
↑ Leiss, Ernst L. (2006). A Programmer's Companion to Algorithm Analysis. CRC Press. с. 28. ISBN 978-1-4200-1170-8. .
↑ Devroye, L.; Kruszewski, P. (1996). On the Horton–Strahler number for random tries. RAIRO Informatique Théorique et Applications 30 (5): 443–456. MR 1435732. .
↑ Equivalently, a family with k distinct elements has at most 2k distinct sets, with equality when it is a power set.
↑ Eppstein, David (2005). The lattice dimension of a graph. European Journal of Combinatorics 26 (5): 585–592. MR 2127682. arXiv:cs.DS/0402028. doi:10.1016/j.ejc.2004.05.001. .
↑ Graham, Ronald L.; Rothschild, Bruce L.; Spencer, Joel H. (1980). Ramsey Theory. Wiley-Interscience. с. 78. .
↑ Bayer, Dave; Diaconis, Persi (1992). Trailing the dovetail shuffle to its lair. The Annals of Applied Probability 2 (2): 294–313. JSTOR 2959752. MR 1161056. doi:10.1214/aoap/1177005705. .
↑ Knuth, Donald E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms (вид. 3rd). Addison-Wesley Professional. ISBN 978-0-321-63574-7. , p. 11.
↑ Mehlhorn, Kurt; Sanders, Peter (2008). 2.5 An example – binary search. Algorithms and Data Structures: The Basic Toolbox. Springer. с. 34–36. ISBN 978-3-540-77977-3. .
↑ Roberts, Fred; Tesman, Barry (2009). Applied Combinatorics (вид. 2nd). CRC Press. с. 206. ISBN 978-1-4200-9983-6. .
↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms (вид. 2nd). MIT Press and McGraw-Hill. с. 34, 53–54. ISBN 0-262-03293-7. .
↑ Sipser, Michael (2012). Example 7.4. Introduction to the Theory of Computation (вид. 3rd). Cengage Learning. с. 277–278. ISBN 9781133187790. .
↑ Sedgewick та Wayne, (2011), p. 186.
↑ Cormen et al., p. 156; Goodrich & Tamassia, p. 238.
↑ Cormen et al., p. 276; Goodrich & Tamassia, p. 159.
↑ Cormen et al., pp. 879–880; Goodrich & Tamassia, p. 464.
↑ Edmonds, Jeff (2008). How to Think About Algorithms. Cambridge University Press. с. 302. ISBN 978-1-139-47175-6. .
↑ аб Campbell, Murray; Greated, Clive (1994). The Musician's Guide to Acoustics. Oxford University Press. с. 78. ISBN 978-0-19-159167-9. .
↑ Randel, Don Michael, ред. (2003). The Harvard Dictionary of Music (вид. 4th). The Belknap Press of Harvard University Press. с. 416. ISBN 978-0-674-01163-2. .
↑ Allen, Elizabeth; Triantaphillidou, Sophie (2011). The Manual of Photography. Taylor & Francis. с. 228. ISBN 978-0-240-52037-7. .
↑ аб Davis, Phil (1998). Beyond the Zone System. CRC Press. с. 17. ISBN 978-1-136-09294-7. .
↑ Allen та Triantaphillidou, (2011), p. 235.
↑ Zwerman, Susan; Okun, Jeffrey A. (2012). Visual Effects Society Handbook: Workflow and Techniques. CRC Press. с. 205. ISBN 978-1-136-13614-6. .
↑ Bauer, Craig P. (2013). Secret History: The Story of Cryptology. CRC Press. с. 332. ISBN 978-1-4665-6186-1. .
Посилання |
Weisstein, Eric W. Binary Logarithm(англ.) на сайті Wolfram MathWorld.
Anderson, Sean Eron (December 12, 2003). Find the log base 2 of an N-bit integer in O(lg(N)) operations. Bit Twiddling Hacks (Stanford University). Процитовано 2015-11-25.- Feynman and the Connection Machine
Категорії:
- Двійкова арифметика
- Числення
- Логарифми
(RLQ=window.RLQ||[]).push(function()mw.config.set("wgPageParseReport":"limitreport":"cputime":"0.280","walltime":"0.354","ppvisitednodes":"value":3097,"limit":1000000,"ppgeneratednodes":"value":0,"limit":1500000,"postexpandincludesize":"value":89623,"limit":2097152,"templateargumentsize":"value":2027,"limit":2097152,"expansiondepth":"value":6,"limit":40,"expensivefunctioncount":"value":1,"limit":500,"unstrip-depth":"value":0,"limit":20,"unstrip-size":"value":42902,"limit":5000000,"entityaccesscount":"value":0,"limit":400,"timingprofile":["100.00% 228.471 1 -total"," 51.47% 117.601 1 Шаблон:Reflist"," 28.06% 64.103 30 Шаблон:Citation"," 14.53% 33.203 1 Шаблон:Main"," 12.60% 28.787 1 Шаблон:Str_find"," 7.24% 16.542 60 Шаблон:Math"," 4.99% 11.407 1 Шаблон:Mathworld"," 4.36% 9.951 2 Шаблон:Harvtxt"," 3.77% 8.608 1 Шаблон:Iw"," 3.19% 7.297 2 Шаблон:Harvard_citation/core"],"scribunto":"limitreport-timeusage":"value":"0.047","limit":"10.000","limitreport-memusage":"value":2298857,"limit":52428800,"cachereport":"origin":"mw1304","timestamp":"20190603215548","ttl":2592000,"transientcontent":false););"@context":"https://schema.org","@type":"Article","name":"u0414u0432u0456u0439u043au043eu0432u0438u0439 u043bu043eu0433u0430u0440u0438u0444u043c","url":"https://uk.wikipedia.org/wiki/%D0%94%D0%B2%D1%96%D0%B9%D0%BA%D0%BE%D0%B2%D0%B8%D0%B9_%D0%BB%D0%BE%D0%B3%D0%B0%D1%80%D0%B8%D1%84%D0%BC","sameAs":"http://www.wikidata.org/entity/Q581168","mainEntity":"http://www.wikidata.org/entity/Q581168","author":"@type":"Organization","name":"u0423u0447u0430u0441u043du0438u043au0438 u043fu0440u043eu0435u043au0442u0456u0432 u0412u0456u043au0456u043cu0435u0434u0456u0430","publisher":"@type":"Organization","name":"u0424u043eu043du0434 u0412u0456u043au0456u043cu0435u0434u0456u0430","logo":"@type":"ImageObject","url":"https://www.wikimedia.org/static/images/wmf-hor-googpub.png","datePublished":"2016-12-08T18:19:52Z","dateModified":"2019-04-23T08:22:14Z","image":"https://upload.wikimedia.org/wikipedia/commons/1/17/Binary_logarithm_plot_with_ticks.svg"(RLQ=window.RLQ||[]).push(function()mw.config.set("wgBackendResponseTime":159,"wgHostname":"mw1255"););
