Bináris logaritmus - Binary logarithm

A log ₂  x grafikonja az x pozitív valós szám függvényében

A matematikában a bináris logaritmus ( log ₂  n ) az a hatvány , amelyre a 2 -es számot fel kell emelni az n érték eléréséhez  . Vagyis bármilyen valós számra x ,

${\ displaystyle x = \ log _ {2} n \ quad \ Longleftrightarrow \ quad 2^{x} = n.}$

Például, a kettes alapú logaritmusának 1 jelentése 0 , kettes alapú logaritmusának 2 jelentése 1 , kettes alapú logaritmusának 4 jelentése  2 , és a bináris logaritmusa 32 jelentése  5 .

A kettes alapú logaritmusának a logaritmusa , hogy a bázis 2 , és az inverz függvény az erejét két funkciót. A log ₂ mellett az lb bináris logaritmus alternatív jelölése (az ISO 31-11 és az ISO 80000-2 által preferált jelölés ).

Történelmileg a bináris logaritmusok első alkalmazása a zeneelméletben volt , Leonhard Euler : a két zenei hang frekvenciaarányának bináris logaritmusa adja meg az oktávok számát, amelyekkel a hangok eltérnek. A bináris logaritmusok segítségével kiszámítható a szám bináris számrendszerben való ábrázolásának hossza , vagy az üzenetek kódolásához szükséges bitek száma az információelméletben . Az informatikában számolják a bináris kereséshez és a kapcsolódó algoritmusokhoz szükséges lépések számát . Más területeken, ahol a kettes alapú logaritmusának gyakran használják többek között a kombinatorika , bioinformatika , a design a sport versenyek , és fényképezés .

A bináris logaritmusokat a standard C matematikai függvények és más matematikai szoftvercsomagok tartalmazzák. A bináris logaritmus egész része megtalálható a kereső első halmaz művelet segítségével egy egész értéken, vagy egy lebegőpontos érték kitevőjének megkeresésével . A logaritmus tört része hatékonyan kiszámítható.

Történelem

Leonhard Euler volt az első, aki bináris logaritmusokat alkalmazott a zeneelméletben , 1739 -ben.

A hatásköre két már ismert, már az ókorban is; például az Euklidesz Elemek , Kellékek című könyvben jelennek meg . IX.32 (a faktorizációja hatáskörének kettő) és IX.36 (fele a Euclid-Euler-tétel , a szerkezet még tökéletes számok ). A kettes hatvány bináris logaritmusa pedig csak a pozíciója a kettő hatványainak sorrendjében. Ennek alapján Michael Stifelt 1544 -ben közzétették az első ismert bináris logaritmusok táblázatában. Az Arithmetica Integra című könyve számos táblázatot tartalmaz, amelyek az egész számokat és a hozzájuk tartozó kettős hatásköröket mutatják be. E táblázatok sorainak megfordítása lehetővé teszi, hogy bináris logaritmusok táblázataiként értelmezzék őket.

Korábban, mint Stifel, a 8. századi jain matematikus, Virasena a bináris logaritmus előfutára. Virasena fogalma ardhacheda lett meghatározva, hogy hányszor adott számot lehet osztani egyenletesen kettő. Ez a meghatározás olyan függvényt eredményez, amely egybeesik a bináris logaritmussal a két hatványon, de más a más egészeknél, és a logaritmus helyett a 2-adic rendet adja meg .

Leonhard Euler 1739 -ben kifejezetten figyelembe vette a bináris logaritmus modern formáját, amely tetszőleges számra alkalmazható (nem csak kettő hatványaira) . Euler megalapozta a bináris logaritmusok alkalmazását a zeneelméletben, jóval azelőtt, hogy az információelméletben és a számítástechnikában való alkalmazásuk elterjedt volna. ismert. Ezen a területen végzett munkája részeként Euler közzétette az 1 és 8 közötti egész számok bináris logaritmusainak táblázatát hét tizedesjegy pontossággal.

Definíció és tulajdonságok

