Бинарни логаритам

график log₂ n

У математици, бинарни логаритам (log2 n) је логаритам са основом 2. То је инверзна функција функцији n ↦ 2n.. Бинарни логаритам n је степен на који број 2 мора бити подигнут да би достигао вредност n. Ово чини бинарни логаритам корисним за све што укључује степене двојке, односно дуплирања. На пример, бинарни логаритам од 1 је 0, бинарни логаритам од 2 је 1, бинарни логаритам од 4 је 2, бинарни логаритам од 8 је 3, бинарни логаритам од16 је 4 и бинарни логаритам од 32 је 5.

Примена

Информатика

Бинарни логаритам се често користи у информатици, јер је уско повезан са бинарним системом бројева. Често се написано ld n, од латинског logarithmus duālis, или lg n, иако је ИСО системом предвиђено lb (n), lg (n) се користи за log₁₀ n. Број цифара, бита, у бинарном запису представља позитиван цео број од n од 1 + lb n, .

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

У информатичкој теорији, дефинисање износа Само-информација и информациона ентропија укључује бинарни логаритам; ово је потребно јер јединица информације, бит, се односи на информације настале од појаве једног од два једнако вероватних догађаја.

Рачунарска комплексност

Бинарни логаритам се такође често појављује у анализи алгоритама. Ако се број n већи од 1 подели два пута уѕастопно са 2 , број итерација потребних да би достигао вредност највише до 1 је поново интегралан део lb n . Ова идеја се користи у анализи неколико алгоритма а и у структури података. На пример, величина проблема које треба решити је преполовљена са сваком итерацијом, и стога је потребно отприлике lb n итерација за добијање проблема величине 1 , који се лако решавају. Слично томе, савршено избалансиран n који садржи елементе је величина lb n + 1 .

Међутим, време рада алгоритма се обично изражава у Биг О нотацији, игноришући сталне факторе. Пошто log₂ n = (1/log_k 2)log_k n, где к може бити било који број већи од 1, алгоритама који раде у O(log₂ n) време може се такође рећи да ради, рецимо , O(log₁₃ n) времена. База логаритма у изразима као што су O(log n) или O(n log n) због тога није важна .

У другим контекстима база логаритма мора бити наведена. На пример O(2^lb n) није исто што и O(2^ln n) јер је први једнак O(n) а други O(n^0.6931...).

Алгоритми са текућим временом n lb n се понекад назива линеарним. Неки примери алгоритама са текућим временом O(lb n) или O(n lb n) су:

• average time quicksort
• binary search trее
• merge sort
• Monge array calculation

Сингл елиминациони турнири

У такмичарским играма и спортовима који укључују два играча / тима у свакој игри / мечу, бинарни логаритам означава број рунди неопходних у циљу утврђивања победника. На пример, турнир од 4 играча захтева lb ( 4 ) или 2 кола за одређивање победника, турнир од 32 тима захтева lb ( 32) метака, што је 5 метака, итд. У овом случају, за n играча/ тимова где n није степен двојке , lb ( n) се заокружује, јер ће бити неопходно да имају најмање један круг у коме сви преостали такмичари играју. На пример , lb ( 6 ) је око 2.585 , заокружен, указује да турнир од 6 захтева 3 рунде ( или ће 2 тима ће одседети прву рунду, или један тим ће седети током другог круга ) .

Коришћење калкулатора

Једноставан начин за израчунавање log₂(n) на калкулатору а да немају функцију log₂ је да користите природни логаритам " ln " или заједнички логаритам " log " функције, које се налазе на већини „озбиљнијих калкулатора ". Класичне формуле за промену логаритамске основе су:

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

па

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

и то поставља питање да ли је log₂(n)у оквиру 0,6% log_e(n) + log₁₀(n). log_e(n)+log₁₀(n) је заправо log_2.0081359...(n) где је основа e^{1/(1+log₁₀e)} = 10^{1/(1 + log_e10)} ≈ 2.00813 59293 46243 95422 87563 25191 0 to (32 значајне цифре). Наравно, log₁₀10 = log_ee = 1.

