Овај чланак можда захтева чишћење и/или прерађивање како би се задовољили стандарди квалитета Википедије. Проблем: математика. Ако сте у могућности, побољшајте овај чланак. (о уклањању шаблона обавештења)

график 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, .

⌊lbn⌋+1.displaystyle lfloor operatorname lb ,nrfloor +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 significant figures). Наравно, log₁₀10 = log_ee = 1.

Алгоритам

Интеџер

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

⌊log2⁡(n)⌋=⌈log2⁡(n+1)⌉−1, if n≥1.displaystyle lfloor log _2(n)rfloor =lceil log _2(n+1)rceil -1,text if ngeq 1. ^[1]

Дефиниција се може продужити дефинисањем ⌊log2⁡(0)⌋=−1displaystyle lfloor log _2(0)rfloor =-1. Ова функција се односи и на број главних нула неодрађеног 32-битног бинарног приказа x, nlz(x).

⌊log2⁡(n)⌋=31−nlz⁡(n).displaystyle lfloor log _2(n)rfloor =31-operatorname nlz (n).^[1]

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

Реалан број

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

1. Израчунати део ⌊lb⁡(x)⌋displaystyle lfloor operatorname lb (x)rfloor
   


2. Израчунати разломак

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

lb⁡(x)=n+lb⁡(y)where y=2−nx and y∈[1,2)displaystyle operatorname lb (x)=n+operatorname lb (y)quad textwhere y=2^-nxtext and yin [1,2)

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

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

1. Почињемо са реалним бројем y∈[1,2)displaystyle yin [1,2). Ако је y=1displaystyle y=1, онда смо завршили и разломачки део је нула.


2. У супротном , квадрирамо ydisplaystyle y бише пута док резултат не постане z∈[2,4)displaystyle zin [2,4). Нека је mdisplaystyle m број потребних степеновања. То ѕначи да је, z=y2↑mdisplaystyle z=y^2uparrow m са mdisplaystyle m изабран тако да z∈[2,4)displaystyle zin [2,4)
   


3. Логаритмовањем обе стране и рачунањем добијамо
   

   lbz=2mlbylby=lb⁡z2m=1+lb⁡(z/2)2m=2−m+2−mlb⁡(z/2)displaystyle beginalignedoperatorname lb ,z&=2^moperatorname lb ,y\operatorname lb ,y&=frac operatorname lb z2^m\&=frac 1+operatorname lb (z/2)2^m\&=2^-m+2^-moperatorname lb (z/2)endaligned



4. Приметимо да је z/2displaystyle z/2 поново реални број у интервалу [1,2)displaystyle [1,2).


5. Вратимо се на први корак и израчунајмо бинарни логаримтам од z/2displaystyle z/2 користећи ову методу.

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

lbx=n+2−m1(1+2−m2(1+2−m3(1+⋯)))=n+2−m1+2−m1−m2+2−m1−m2−m3+⋯displaystyle beginalignedoperatorname lb ,x&=n+2^-m_1left(1+2^-m_2left(1+2^-m_3left(1+cdots right)right)right)\&=n+2^-m_1+2^-m_1-m_2+2^-m_1-m_2-m_3+cdots endaligned

У посебном случају када је разломачки део у кораку један нула, ово је ограничена секвенца која се завршава у једном тренутку. У супротном , то је бесконачно серија која конвергира, јер је сваки део строго мањи од претходног (јер сваки mi>0displaystyle m_i>0). У пракси, ова серија се мора скратити до приблињног резултата. Ако је серија смањена пре 'i-тог дела, онда је грешка у резултату мања од 2−(m1+m2+⋯+mi)displaystyle 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.