Binarni logaritam

grafik log₂ n

U matematici, binarni logaritam (log2 n) je logaritam sa osnovom 2. To je inverzna funkcija funkciji n ↦ 2n.. Binarni logaritam n je stepen na koji broj 2 mora biti podignut da bi dostigao vrednost n. Ovo čini binarni logaritam korisnim za sve što uključuje stepene dvojke, odnosno dupliranja. Na primer, binarni logaritam od 1 je 0, binarni logaritam od 2 je 1, binarni logaritam od 4 je 2, binarni logaritam od 8 je 3, binarni logaritam od16 je 4 i binarni logaritam od 32 je 5.

Primena

Informatika

Binarni logaritam se često koristi u informatici, jer je usko povezan sa binarnim sistemom brojeva. Često se napisano ld n, od latinskog logarithmus duālis, ili lg n, iako je ISO sistemom predviđeno lb (n), lg (n) se koristi za log₁₀ n. Broj cifara, bita, u binarnom zapisu predstavlja pozitivan ceo broj od n od 1 + lb n, .

$\lfloor \operatorname {lb} \,n\rfloor +1.\,$

U informatičkoj teoriji, definisanje iznosa Samo-informacija i informaciona entropija uključuje binarni logaritam; ovo je potrebno jer jedinica informacije, bit, se odnosi na informacije nastale od pojave jednog od dva jednako verovatnih događaja.

Računarska kompleksnost

Binarni logaritam se takođe često pojavljuje u analizi algoritama. Ako se broj n veći od 1 podeli dva puta uѕastopno sa 2 , broj iteracija potrebnih da bi dostigao vrednost najviše do 1 je ponovo integralan deo lb n . Ova ideja se koristi u analizi nekoliko algoritma a i u strukturi podataka. Na primer, veličina problema koje treba rešiti je prepolovljena sa svakom iteracijom, i stoga je potrebno otprilike lb n iteracija za dobijanje problema veličine 1 , koji se lako rešavaju. Slično tome, savršeno izbalansiran n koji sadrži elemente je veličina lb n + 1 .

Međutim, vreme rada algoritma se obično izražava u Big O notaciji, ignorišući stalne faktore. Pošto log₂ n = (1/log_k 2)log_k n, gde k može biti bilo koji broj veći od 1, algoritama koji rade u O(log₂ n) vreme može se takođe reći da radi, recimo , O(log₁₃ n) vremena. Baza logaritma u izrazima kao što su O(log n) ili O(n log n) zbog toga nije važna .

U drugim kontekstima baza logaritma mora biti navedena. Na primer O(2^lb n) nije isto što i O(2^ln n) jer je prvi jednak O(n) a drugi O(n^0.6931...).

Algoritmi sa tekućim vremenom n lb n se ponekad naziva linearnim. Neki primeri algoritama sa tekućim vremenom O(lb n) ili O(n lb n) su:

• average time quicksort
• binary search tree
• merge sort
• Monge array calculation

Singl eliminacioni turniri

U takmičarskim igrama i sportovima koji uključuju dva igrača / tima u svakoj igri / meču, binarni logaritam označava broj rundi neophodnih u cilju utvrđivanja pobednika. Na primer, turnir od 4 igrača zahteva lb ( 4 ) ili 2 kola za određivanje pobednika, turnir od 32 tima zahteva lb ( 32) metaka, što je 5 metaka, itd. U ovom slučaju, za n igrača/ timova gde n nije stepen dvojke , lb ( n) se zaokružuje, jer će biti neophodno da imaju najmanje jedan krug u kome svi preostali takmičari igraju. Na primer , lb ( 6 ) je oko 2.585 , zaokružen, ukazuje da turnir od 6 zahteva 3 runde ( ili će 2 tima će odsedeti prvu rundu, ili jedan tim će sedeti tokom drugog kruga ) .

Korišćenje kalkulatora

Jednostavan način za izračunavanje log₂(n) na kalkulatoru a da nemaju funkciju log₂ je da koristite prirodni logaritam " ln " ili zajednički logaritam " log " funkcije, koje se nalaze na većini „ozbiljnijih kalkulatora ". Klasične formule za promenu logaritamske osnove su:

log₂(n) = ln(n)/ln(2) = log(n)/log(2)

pa

log2(n) = loge(n)×1.442695... = log10(n)×3.321928...

i to postavlja pitanje da li je log₂(n)u okviru 0,6% log_e(n) + log₁₀(n). log_e(n)+log₁₀(n) je zapravo log_2.0081359...(n) gde je osnova e^{1/(1+log₁₀e)} = 10^{1/(1 + log_e10)} ≈ 2.00813 59293 46243 95422 87563 25191 0 to (32 značajne cifre). Naravno, log₁₀10 = log_ee = 1.

Algoritam

Ceo broj

Za ceo domen i opseg, binarni logaritam se može izračunati zaokruživanjem gore ili dole. Ova dva oblika intedžer binarnog logaritma se odnose prema ovoj formuli

$\lfloor \log _{2}(n)\rfloor =\lceil \log _{2}(n+1)\rceil -1,{\text{ if }}n\geq 1.$