Алгоритам

Цео број

За цео домен и опсег, бинарни логаритам се може израчунати заокруживањем горе или доле. Ова два облика интеџер бинарног логаритма се односе према овој формули

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

Дефиниција се може продужити дефинисањем $\lfloor \log _{2}(0)\rfloor =-1$. Ова функција се односи и на број главних нула неодрађеног 32-битног бинарног приказа x, nlz(x).

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

Овај бинарни логаритам се може тумачити као индекс 0 најзначајнијег бита 1 у улазу. У том смислу је комплемент проналазак први сет операције, која проналази индекс најмање значајног бита 1.

Реалан број

За општи позитиван реалан број, бинарни логаритам се може израчунати у два корака :

1. Израчунати део $\lfloor \operatorname {lb} (x)\rfloor$
2. Израчунати разломак

За било које x > 0, постоји јединствен цео број n , такав да 2ⁿ ≤ x < 2ⁿ⁺¹, односно 1 ≤ 2⁻ⁿx < 2. Сада је интеџер део логарима само n, а раѕломачки део lb(2⁻ⁿx). Другим речима:

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

Разломачки део резултата је $\operatorname {lb} y$, а може се израчунати користећи најосновније множење и дељење.

Да бисте израчунали разломачки део :

1. Почињемо са реалним бројем $y\in [1,2)$. Ако је $y=1$, онда смо завршили и разломачки део је нула.
2. У супротном, квадрирамо $y$ бише пута док резултат не постане $z\in [2,4)$. Нека је $m$ број потребних степеновања. То значи да је, $z=y^{2\uparrow m}$ са $m$ изабран тако да $z\in [2,4)$
3. Логаритмовањем обе стране и рачунањем добијамо

   ${\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. Приметимо да је $z/2$ поново реални број у интервалу $[1,2)$.
5. Вратимо се на први корак и израчунајмо бинарни логаримтам од $z/2$ користећи ову методу.

Резултат тога је изражен следећим формулама, у којима $m_{i}$ број квадрирања потербан за i-ту рекурзију логаритма

${\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}}$

У посебном случају када је разломачки део у кораку један нула, ово је ограничена секвенца која се завршава у једном тренутку. У супротном, то је бесконачно серија која конвергира, јер је сваки део строго мањи од претходног (јер сваки $m_{i}>0$). У пракси, ова серија се мора скратити до приблињног резултата. Ако је серија смањена пре 'i-тог дела, онда је грешка у резултату мања од $2^{-(m_{1}+m_{2}+\cdots +m_{i})}$.

Срећом, у пракси можемо да урадимо обрачуне и знамо грешке без икаквог рачунања. Претпоставимо да желимо израчунати log of 1.65 са четири бинарне цифре. Поновите ове кораке четири пута :

1. Квадрирајте број
2. Ако је квадрат > = 2 , то поделите са два и пишите 1. у супротном, написати 0.

Бројеви које смо написали је заправо логаритам написан у бинарном запису.

Ово можемо примењивати све док радимо са било којим бројевима између 1 и 2. Дакле

• • 1,65 квадрирано је 2,72, што је више него два, па смо га преполовити до 1.36 и записали 1
  • 1,36 квадрирано је 1.85, што је мање од два, па га не делимо, већ пишемо 0
  • 1,85 квадрирано је 3.43, што је више од два, па га преполовити на 1.72 и записати 1
  • 1,72 квадрирано је 2.95, што је више од два, па пишемо 1 (нема потребе да се преполови 2,95 јер смо већ завршили)

Написали смо до сада 1011, па бинарни логаритам 1.65 написан у бинарном облику је 0.1011 (или, написан као разломак, 11/16), а грешка је мања од 1/16. Додавањем 1/32, добијамо 23/32 где је грешка мања од 1/32. У принципу, да бисмо добили грешке мање од 0,5 подигнуте на 1+N, потребно нам је N квадрирања или N или мање дељења са два.

Види још

• Природни логаритам

Литература

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