A bináris logaritmus függvény lehet meghatározni, mint az inverz függvényt a hatalom két funkció, ami szigorúan monoton növekvő függvény a pozitív valós számok , és ezért egyedi inverze. Alternatívaként meghatározhatjuk, mint ln n /ln 2 , ahol ln a természetes logaritmus , bármely szabványos módon definiálva. A komplex logaritmus használata ebben a definícióban lehetővé teszi a bináris logaritmus kiterjesztését a komplex számokra .

A többi logaritmushoz hasonlóan a bináris logaritmus a következő egyenleteknek felel meg, amelyekkel egyszerűsíteni lehet azokat a képleteket, amelyek a bináris logaritmusokat szorzással vagy hatványozással kombinálják:

${\ displaystyle \ log _ {2} xy = \ log _ {2} x+\ log _ {2} y}$

${\ displaystyle \ log _ {2} {\ frac {x} {y}} = \ log _ {2} x- \ log _ {2} y}$

${\ displaystyle \ log _ {2} x^{y} = y \ log _ {2} x.}$

További információért lásd a logaritmikus azonosságok listáját .

Jelölés

A matematikában az n szám bináris logaritmusát gyakran log ₂  n -ként írják . Ennek a funkciónak számos más jelölését használták vagy javasolták, különösen az alkalmazási területeken.

Egyes szerzők a bináris logaritmust lg n néven írják , a The Chicago Manual of Style felsorolásban . Donald Knuth ezt a jelölést Edward Reingold javaslatának tulajdonítja , de használata mind az információelméletben, mind a számítástechnikában Reingold aktív kezdete előtt történt. A bináris logaritmust log n -ként is megírtuk, azzal a korábbi kijelentéssel, hogy a logaritmus alapértelmezett alapja  2 . Egy másik jelölést, amelyet gyakran használnak az azonos funkciót (különösen a német szakirodalomban is) LD n , a latin logarithmus dualis vagy logarithmus dyadis . A DIN 1302  [ de ] , az ISO 31-11 és az ISO 80000-2 szabványok egy másik jelölést javasolnak, lb n . Ezen szabványok szerint az lg n -t nem szabad használni a bináris logaritmushoz, mivel helyette a közös logaritmus log ₁₀ n számára van fenntartva .

Alkalmazások

Információelmélet

A számjegyek száma ( bit ) a bináris ábrázolása egy pozitív egész szám n jelentése a szerves része a 1 + log ₂  n , azaz

${\ displaystyle \ lfloor \ log _ {2} n \ rfloor +1.}$

Az információelméletben az öninformáció és az információ entrópia mennyiségének meghatározását gyakran a bináris logaritmussal fejezik ki, ami azt jelenti, hogy a bit az információ alapegysége . Ezekkel az egységekkel a Shannon – Hartley-tétel egy csatorna információs kapacitását fejezi ki a jel-zaj arány bináris logaritmusaként, plusz eggyel. Azonban a természetes logaritmus és a nat alternatív jelölésekben is használatos ezekhez a definíciókhoz.

Kombinatorika

Egy 16 játékosból álló, kizáró bajnoki konzol egy teljes bináris fa felépítéssel . A fa magassága (a verseny fordulóinak száma) a játékosok számának bináris logaritmusa, egész számra kerekítve.

Bár a természetes logaritmus fontosabb a bináris logaritmusnál a tiszta matematika számos területén, például a számelméletben és a matematikai elemzésben , a bináris logaritmusnak számos alkalmazása van a kombinatorikában :

