Просмотр кода страницы Двоичный логарифм

[[Файл:Binary logarithm plot with ticks.svg|right|thumb|300px|<center>График двоичного логарифма</center>]]
'''Двоичный логарифм''' — [[логарифм]] по основанию 2. Другими словами, двоичный логарифм числа <math>b</math> есть решение уравнения <math>2^x=b.</math>

Двоичный логарифм [[Вещественное число|вещественного числа]] <math>b</math> существует, если <math>b>0.</math> Согласно стандарту [[ISO 31-11]], он обозначается<ref>Иногда, особенно в немецких изданиях, двоичный логарифм обозначается <math>\operatorname{ld} b</math> (от {{lang-lat|logarithmus dyadis}}), см. {{книга |заглавие=Origins and Foundations of Computing: In Cooperation with Heinz Nixdorf MuseumsForum |издательство=[[Springer Science+Business Media|Springer Science & Business Media]] |год=2009 |isbn=978-3-642-02991-2 |страницы=54 |ссылка=https://books.google.com/books?id=y4uTaLiN-wQC&pg=PA54 |ref=Bauer |язык=en |автор=Bauer, Friedrich L.}}</ref> <math>\operatorname{lb} b,</math> <math>\operatorname{lb} (b)</math> или <math>\log_2 b</math>. Примеры:
: <math>\operatorname{lb} 1=0;\, \operatorname{lb} 2=1;\, \operatorname{lb} 16=4</math>
: <math>\operatorname{lb} 0{,}5=-1;\, \operatorname{lb} \frac{1}{256}=-8</math>

== История ==
Исторически двоичные логарифмы нашли своё первое применение в [[Теория музыки|теории музыки]], когда [[Леонард Эйлер]] установил: двоичный логарифм отношения частот двух [[Высота звука|музыкальных тонов]] равен количеству [[Октава|октав]], которое отделяет один тон от другого.  Эйлер также опубликовал таблицу двоичных логарифмов целых чисел от 1 до 8 с точностью до семи десятичных знаков<ref>{{citation |last = Euler |first = Leonhard |contribution = Chapter VII. De Variorum Intervallorum Receptis Appelationibus |language = Latin |pages = 102—112 |publisher = Saint Petersburg Academy |title = Tentamen novae theoriae musicae ex certissismis harmoniae principiis dilucide expositae |url = http://eulerarchive.maa.org/pages/E033.html |year = 1739 |access-date = 2019-08-06 |archive-date = 2018-10-11 |archive-url = https://web.archive.org/web/20181011023106/http://eulerarchive.maa.org/pages/E033.html |url-status = live }} {{Cite web |url=http://eulerarchive.maa.org/pages/E033.html |title=Источник |access-date=2019-08-06 |archive-date=2018-10-11 |archive-url=https://web.archive.org/web/20181011023106/http://eulerarchive.maa.org/pages/E033.html |deadlink=unfit }}.</ref><ref>{{citation|title=London encyclopaedia; or, Universal dictionary of science, art, literature and practical mechanics: comprising a popular view of the present state of knowledge, Volume 4|first=Thomas|last=Tegg|year=1829|contribution=Binary logarithms|pages=142–143|url=https://books.google.com/books?id=E-ZTAAAAYAAJ&pg=PA142}} {{Cite web |url=https://books.google.com/books?id=E-ZTAAAAYAAJ&pg=PA142 |title=Источник |access-date=2019-08-06 |archive-date=2021-05-23 |archive-url=https://web.archive.org/web/20210523051211/https://books.google.com/books?id=E-ZTAAAAYAAJ&pg=PA142 |deadlink=unfit }}.</ref>.

С созданием [[информатика|информатики]] выяснилось, что двоичные логарифмы необходимы для определения количества [[бит]]ов, требующихся для [[Кодирование информации|кодирования сообщения]]. Другие области, в которых часто используется двоичный логарифм, включают [[Комбинаторика|комбинаторику]], [[Биоинформатика|биоинформатику]], [[Криптография|криптографию]], проведение спортивных турниров и [[Фотография|фотографию]]. Стандартная функция для вычисления двоичного логарифма предусмотрена во многих распространённых системах программирования.

== Алгебраические свойства ==
В нижеследующей таблице предполагается, что все значения положительны{{sfn |Выгодский М. Я. Справочник по элементарной математике|1978|с=187. }}:
<center>
{| class="wikitable"
|-
!  !! Формула !! Пример
|-
| Произведение || <cite id=labelLogarithmProducts><math> \operatorname{lb}(x y) = \operatorname{lb} (x) + \operatorname{lb} (y)</math></cite>|| <math> \operatorname{lb} (256) = \operatorname{lb}(16 \cdot 16) = \operatorname{lb} (16) + \operatorname{lb} (16) = 4 + 4 = 8</math>
|-
| Частное от деления || <math>\operatorname{lb} \!\left(\frac x y \right) = \operatorname{lb} (x) - \operatorname{lb} (y)</math>|| <math> \operatorname{lb} \left(\frac{1}{32}\right) = \operatorname{lb} (1) - \operatorname{lb} (32) = 0 - 5 = -5</math>
|-
| Степень || <cite id=labelLogarithmPowers><math>\operatorname{lb}(x^p) = p \operatorname{lb} (x)</math></cite>|| <math> \operatorname{lb} (1024) = \operatorname{lb} (2^{10}) = 10 \operatorname{lb} (2) = 10</math>
|-
| Корень || <math>\operatorname{lb} \sqrt[p]{x} = \frac {\operatorname{lb} (x)} p</math>|| <math> \operatorname{lb} \sqrt{8} = \frac{1}{2}\operatorname{lb} 8 = \frac{3}{2} = 1{,}5 </math>
|}
</center>
Существует очевидное обобщение приведенных формул на случай, когда допускаются отрицательные переменные, например:
: <math>\operatorname{lb} |x y| = \operatorname{lb} (|x|) + \operatorname{lb} (|y|),</math>
: <math>\operatorname{lb} \!\left|\frac x y \right| = \operatorname{lb} (|x|) - \operatorname{lb} (|y|),</math>
Формула для логарифма произведения без труда обобщается на произвольное количество сомножителей:
: <math> \operatorname{lb}(x_1 x_2 \dots x_n) = \operatorname{lb} (x_1) + \operatorname{lb} (x_2) + \dots + \operatorname{lb} (x_n)</math>

Связь двоичного, [[Натуральный логарифм|натурального]] и [[Десятичный логарифм|десятичного]] логарифмов:
: <math>\operatorname{lb} x \approx 1{,}442695 \ln x</math>
: <math>\operatorname{lb} x \approx 3{,}321928 \lg x</math>

== Функция двоичного логарифма ==
Если рассматривать логарифмируемое число как переменную, мы получим функцию двоичного логарифма:  <math>y = \operatorname{lb} x</math>. Она определена при всех <math>x>0,</math> область значений: <math>E(y)=(-\infty; + \infty )</math>. График этой функции часто называется ''логарифмикой'', она [[Обратная функция|обратна]] для функции <math>y=2^x</math>. Функция [[Монотонная функция|монотонно]] возрастает, [[Непрерывное отображение|непрерывна]] и [[Дифференцируемая функция|дифференцируема]] всюду, где она определена. [[Производная функции|Производная]] для неё даётся формулой<ref name=MATENC>{{книга |часть=Логарифмическая функция. |заглавие=Математическая энциклопедия (в 5 томах) |место=М. |год=1982 |том=3 |ссылка=http://eqworld.ipmnet.ru/ru/library/books/Vinogradov_MatEnc_t3.djvu |издательство=[[Большая Российская энциклопедия (издательство)|Советская Энциклопедия]] |archivedate=2013-10-16 |archiveurl=https://web.archive.org/web/20131016140955/http://eqworld.ipmnet.ru/ru/library/books/Vinogradov_MatEnc_t3.djvu }}</ref>:
: <math>\frac {d} {dx} \operatorname{lb}  x = \frac {\operatorname{lb}  e} {x}</math>

[[Ось ординат]] <math>(x=0)</math> является [[Асимптота|вертикальной асимптотой]], поскольку:
: <math>\lim_{x \to 0+0} \operatorname{lb}  x = - \infty</math>

== Применение ==

=== Теория информации ===
Двоичный логарифм [[Натуральное число|натурального числа]] <math>N</math> позволяет определить число цифр <math>b(N)</math> во внутреннем компьютерном ([[бит]]овом) представлении этого числа:
:  <math>b(N) = \lfloor \operatorname{lb} N \rfloor + 1</math> (скобки  обозначают [[Целая часть|целую часть]] числа)
[[Информационная энтропия]] — мера [[Количество информации|количества информации]], также основана на двоичном логарифме

=== Сложность рекурсивных алгоритмов ===
Оценка [[Вычислительная сложность|асимптотической сложности]] [[Рекурсивный алгоритм|рекурсивных алгоритмов]], основанных на принципе «[[Разделяй и властвуй (информатика)|разделяй и властвуй]]»<ref>{{книга|автор=Harel, David; Feldman, Yishai A.|заглавие=Algorithmics: the spirit of computing|ссылка=https://archive.org/details/algorithmicsspir00hare_065|место=New York|издательство=Addison-Wesley|год=2004|pages=[https://archive.org/details/algorithmicsspir00hare_065/page/143 143]|isbn=978-0-321-11784-7}}</ref> — таких, как [[быстрая сортировка]], [[быстрое преобразование Фурье]], [[двоичный поиск]] {{итп}}

=== Комбинаторика ===
Если [[двоичное дерево]] содержит <math>n</math> узлов, то его высота не меньше, чем <math>\log_2 n</math> (равенство достигается, если <math>n</math> является степенью 2)<ref>{{citation |last=Leiss |first=Ernst L. |isbn=978-1-4200-1170-8 |page=28 |publisher=CRC Press |title=A Programmer's Companion to Algorithm Analysis |url=https://books.google.com/books?id=E6BNGFQ6m_IC&pg=RA2-PA28 |year=2006 }} {{Cite web |url=https://books.google.com/books?id=E6BNGFQ6m_IC&pg=RA2-PA28 |title=Источник |access-date=2019-08-06 |archive-date=2020-08-12 |archive-url=https://web.archive.org/web/20200812191211/https://books.google.com/books?id=E6BNGFQ6m_IC&pg=RA2-PA28 |deadlink=unfit }}</ref>. Соответственно, [[число Стралера — Философова]] для речной системы с <math>n</math> притоками не превышает<ref>{{citation |last1=Devroye |first1=L. |last2=Kruszewski |first2=P. |issue=5 |journal=RAIRO Informatique Théorique et Applications |mr=1435732 |pages=443—456 |title=On the Horton–Strahler number for random tries |url=https://eudml.org/doc/92635 |volume=30 |year=1996 |doi=10.1051/ita/1996300504431 |access-date=2019-08-06 |archive-date=2015-10-07 |archive-url=https://web.archive.org/web/20151007092252/https://eudml.org/doc/92635 |url-status=live }} {{Cite web |url=https://eudml.org/doc/92635 |title=Источник |access-date=2019-08-06 |archive-date=2015-10-07 |archive-url=https://web.archive.org/web/20151007092252/https://eudml.org/doc/92635 |deadlink=unfit }}.</ref> <math>\log_2 n + 1</math>.

[[Изометрическая размерность]] [[Частичный куб|частичного куба]] с <math>n</math> вершинами не меньше, чем <math>\log_2 n.</math> Число рёбер куба не более, чем  <math>\frac12 n\log_2 n,</math> равенство имеет место, когда частичный куб является [[граф гиперкуба|графом гиперкуба]]<ref>{{citation | last = Eppstein | first = David  |arxiv = cs.DS/0402028 | doi = 10.1016/j.ejc.2004.05.001 | issue = 5 | journal = European Journal of Combinatorics | mr = 2127682 | pages = 585–592 | title = The lattice dimension of a graph | volume = 26 | year = 2005}}</ref>.

Согласно [[Теорема Рамсея|теореме Рамсея]], [[неориентированный граф]] с <math>n</math> вершинами содержит либо [[Клика (теория графов)|клику]], либо [[Задача о независимом множестве|независимое множество]], размер которого логарифмически зависит от <math>n.</math> Точный размер этого множества неизвестен, но наилучшие в настоящий момент оценки содержат двоичные логарифмы.

=== Другие применения ===
Число кругов игры по [[Олимпийская система|олимпийской системе]] равно двоичному логарифму от числа участников соревнований<ref>{{книга|автор=Харин А. А.|заглавие=Организация и проведение соревнований. Методическое пособие|ссылка=http://elibrary.udsu.ru/xmlui/bitstream/handle/123456789/8185/2011348.pdf?sequence=1|место=Ижевск|издательство=УдГУ|год=2011|страницы=27|archivedate=2020-07-24|archiveurl=https://web.archive.org/web/20200724145317/http://elibrary.udsu.ru/xmlui/bitstream/handle/123456789/8185/2011348.pdf?sequence=1}}</ref>.

В [[Теория музыки|теории музыки]], чтобы решить вопрос о том, на сколько частей делить [[Октава|октаву]], требуется отыскать рациональное приближение для <math>\log_2 \frac {3}{2} \approx 0{,}585.</math> Если разложить это число в [[Непрерывная дробь|непрерывную дробь]], то третья подходящая дробь (7/12) позволяет обосновать классическое деление октавы на 12 [[полутон]]ов<ref>''Шилов Г. Е.'' [http://www.math.ru/lib/book/plm/v37.djvu Простая гамма. Устройство музыкальной шкалы.] {{Wayback|url=http://www.math.ru/lib/book/plm/v37.djvu |date=20140222071112 }} М.: Физматгиз, 1963. 20 с. Серия «Популярные лекции по математике», выпуск 37.</ref>.

== Примечания ==
{{примечания}}

== Литература ==
* {{книга |автор=[[Выгодский, Марк Яковлевич|Выгодский М. Я.]]
  |заглавие=Справочник по элементарной математике |издание=изд. 25-е
  |ссылка=http://eqworld.ipmnet.ru/ru/library/books/Vygodskij1966ru.djvu
  |место = М. |издательство=Наука |год=1978 |isbn=5-17-009554-6 
  |ref=Выгодский М. Я. Справочник по элементарной математике }}
* {{книга |автор=Корн Г., Корн Т. |ссылка=http://eqworld.ipmnet.ru/ru/library/books/Korn1973ru.djvu
  |заглавие=Справочник по математике (для научных работников и инженеров) |страниц=720
  |издательство=Наука |место=М. |год=1973 |ref=Корн Г., Корн Т. Справочник по математике }}
* {{книга |автор=[[Фихтенгольц, Григорий Михайлович|Фихтенгольц Г. М.]]
  |заглавие=Курс дифференциального и интегрального исчисления
  |издание=изд. 6-е |место=М. |издательство=Наука |год=1966 |страниц=680
  |ref=Фихтенгольц Г. М. Курс дифференциального и интегрального исчисления }}

== Ссылки ==
* [http://sernam.ru/book_tp.php?id=128 Таблица двоичных логарифмов целых чисел от 1 до 100.] {{Wayback|url=http://sernam.ru/book_tp.php?id=128 |date=20190812002132 }} 

[[Категория:Логарифмы]]
[[Категория:Двоичная арифметика]]