Definicija se može produžiti definisanjem $\lfloor \log _{2}(0)\rfloor =-1$. Ova funkcija se odnosi i na broj glavnih nula neodrađenog 32-bitnog binarnog prikaza x, nlz(x).

$\lfloor \log _{2}(n)\rfloor =31-\operatorname {nlz} (n).$

Ovaj binarni logaritam se može tumačiti kao indeks 0 najznačajnijeg bita 1 u ulazu. U tom smislu je komplement pronalazak prvi set operacije, koja pronalazi indeks najmanje značajnog bita 1.

Realan broj

Za opšti pozitivan realan broj, binarni logaritam se može izračunati u dva koraka :

1. Izračunati deo $\lfloor \operatorname {lb} (x)\rfloor$
2. Izračunati razlomak

Za bilo koje x > 0, postoji jedinstven ceo broj n , takav da 2ⁿ ≤ x < 2ⁿ⁺¹, odnosno 1 ≤ 2⁻ⁿx < 2. Sada je intedžer deo logarima samo n, a raѕlomački deo lb(2⁻ⁿx). Drugim rečima:

$\operatorname {lb} (x)=n+\operatorname {lb} (y)\quad {\text{where }}y=2^{-n}x{\text{ and }}y\in [1,2)$

Razlomački deo rezultata je $\operatorname {lb} y$, a može se izračunati koristeći najosnovnije množenje i deljenje.

Da biste izračunali razlomački deo :

1. Počinjemo sa realnim brojem $y\in [1,2)$. Ako je $y=1$, onda smo završili i razlomački deo je nula.
2. U suprotnom, kvadriramo $y$ biše puta dok rezultat ne postane $z\in [2,4)$. Neka je $m$ broj potrebnih stepenovanja. To znači da je, $z=y^{2\uparrow m}$ sa $m$ izabran tako da $z\in [2,4)$
3. Logaritmovanjem obe strane i računanjem dobijamo

   ${\begin{aligned}\operatorname {lb} \,z&=2^{m}\operatorname {lb} \,y\\\operatorname {lb} \,y&={\frac {\operatorname {lb} z}{2^{m}}}\\&={\frac {1+\operatorname {lb} (z/2)}{2^{m}}}\\&=2^{-m}+2^{-m}\operatorname {lb} (z/2)\end{aligned}}$

4. Primetimo da je $z/2$ ponovo realni broj u intervalu $[1,2)$.
5. Vratimo se na prvi korak i izračunajmo binarni logarimtam od $z/2$ koristeći ovu metodu.

Rezultat toga je izražen sledećim formulama, u kojima $m_{i}$ broj kvadriranja poterban za i-tu rekurziju logaritma

${\begin{aligned}\operatorname {lb} \,x&=n+2^{-m_{1}}\left(1+2^{-m_{2}}\left(1+2^{-m_{3}}\left(1+\cdots \right)\right)\right)\\&=n+2^{-m_{1}}+2^{-m_{1}-m_{2}}+2^{-m_{1}-m_{2}-m_{3}}+\cdots \end{aligned}}$

U posebnom slučaju kada je razlomački deo u koraku jedan nula, ovo je ograničena sekvenca koja se završava u jednom trenutku. U suprotnom, to je beskonačno serija koja konvergira, jer je svaki deo strogo manji od prethodnog (jer svaki $m_{i}>0$). U praksi, ova serija se mora skratiti do priblinjnog rezultata. Ako je serija smanjena pre 'i-tog dela, onda je greška u rezultatu manja od $2^{-(m_{1}+m_{2}+\cdots +m_{i})}$.

Srećom, u praksi možemo da uradimo obračune i znamo greške bez ikakvog računanja. Pretpostavimo da želimo izračunati log of 1.65 sa četiri binarne cifre. Ponovite ove korake četiri puta :

1. Kvadrirajte broj
2. Ako je kvadrat > = 2 , to podelite sa dva i pišite 1. u suprotnom, napisati 0.

Brojevi koje smo napisali je zapravo logaritam napisan u binarnom zapisu.

Ovo možemo primenjivati sve dok radimo sa bilo kojim brojevima između 1 i 2. Dakle

• • 1,65 kvadrirano je 2,72, što je više nego dva, pa smo ga prepoloviti do 1.36 i zapisali 1
  • 1,36 kvadrirano je 1.85, što je manje od dva, pa ga ne delimo, već pišemo 0
  • 1,85 kvadrirano je 3.43, što je više od dva, pa ga prepoloviti na 1.72 i zapisati 1
  • 1,72 kvadrirano je 2.95, što je više od dva, pa pišemo 1 (nema potrebe da se prepolovi 2,95 jer smo već završili)

Napisali smo do sada 1011, pa binarni logaritam 1.65 napisan u binarnom obliku je 0.1011 (ili, napisan kao razlomak, 11/16), a greška je manja od 1/16. Dodavanjem 1/32, dobijamo 23/32 gde je greška manja od 1/32. U principu, da bismo dobili greške manje od 0,5 podignute na 1+N, potrebno nam je N kvadriranja ili N ili manje deljenja sa dva.

Vidi još

• Prirodni logaritam

Literatura

• Warren Jr., Henry S. (2002). Hacker's Delight. Addison Wesley. str. 215. ISBN 978-0-201-91465-8.