• Minden bináris fa és n levelek rendelkezik magassága legalább log ₂  n , az egyenlőséggel, ha n egy ereje két és a fa egy teljes bináris fa . Ehhez kapcsolódóan a n mellékfolyókkal rendelkező folyórendszer Strahler -száma legfeljebb log ₂ n + 1 . 
• Minden családnak készletek az n különböző készletek legalább log ₂  n eleme a szakszervezet, az egyenlőség, ha a család egy áramfejlesztőt .
• Minden részleges kocka az n pontú izometrikus dimenziója legalább log ₂  n , és van a legtöbb 1/2 n log ₂  n élek, egyenlőséggel, ha a részkocka hiperkocka gráf .
• Szerint a Ramsey-tétel , minden n -vertex irányítatlan gráf van vagy egy klikk , vagy egy független halmaza méretű logaritmikus n . A garantálható pontos méret nem ismert, de a méretéről ismert legjobb határok a bináris logaritmusokat tartalmazzák. Különösen minden grafikonnak legalább klikkje vagy független mérete van1/2log ₂  n (1 - o (1)), és szinte minden grafikonon nincs klikk vagy független, 2 log ₂  n -nél nagyobb halmaz (1 + o (1)) .
• A véletlenszerű véletlenszerű keverések Gilbert – Shannon – Reeds modelljének matematikai elemzéséből kimutatható, hogy hányszor kell megkeverni egy n -kártyás pakli kártyát, riffle shuffles használatával , hogy a permutációkhoz hasonló eloszlást kapjunk. egyenletesen véletlenszerű, körülbelül3/2log ₂  n . Ez a számítás az alapja annak az ajánlásnak, hogy az 52 kártyás paklit hétszer kell megkeverni.

Számítási komplexitás

Bináris keresés rendezett tömbben, olyan algoritmus, amelynek időbeli összetettsége bináris logaritmusokat tartalmaz

A bináris logaritmus gyakran megjelenik az algoritmusok elemzésében is , nemcsak a bináris szám-aritmetika algoritmusokban való gyakori használata miatt, hanem azért is, mert a kétirányú elágazáson alapuló algoritmusok bináris logaritmusai fordulnak elő. Ha egy probléma kezdetben n választási lehetőséggel rendelkezik, és az algoritmus minden iterációja kétszeresére csökkenti a választások számát, akkor az egyetlen választás kiválasztásához szükséges ismétlések száma ismét a log ₂  n szerves része . Ezt az ötletet számos algoritmus és adatstruktúra elemzésére használják . Például a bináris keresésben a megoldandó feladat mérete minden iterációnál a felére csökken, ezért nagyjából log ₂  n iterációra van szükség ahhoz, hogy megoldást kapjunk az n méretű feladatra . Hasonlóképpen, egy tökéletesen kiegyensúlyozott , n elemet tartalmazó bináris keresési fa magassága log ₂ ( n + 1) - 1 .

Egy algoritmus futási idejét általában nagy O jelöléssel fejezik ki , amelyet a kifejezések egyszerűsítésére használnak az állandó tényezőik és az alacsonyabb rendű kifejezések kihagyásával. Mivel a különböző bázisú logaritmusok csak konstans tényezővel térnek el egymástól, az O (log ₂  n ) időben futó algoritmusokról is mondhatjuk, hogy mondjuk O (log ₁₃ n ) időben futnak . A logaritmus alapja olyan kifejezésekben, mint O (log n ) vagy O ( n log n ) , ezért nem fontos, és kihagyható. Azonban azoknak a logaritmusoknak az esetében, amelyek egy időkorlát kitevőjében jelennek meg, a logaritmus alapja nem hagyható ki. Például O (2 ^{log ₂  n} ) nem azonos O (2 ^{ln n} ) -vel, mert az előbbi egyenlő O ( n ) -vel , az utóbbi pedig O ^-val ( n ^{0,6931 ...} ) .

Az O ( n  log  n ) futási idejű algoritmusokat néha lineárisnak nevezik . Néhány példa az O (log n ) vagy O ( n log n ) futási idejű algoritmusokra :

• Átlagos időgyorsítás és más összehasonlító rendezési algoritmusok
• Keresés kiegyensúlyozott bináris keresési fákban
• Kifejezés négyzetekkel
• Leghosszabb növekvő alsorozat

