Binární logaritmus

Binární logaritmus je logaritmus se základem 2. Jinými slovy, binární logaritmus čísla je řešením rovnice $b$ $2^{x}=b.$

Binární logaritmus reálného čísla existuje, pokud je podle ISO 31-11 označen [1] nebo . Příklady: $b$ $b>0.$ $\operatorname {lb} b,$ $\operatorname {lb} (b)$ $\log _{2}b$

\operatorname{lb} 1=0;\, \operatorname{lb} 2=1;\, \operatorname{lb} 16=4

\operatorname{lb} 0{,}5=-1;\, \operatorname{lb} \frac{1}{256}=-8

Historie

Historicky našly binární logaritmy své první použití v hudební teorii , když Leonhard Euler zjistil, že binární logaritmus poměru frekvencí dvou hudebních tónů se rovná počtu oktáv , které oddělují jeden tón od druhého. Euler také zveřejnil tabulku binárních logaritmů celých čísel 1 až 8 až na sedm desetinných míst [2] [3] .

S příchodem informatiky bylo jasné, že k určení počtu bitů požadovaných ke kódování zprávy jsou potřeba binární logaritmy . Mezi další oblasti, ve kterých se binární logaritmus často používá, patří kombinatorika , bioinformatika , kryptografie , sportovní turnaje a fotografie . Standardní funkce pro výpočet binárního logaritmu je k dispozici v mnoha běžných programovacích systémech.

Algebraické vlastnosti

Následující tabulka předpokládá, že všechny hodnoty jsou kladné [4] :

	Vzorec	Příklad
Práce	$\operatorname {lb} (xy)=\operatorname {lb} (x)+\operatorname {lb} (y)$	$\operatorname {lb} (256)=\operatorname {lb} (16\cdot 16)=\operatorname {lb} (16)+\operatorname {lb} (16)=4+4=8$
Podíl dělení	$\operatorname {lb} \!\left({\frac {x}{y}}\right)=\operatorname {lb} (x)-\operatorname {lb} (y)$	$\operatorname{lb} \left(\frac{1}{32}\right) = \operatorname{lb} (1) - \operatorname{lb} (32) = 0 - 5 = -5$
Stupeň	$\operatorname {lb} (x^{p})=p\operatorname {lb} (x)$	$\operatorname {lb} (1024)=\operatorname {lb} (2^{10})=10\operatorname {lb} (2)=10$
Vykořenit	$\operatorname {lb} {\sqrt[{p}]{x}}={\frac {\operatorname {lb} (x)}{p}}$	$\operatorname{lb} \sqrt{8} = \frac{1}{2}\operatorname{lb} 8 = \frac{3}{2} = 1{,}5$

Je zřejmé zobecnění výše uvedených vzorců na případ, kdy jsou povoleny záporné proměnné, například:

\operatorname{lb} |xy| = \operatorname{lb} (|x|) + \operatorname{lb} (|y|),

\operatorname{lb} \!\left|\frac xy \right| = \operatorname{lb} (|x|) - \operatorname{lb} (|y|),

Vzorec pro logaritmus součinu lze snadno zobecnit na libovolný počet faktorů:

\operatorname{lb}(x_1 x_2 \dots x_n) = \operatorname{lb} (x_1) + \operatorname{lb} (x_2) + \dots + \operatorname{lb} (x_n)

Vztah mezi binárními, přirozenými a desítkovými logaritmy:

\operatorname{lb} x \cca 1{,}442695 \ln x

\operatorname{lb} x \cca 3{,}321928 \lg x

Funkce binárního logaritmu

Uvažujeme-li logaritmické číslo jako proměnnou, dostaneme binární logaritmickou funkci: . Je definován pro všechny rozsahy hodnot: . Graf této funkce se často nazývá logaritmus , je to inverzní funkce . Funkce je monotónně rostoucí, spojitá a diferencovatelná , kdekoli je definována. Jeho derivace je dána vzorcem [5] : $y=\operatorname {lb} x$ $x>0,$ $E(y)=(-\infty ;+\infty )$ $y=2^{x}$

\frac {d} {dx} \operatorname{lb} x = \frac {\operatorname{lb} e} {x}

Osa y je svislá asymptota , protože: $(x=0)$

\lim_{x \to 0+0} \operatorname{lb} x = - \infty

Aplikace

Teorie informace

Binární logaritmus přirozeného čísla vám umožňuje určit počet číslic ve vnitřní počítačové ( bitové ) reprezentaci tohoto čísla: $N$ $b(N)$

b(N) = \lpodlaží \jméno operátora{lb} N \rpodlaží + 1

(závorky označují celočíselnou část čísla)

Informační entropie je mírou množství informací , také na základě binárního logaritmu

Složitost rekurzivních algoritmů

Odhad asymptotické složitosti rekurzivních algoritmů rozděl a panuj [6] , jako je quicksort , rychlá Fourierova transformace , binární vyhledávání atd.

