Logaritm binar

Logaritmul binar este logaritmul de bază 2. Cu alte cuvinte, logaritmul binar al unui număr este soluția ecuației $b$ $2^{x}=b.$

Logaritmul binar al unui număr real există dacă, conform ISO 31-11 , acesta este notat cu [1] sau . Exemple: $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

Istorie

Din punct de vedere istoric, logaritmii binari și-au găsit prima utilizare în teoria muzicii când Leonhard Euler a stabilit că logaritmul binar al raportului dintre frecvențele a două tonuri muzicale este egal cu numărul de octave care separă un ton de altul. Euler a publicat și un tabel cu logaritmii binari ai numerelor întregi de la 1 la 8, până la șapte zecimale [2] [3] .

Odată cu apariția informaticii , a devenit clar că erau necesari logaritmi binari pentru a determina numărul de biți necesari pentru a codifica un mesaj . Alte domenii în care logaritmul binar este adesea folosit includ combinatoria , bioinformatica , criptografia , turneele sportive și fotografia . O funcție standard pentru calcularea logaritmului binar este furnizată în multe sisteme de programare comune.

Proprietăți algebrice

Următorul tabel presupune că toate valorile sunt pozitive [4] :

	Formulă	Exemplu
Muncă	$\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$
Coeficientul de diviziune	$\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$
grad	$\operatorname {lb} (x^{p})=p\operatorname {lb} (x)$	$\operatorname {lb} (1024)=\operatorname {lb} (2^{10})=10\operatorname {lb} (2)=10$
Rădăcină	$\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$

Există o generalizare evidentă a formulelor de mai sus în cazul în care sunt permise variabile negative, de exemplu:

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

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

Formula pentru logaritmul unui produs poate fi generalizată cu ușurință la un număr arbitrar de factori:

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

Relația dintre logaritmii binari, naturali și zecimali :

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

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

Funcția logaritm binar

Dacă considerăm numărul logaritmic ca o variabilă, obținem funcția logaritm binar: . Este definit pentru toată gama de valori: . Graficul acestei funcții este adesea numit logaritm , este inversul funcției . Funcția este monoton crescătoare, continuă și diferențiabilă oriunde este definită. Derivata pentru aceasta este data de formula [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}

Axa y este o asimptotă verticală deoarece: $(x=0)$

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

Aplicație

Teoria informației

Logaritmul binar al unui număr natural vă permite să determinați numărul de cifre din reprezentarea computerului intern ( bit ) a acestui număr: $N$ $b(N)$

b(N) = \lfloor \operatorname{lb} N \rfloor + 1

(parantezele indică partea întreagă a numărului)

Entropia informației este o măsură a cantității de informații , bazată și pe logaritmul binar

Complexitatea algoritmilor recursivi

Estimarea complexității asimptotice a algoritmilor recursivi de împărțire și cucerire [6] , cum ar fi sortarea rapidă , transformarea Fourier rapidă , căutarea binară etc.

Combinatorică

Dacă un arbore binar conține noduri, atunci înălțimea lui nu este mai mică decât (egalitatea se realizează dacă este o putere de 2) [7] . În consecință, numărul Strahler-Filosofov pentru un sistem fluvial cu afluenți nu depășește [8] . $n$ $\log _{2}n$ $n$ $n$ $\log _{2}n+1$

Dimensiunea izometrică a unui cub parțial cu vârfuri nu este mai mică decât numărul de muchii ale cubului, nu mai mult decât este valabil și egalitatea atunci când cubul parțial este un grafic hipercub [9] . $n$ $\log _{2}n.$ ${\frac {1}{2}}n\log _{2}n,$

Conform teoremei lui Ramsey , un grafic de vârf nedirecționat conține fie o clică , fie o mulțime independentă a cărei dimensiune depinde logaritmic de Mărimea exactă a acestei mulțimi este necunoscută, dar cele mai bune estimări în prezent conțin logaritmi binari. $n$ $n.$

Alte utilizări