Bináris logaritmusok is előfordulnak az osztási és meghódítási algoritmusok időhatárainak kitevőiben , például a Karatsuba algoritmus az n -bites számok O időben történő megszorzására ( n ^{log ₂  3} ) , és a Strassen algoritmus az n × n mátrixok idő O ( n ^{log ₂  7} ) . A bináris logaritmusok előfordulása ezekben a futási időkben a megosztás és hódítás ismétlődések mester tételére való hivatkozással magyarázható .

Bioinformatika

A microarray körülbelül 8700 géneket. Ezen gének expressziós arányát bináris logaritmusok segítségével hasonlítják össze.

A bioinformatika , microarray mérésére használjuk, hogy milyen erősen különböző gének vannak kifejezve a minta biológiai anyag. A gének különböző expressziós arányait gyakran összehasonlítják az expressziós arányok bináris logaritmusának használatával: két expressziós sebesség log arányát a két sebesség arányának bináris logaritmusaként határozzák meg. A bináris logaritmusok lehetővé teszik az expressziós arányok kényelmes összehasonlítását: a megduplázódott kifejezési sebesség leírható 1 -es logaránnyal, a felezett expressziós sebesség leírható -1 -es log -aránnyal , és változatlan kifejezési sebesség írható le egy például a nulla log arány.

Az így kapott adatpontokat gyakran scatterplotként jelenítjük meg, amelyben az egyik vagy mindkét koordináta -tengely az intenzitásviszonyok bináris logaritmusa, vagy olyan vizualizációkban, mint az MA -diagram és az RA -diagram, amelyek forgatják és méretezik ezeket a naplóarányos szórási diagramokat .

Zeneelmélet

A zeneelmélet , a intervallum vagy érzékelési különbség a két hallhatók aránya határozza meg a frekvenciájuk. A racionális számarányokból származó intervallumokat kis számlálókkal és nevezőkkel különösen eufonikusnak tartják. Ezen intervallumok közül a legegyszerűbb és legfontosabb az oktáv , a frekvenciaarány 2: 1 . A két hang közötti oktávok száma a frekvenciaarányuk bináris logaritmusa.

A hangolási rendszerek és a zeneelmélet egyéb aspektusainak tanulmányozásához , amelyek finomabb megkülönböztetést igényelnek a hangok között, hasznos, ha az intervallum méretét oktávnál finomabbnak tekintjük, és additív (a logaritmusok szerint), nem pedig multiplikatív (mint frekvencia) az arányok). Azaz, ha hangok x , y , és z formában emelkedő hangsor, majd az intézkedés az intervallum a x a y plusz az intézkedés az intervallum a y a z meg kell egyeznie az intézkedés az intervallum a x a z . Ilyen mértéket a cent ad , amely az oktávot 1200 egyenlő intervallumra osztja ( 12 félhang , egyenként 100 cent). Matematikailag adott hangot frekvenciákkal f ₁ és f ₂ , száma cent az intervallumot f ₁ és f ₂ jelentése

${\ displaystyle \ left | 1200 \ log _ {2} {\ frac {f_ {1}} {f_ {2}}} \ right |.}$

A millioctave ugyanúgy van definiálva, de 1200 helyett 1000 -es szorzóval .

Sportütemezés

Versenyjátékokban és sportokban, amelyekben minden játékban vagy mérkőzésen két játékos vagy csapat vesz részt, a bináris logaritmus azt jelzi, hogy hány forduló szükséges egy győztes meghatározásához szükséges egykieséses tornán . Például egy 4 játékosból álló bajnoksághoz log ₂  4 = 2 fordulóra van szükség a győztes meghatározásához, egy 32 csapatos tornához log ₂  32 = 5 fordulóra stb. Ebben az esetben n játékos/csapat esetében, ahol n nem hatalom a 2 -ből a log ₂  n -t fel kell kerekíteni, mivel szükség van legalább egy körre, amelyben nem minden megmaradt versenyző játszik. Például jelentkezzen ₂  6 megközelítőleg 2.585 , ami Kerekítést 3 , jelezve, hogy a bajnokság 6. csapatok igényel 3 kört (akár két csapat üljön ki az első körben, vagy az egyik csapat kiül a második fordulóban). Ugyanez a fordulószám szükséges a svájci rendszerű verseny egyértelmű győztesének meghatározásához .