Kombinatorika

Pokud binární strom obsahuje uzly, pak jeho výška není menší než (rovnosti je dosaženo, je- li mocnina 2) [7] . V souladu s tím Strahler-Filosofov číslo pro říční systém s přítoky nepřesahuje [8] . $n$ $\log _{2}n$ $n$ $n$ $\log _{2}n+1$

Izometrický rozměr částečné krychle s vrcholy není menší než počet hran krychle, ne více než platí rovnost, když je částečná krychle grafem hyperkrychle [9] . $n$ $\log _{2}n.$ ${\frac {1}{2}}n\log _{2}n,$

Podle Ramseyho teorému obsahuje neorientovaný vrcholový graf buď kliku nebo nezávislou množinu , jejíž velikost závisí logaritmicky na Přesná velikost této množiny není známa, ale aktuálně nejlepší odhady obsahují binární logaritmy. $n$ $n.$

Další použití

Počet kol hry podle olympijského systému se rovná binárnímu logaritmu počtu účastníků soutěže [10] .

Abychom v hudební teorii vyřešili otázku, kolik dílů rozdělit oktávu , je nutné najít racionální aproximaci pro Pokud toto číslo rozšíříme na pokračující zlomek , pak třetí konvergentní zlomek (7/12) nám umožňuje zdůvodnit klasické rozdělení oktávy na 12 půltónů [11] . $\log_2 \frac {3}{2} \cca 0{,}585.$

Poznámky

↑ Někdy, zvláště v německých vydáních, je binární logaritmus označován (z latinského logaritmus dyadis ), viz Bauer, Friedrich L. Origins and Foundations of Computing: In Cooperation with Heinz Nixdorf MuseumsForum (anglicky) . - Springer Science & Business Media , 2009. - S. 54. - ISBN 978-3-642-02991-2 . $\operatorname {ld} b$
↑ Euler, Leonhard (1739), kapitola VII. De Variorum Intervallorum Receptis Appelationibus , Tentamen novae theoriae musicae ex certissismis harmoniae principiis dilucide expositae , Petrohradská akademie, s. 102-112 , < http://eulerarchive.maa.org/pages/E033.html > Archivováno 11. října 2018 ve Wayback Machine .
↑ Tegg, Thomas (1829), Binární logaritmy , Londýnská encyklopedie; aneb Univerzální slovník vědy, umění, literatury a praktické mechaniky: obsahující populární pohled na současný stav poznání, svazek 4 , str. 142–143 , < https://books.google.com/books?id=E-ZTAAAAYAAJ&pg=PA142 > Archivováno 23. května 2021 ve Wayback Machine .
↑ Vygodsky M. Ya. Příručka elementární matematiky, 1978 , s. 187..
↑ Logaritmická funkce. // Matematická encyklopedie (v 5 svazcích) . - M . : Sovětská encyklopedie , 1982. - T. 3.
↑ Harel, David; Feldman, Yishai A. Algorithmics: the spirit of computing . - New York: Addison-Wesley, 2004. - S. 143 . - ISBN 978-0-321-11784-7 .
↑ Leiss, Ernst L. (2006), A Programmer's Companion to Algorithm Analysis , CRC Press, str. 28, ISBN 978-1-4200-1170-8 , < https://books.google.com/books?id=E6BNGFQ6m_IC&pg=RA2-PA28 > Archivováno 12. srpna 2020 na Wayback Machine
↑ Devroye, L. & Kruszewski, P. (1996), O čísle Horton-Strahler pro náhodné pokusy , RAIRO Informatique Théorique et Applications vol . 30 (5): 443-456, doi : 10.1051 /ita/ 10463105 ://eudml.org/doc/92635 > Archivováno 7. října 2015 na Wayback Machine .
↑ Eppstein, David (2005), The lattice division of a graph , European Journal of Combinatorics vol. 26 (5): 585–592 , DOI 10.1016/j.ejc.2004.05.001
↑ Kharin A. A. Organizace a pořádání soutěží. Metodická příručka . - Iževsk: UdGU, 2011. - S. 27.
↑ Shilov G. E. Jednoduchá gama. Zařízení hudební stupnice. Archivní kopie ze dne 22. února 2014 na Wayback Machine M.: Fizmatgiz, 1963. 20 s. Řada "Populární přednášky z matematiky", číslo 37.

Literatura

Vygodsky M. Ya. Příručka elementární matematiky . - ed. 25. - M .: Nauka, 1978. - ISBN 5-17-009554-6 .
Korn G., Korn T. Příručka matematiky (pro výzkumníky a inženýry) . - M .: Nauka, 1973. - 720 s.
Fikhtengol'ts G. M. Kurz diferenciálního a integrálního počtu. - ed. 6. — M .: Nauka, 1966. — 680 s.

Odkazy

Tabulka binárních logaritmů celých čísel od 1 do 100. Archivováno 12. srpna 2019 na Wayback Machine