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

Графік Шаблон:Math як функції додатних дійсних чисел Шаблон:Mvar

В математиці, двійковий логарифм (Шаблон:Math) — це степінь, до якого треба піднести число Шаблон:Math, щоб отримати значення Шаблон:Mvar. Тобто, для будь-якого дійсного числа Шаблон:Mvar, виконується еквівалентність

$x={\log }_{2}n⟺2^x=n.$

Наприклад, двійковий логарифм числа Шаблон:Math дорівнює Шаблон:Math, двійковий логарифм числа Шаблон:Math — Шаблон:Math, двійковий логарифм числа Шаблон:Math дорівнює Шаблон:Math, а двійковий логарифм числа Шаблон:Math — Шаблон:Math.

Означення та позначення

Бінарний логарифм — це логарифм за основою Шаблон:Math. Функція двійкового логарифма є оберненою функцією до функції степеня двійки. Окрім стандартного позначення Шаблон:Math, використовуються альтернативні позначення, такі як Шаблон:Math, Шаблон:Math, Шаблон:Math та Шаблон:Math (за попередньої домовленості, що основою є 2).

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

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

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

Історія

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

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

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

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

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

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

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

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

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

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

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

Застосування

Теорія інформації

Кількість розрядів (біт) в двійковому представленні додатного цілого Шаблон:Mvar дорівнюватиме цілій частині числа Шаблон:Math.

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

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

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

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

• Кожне двійкове дерево кожне Шаблон:Mvar листя має висоту принаймні в Шаблон:Math, і стає рівним цьому значенню, коли Шаблон:Mvar є степенем двійки, а саме дерево є повним двійковим деревом. Відповідно, число Стрехлера річкової системи із Шаблон:Mvar притоками буде щонайбільше дорівнювати Шаблон:Math.
• Кожне сімейство множин з Шаблон:Mvar різними наборами має принаймні Шаблон:Math елементів в купі, і буде рівністю коли це сімейство становить булеан.
• Кожен частковий куб із Шаблон:Mvar вершинами має ізометричну розмірність щонайменше в Шаблон:Math, і має не більше ніж Шаблон:Math ребер, при чому рівність буде, якщо частковий куб є графом гіперкуба.
• Відповідно до Теореми Рамсея, кожний неорієнтований граф з Шаблон:Mvar-вершин має або кліку або незалежну множину з розміром в логарифмічній залежності із Шаблон:Mvar. Точний розмір гарантовано не відомий, але найкраща відома межа цього розміру застосовує двійковий логарифм. Зокрема, всі графи мають кліку або незалежну множину розміром принаймні в Шаблон:Math і майже всі графи не мають кліки або незалежної множини більшого розміру ніж Шаблон:Math.
• Із теорії математичного аналізу Шаблон:Iw для випадкового тасування кар, можна визначити число разів необхідних при тасуванні колоди з Шаблон:Mvar-карт, використовуючи метод каскадного тасування, аби отримати кількість перестановок, що будуть близкі до рівномірного розподілу, і це значення приблизно дорівнює Шаблон:Math. Цей підрахунок дав основу для рекомендації, що колода з 52-карт повинна перемішуватись сім разів.

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

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

Двійковий логарифм також часто фігурує в аналізі алгоритмів, не тільки через часте використання двійкової арифметики в алгоритмах, а й тому, що двійкові логарифми зустрічаються при аналізі алгоритмів, заснованих на двонаправлених розгалуженнях. Якщо задача початково має Шаблон:Mvar варіантів шляху вирішення, а кожна ітерація алгоритму зменшує кількість варіантів в два рази, тоді кількість ітерацій, необхідних аби завершити пошук на одному з варіантів знову таки є цілою частиною від Шаблон:Math. Цей підхід використовується при аналізі багатьох алгоритмів і структур даних. Наприклад, при двійковому пошуку, об'єм задачі, що розв'язується змешнується навпіл при кожній ітерації, і таким чином приблизно Шаблон:Math ітерацій необхідно здійснити або отримати задачу розміром Шаблон:Math, що означає, що задачу можна вирішити за скінченний передбачений час. Аналогічно, ідеально збалансоване дерево двійкового пошуку, яке містить Шаблон:Mvar елементів має висоту Шаблон:Math.

Час роботи алгоритму зазвичай виражають в нотації Ландау (велике О), яка використовується для спрощення виразів не указуючи постійних складових і членів нижчого порядку. Оскільки логарифми з різними основами відрізняються один від одного лише на сталу величину, про алгоритми, які виконуються за час Шаблон:Math також можна казати, що вони виконуються за Шаблон:Math часу. Основу логарифма у виразах такого вигляду як Шаблон:Math або Шаблон:Math можна не вказувати. Однак, якщо логарифм вказується в показнику степеня при розрахунку часу, основою логарифма не можна нехтувати і треба вказувати. Наприклад, Шаблон:Math не те саме, що Шаблон:Math оскільки останнє буде дорівнювати Шаблон:Math а перший вираз — Шаблон:Math.

Алгоритми з часом виконання Шаблон:Math іноді називають Шаблон:Iw. Прикладами алгоритмів із часом виконання Шаблон:Math або Шаблон:Math є:

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

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

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

При вивченні музичного строю і інших аспектів музичної теорії, які потребують кращого розрізнення між тонами, ж зручним мати міру розміру інтервалу меншу за октаву із властивістю адитивності (чим є логарифми), а не мультиплікативності (яким є співвідношення частот). Таким чином, якщо тони Шаблон:Mvar, Шаблон:Mvar, і Шаблон:Mvar утворюють зростаючу послідовність тонів, то міра інтервалу від Шаблон:Mvar до Шаблон:Mvar плюс міра інтервалу від Шаблон:Mvar до Шаблон:Mvar повинні дорівнювати мірі інтервалу від Шаблон:Mvar до Шаблон:Mvar. Така міра задається за допомогою центу, який поділяє октаву на Шаблон:Math рівних інтервалів (Шаблон:Math півтонів, що містять Шаблон:Math центів кожен). Математично, якщо дані тони із частотами Шаблон:Math і Шаблон:Math, кількість центів в інтервалі від Шаблон:Math до Шаблон:Math становитиме

$\left|1200{\log }_2\frac{f_1}{f_2}\right|.$

Шаблон:Iw визначається тим самим способом, але матиме множник Шаблон:Math замість Шаблон:Math.

Фотографія

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

${\log }_2\frac{N^2}{t}$

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

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

Обчислення

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

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

Простим способом розрахувати значення Шаблон:Math на калькуляторі, який не має функції Шаблон:Math, це використати натуральний логарифм (Шаблон:Math), звичайний логарифм (Шаблон:Math або Шаблон:Math), які можна знайти в багатьох Шаблон:Iw. Для цього існує формула зміна основи логарифма:

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

або наближено

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

Посилання

• Шаблон:Mathworld
• Шаблон:Citation
• Feynman and the Connection Machine Шаблон:Webarchive