Fényképezés

A fényképezés , expozíciós értékeket is mérik a bináris logaritmusa fény mennyisége eléri a film vagy érzékelő, összhangban Weber-törvény írja le logaritmikus összefüggést az emberi vizuális rendszer a fényre. Az expozíció egyetlen megállása egy egység a 2-es logaritmikus skálán. Pontosabban, a fénykép expozíciós értéke a következő

${\ displaystyle \ log _ {2} {\ frac {N^{2}} {t}}}$

ahol N az f-szám, amely a lencse rekesznyílását méri az expozíció során, és t az expozíció másodperceinek száma.

A bináris logaritmusokat (megállásként kifejezve) a denzitometriában is használják a fényérzékeny anyagok vagy digitális érzékelők dinamikus tartományának kifejezésére .

Számítás

TI SR-50 tudományos számológép (1974). Az ln és a log gombok a második sorban vannak; nincs log ₂  kulcs.

Átalakítás más bázisokból

Egy egyszerű módja annak, hogy számítani log ₂  n a számológépek , amelyek nem rendelkeznek a log ₂ funkció használatához a természetes logaritmus ( ln ), illetve a közös logaritmusát ( log vagy jelentkezzen ₁₀ ) funkciók, amelyek megtalálhatók a legtöbb tudományos számológép . A specifikus változása logaritmus alapja képletek a következők lehetnek:

${\ displaystyle \ log _ {2} n = {\ frac {\ ln n} {\ ln 2}} = {\ frac {\ log _ {10} n} {\ log _ {10} 2}},}$

vagy nagyjából

${\ displaystyle \ log _ {2} n \ kb 1,442695 \ nn \ kb 3,321928 \ log _ {10} n.}$

Egész szám kerekítése

A bináris logaritmus függvényekké alakítható egész számokból és egész számokból felfelé vagy lefelé kerekítve . Az egész bináris logaritmus két formáját a következő képlet kapcsolja össze:

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

A definíció meghatározással bővíthető . Bővített ily módon, ez a funkció kapcsolódik a számos vezető nullák a 32 bites, előjel nélküli bináris ábrázolása x , nlz ( x ) . ${\ displaystyle \ lfloor \ log _ {2} (0) \ rfloor = -1}$

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

Az egész bináris logaritmus úgy értelmezhető, mint a bemenet legjelentősebb 1 bitjének nulla alapú indexe . Ebben az értelemben a kereső első halmaz művelet kiegészítése, amely megtalálja a legkevésbé szignifikáns 1 bit indexét . Számos hardverplatform támogatja a vezető nullák számának megkeresését, vagy ezzel egyenértékű műveleteket, amelyek segítségével gyorsan megtalálható a bináris logaritmus. A flsés a flslfüggvények a Linux kernelben és a libc szoftverkönyvtár egyes verzióiban szintén kiszámítják a bináris logaritmust (egész számra kerekítve, plusz egy).

Iteratív közelítés

Általános pozitív valós szám esetén a bináris logaritmus két részből állhat. Először is, az egyik kiszámítja az egész részét , (az úgynevezett jellemző logaritmusát). Ez csökkenti a problémát olyanra, ahol a logaritmus argumentuma korlátozott tartományban van, az [1, 2] intervallum , egyszerűsítve a törtrész (a logaritmus mantrisa) kiszámításának második lépését. Bármely x > 0 esetén létezik egyedi n egész egész , amely 2 ⁿ ≤ x <2 ^{n +1} , vagy egyenértékű 1 ≤ 2 ^{- n} x <2 . Most a logaritmus egész része egyszerűen n , a törtrész pedig log ₂ (2 ^{- n} x ) . Más szavakkal: ${\ displaystyle \ lfloor \ log _ {2} x \ rfloor}$