Numărul de runde ale jocului conform sistemului olimpic este egal cu logaritmul binar al numărului de participanți la competiție [10] .

În teoria muzicii , pentru a rezolva problema câte părți să împărțim o octava , este necesar să găsim o aproximare rațională pentru Dacă extindem acest număr într-o fracție continuă , atunci a treia fracție convergentă (7/12) ne permite pentru a justifica împărțirea clasică a octavei în 12 semitonuri [11] . $\log_2 \frac {3}{2} \aprox 0{,}585.$

Note

↑ Uneori, mai ales în edițiile germane, logaritmul binar este notat (din latinescul logarithmus dyadis ), vezi Bauer, Friedrich L. Origins and Foundations of Computing: In Cooperation with Heinz Nixdorf MuseumsForum (engleză) . - Springer Science & Business Media , 2009. - P. 54. - ISBN 978-3-642-02991-2 . $\operatorname {ld} b$
↑ Euler, Leonhard (1739), Capitolul VII. De Variorum Intervallorum Receptis Appelationibus , Tentamen novae theoriae musicae ex certissismis harmoniae principiis dilucide expositae , Academia din Sankt Petersburg, p. 102-112 , < http://eulerarchive.maa.org/pages/E033.html > Arhivat 11 octombrie 2018 la Wayback Machine .
↑ Tegg, Thomas (1829), Binary logarithms , enciclopedia londoneză; sau, Dicționar universal de știință, artă, literatură și mecanică practică: cuprinzând o viziune populară asupra stării actuale a cunoașterii, Volumul 4 , p. 142–143 , < https://books.google.com/books?id=E-ZTAAAAYAAJ&pg=PA142 > Arhivat 23 mai 2021 la Wayback Machine .
↑ Vygodsky M. Ya. Manual de matematică elementară, 1978 , p. 187..
↑ Funcția logaritmică. // Enciclopedie matematică (în 5 volume) . - M . : Enciclopedia Sovietică , 1982. - T. 3.
↑ Harel, David; Feldman, Yishai A. Algoritmici: spiritul de calcul . - New York: Addison-Wesley, 2004. - P. 143 . - ISBN 978-0-321-11784-7 .
↑ Leiss, Ernst L. (2006), A Programmer's Companion to Algorithm Analysis , CRC Press, p. 28, ISBN 978-1-4200-1170-8 , < https://books.google.com/books?id=E6BNGFQ6m_IC&pg=RA2-PA28 > Arhivat la 12 august 2020 la Wayback Machine
↑ Devroye, L. & Kruszewski, P. (1996), On the Horton-Strahler number for random tries , RAIRO Informatique Théorique et Applications vol . 30 (5): 443-456, doi : 10.1051/ita/19963005041 , < https://www.airo.org/ ://eudml.org/doc/92635 > Arhivat la 7 octombrie 2015 la Wayback Machine .
↑ Eppstein, David (2005), The lattice dimension of a graph , European Journal of Combinatorics vol. 26 (5): 585–592 , DOI 10.1016/j.ejc.2004.05.001
↑ Kharin A. A. Organizarea și desfășurarea de concursuri. Ghid metodologic . - Izhevsk: UdGU, 2011. - S. 27.
↑ Shilov G. E. Gama simplă. Dispozitiv de cântare muzicală. Copie de arhivă din 22 februarie 2014 la Wayback Machine M.: Fizmatgiz, 1963. 20 p. Seria „Prelegeri populare de matematică”, numărul 37.

Literatură

Vygodsky M. Ya. Manual de matematică elementară . - ed. 25. - M .: Nauka, 1978. - ISBN 5-17-009554-6 .
Korn G., Korn T. Manual de matematică (pentru cercetători și ingineri) . - M . : Nauka, 1973. - 720 p.
Fikhtengol's G. M. Curs de calcul diferențial și integral. - ed. al 6-lea. — M .: Nauka, 1966. — 680 p.

Link -uri

Tabel de logaritmi binari ai numerelor întregi de la 1 la 100. Arhivat 12 august 2019 la Wayback Machine