${\ displaystyle \ log _ {2} x = n+\ log _ {2} y \ quad {\ text {where}} y = 2^{-n} x {\ text {és}} y \ in [1, 2)}$

Normalizált lebegőpontos számok esetén az egész részt a lebegőpontos kitevő adja meg, egész számoknál pedig a számláló első nullaművelet végrehajtásával.

Az eredmény tört része log ₂  y, és iteratív módon, csak elemi szorzás és osztás segítségével számítható ki. A törtrész kiszámításának algoritmusa pszeudokódban a következőképpen írható le :

1. Kezdje y valós számmal a félig nyitott intervallumban [1, 2) . Ha y = 1 , akkor az algoritmus kész, és a törtrész nulla.
2. Ellenkező esetben az y négyzetet többször ismételje, amíg a z eredmény a [2, 4) intervallumban van . Legyen m a szükséges négyzetek száma. Vagyis z = y ^{2 m} , m -et úgy választva, hogy z benne legyen a [2, 4] -ben .
3. Mindkét oldal logaritmusát figyelembe véve néhány algebrát:
   $${\ displaystyle {\ begin {aligned} \ log _ {2} z & = 2^{m} \ log _ {2} y \\\ log _ {2} y & = {\ frac {\ log _ {2} z } {2^{m}}} \\ & = {\ frac {1+ \ log _ {2} (z/2)} {2^{m}}} \\ & = 2^{-m}+ 2^{-m} \ napló _ {2} (z/2). \ Vége {igazítva}}}$$

   
4. Ismét z /2 egy valós szám az [1, 2) intervallumban . Térjen vissza az 1. lépéshez, és számítsa ki z /2 bináris logaritmusát ugyanezzel a módszerrel.

Ennek eredményét a következő rekurzív képletek fejezik ki, amelyekben az algoritmus i -edik iterációjában szükséges négyzetek száma szerepel : ${\ displaystyle m_ {i}}$

$${\ displaystyle {\ begin {aligned} \ log _ {2} x & = n+2^{-m_ {1}} \ left (1+2^{-m_ {2}} \ left (1+2^{ -m_ {3}} \ bal (1+ \ cdots \ jobb) \ jobb) \ jobb) \\ & = n+2^{-m_ {1}}+2^{-m_ {1} -m_ {2 }}+2^{-m_ {1} -m_ {2} -m_ {3}}+\ cdots \ end {aligned}}}$$

Abban az esetben, ha az 1. lépés törtrésze nulla, ez egy véges szekvencia, amely egy ponton véget ér. Ellenkező esetben, ez egy végtelen sorozat , hogy konvergál szerinti arány vizsgálata , mivel minden egyes kifejezés szigorúan kisebb, mint az előző (mivel minden m _i > 0 ). A gyakorlati felhasználás érdekében ezt a végtelen sorozatot le kell csonkolni, hogy megközelítő eredményt érjünk el. Ha a sorozat az i -edik tag után le van csonkolva , akkor az eredmény hibája kisebb, mint 2 ^{-( m ₁ + m ₂ + ⋯ + m _i )} .

Szoftvertár támogatása

A log2függvény szerepel a standard C matematikai függvényekben . Ennek a függvénynek az alapértelmezett verziója kettős pontosságú argumentumokat tartalmaz, de változatai lehetővé teszik az argumentum egyszeri pontosságát vagy hosszú dupláját . Komplex számokat és implicit típuskonverziót támogató számítási környezetekben , mint például a MATLAB , a log2függvény argumentuma negatív szám lehet , és összetett számot ad vissza.

Hivatkozások

Külső linkek

• Weisstein, Eric W. , "Bináris logaritmus" , MathWorld
• Anderson, Sean Eron (2003. december 12.), "Keresse meg egy N-bites egész szám napló alapját az O (lg (N)) műveletekben" , Bit Twiddling Hacks , Stanford University , letöltve 2015-11-25
• Feynman és a csatlakozógép