Binäärinen logaritmi

**Binäärinen logaritmi** eli **kaksikantainen logaritmi** (log2&nbsp;*n*) on logaritmi, jonka kantaluku on 2. Se on funktion y = 2^x käänteisfunktio ja osoittaa, mihin potenssiin luku 2 on korotettava, jotta saadaan annettu luku. Toisin sanoen:
:y=\log_2 x \quad\Longleftrightarrow\quad 2^y=x.
Esimerkiksi luvun 1 binäärinen logaritmi on 0, luvun 2 binäärinen logaritmi on 1, luvun 4 binäärinen logaritmi on 2, luvun 8 binäärinen logaritmi on 3 ja luvun 16 binäärinen logaritmi 4.

Binäärinen logaritmi liittyy läheisesti binääri­luku­järjestelmään. Historiallisesti ensimmäinen binäärisen logaritmin sovellusala oli kuitenkin musiikin teoria, johon sitä sovelsi Leonhard Euler. Muita aloja, joissa binääristä logaritmia paljon käytetään, ovat informaatioteoria, kombinatoriikka, tietojenkäsittelytiede, bioinformatiikka, urheilukilpailujen suunnittelu ja valokuvaus.

## Historia

Michael Stifel julkaisi vuonna 1544 kahden potensseista taulukon, jota voidaan sen rivit kääntämällä käyttää myös binääristen logaritmien taulukkona. Binääristen logaritmien sovellukset musiikin teoriassa esitti Leonhard Euler vuonna 1739, kauan ennen kuin nyky­aikainen informaatio­teoria ja tietojen­käsittely­tiede saivat alkunsa. Osana tätä alaa koskevasta tutkimuksestaan Euler laati taulukon kokonaislukujen 1...8 binäärisistä logaritmeista seitsemän desimaalin tarkkuudella.

## Merkintätavat
Matematiikassa luvun *n* binäärinen logaritmi merkitään log2&nbsp;*n*. Varsinkin sovellusaloilla sille kuitenkin käytetään tai on ehdotettu useita muitakin merkintätapoja.

Joskus binääriselle logaritmille käytetään merkintää **lg ''n***. [[Donald Knuth]] on väittänyt tätä merkintää [[Edward Reingold]]in keksimäksi, mutta sitä on käytetty sekä informaatio­teoriassa että tietojen­käsittely­tieteessä jo ennen Reingoldia. Joissakin teoksissa binäärinen logaritmi on merkitty myös *'log *n***, sen jälkeen kun on sanottu, että jäljempänä logaritmien oletuskantaluku on 2.

Toinen varsinkin saksankielisessä kirjallisuudessa usein esiintyvä merkintä samalle funktiolle on **ld *n***, joka tulee sen [[latina]]laisesta nimityksestä ''logarithmus duālis''. [[ISO|ISO:n]] standardien [[ISO 31-11]] ja [[ISO 80000-2]] mukaan se tulisi merkitä **lb *n**'; kun taas lg *n* merkitsee luvun *n* kymmenkantaista eli [[Briggsin logaritmi]]a log<sub>10</sub> *n*. Tämä ISO:n suosittelema binäärisen logaritmin merkintä ei kuitenkaan ole tullut yleiseen käyttöön.

== Sovelluksia ==

=== Informaatioteoria ===

Numeroiden ([[bitti]]en) lukumäärä positiivisen kokonaisluvun *n* [[binääriluku|binääriesityksessä]] on luvun *n* binäärisen logaritmin kokonaisosa lisättynä yhdellä, toisin sanoen 

:<math> \lfloor \log_2 n\rfloor + 1. \, </math>

Informaatioteoriassa [[informaatiosisällön]] ja [[informaatioentropia]]n määritelmät esitetään usein binäärisen logaritmin avulla, mikä vastaa bitin merkitystä informaation perusyksikkönä. Joskus ne kuitenkin määritellään [[luonnollinen logaritmi|luonnollisen logaritmin]] avulla, jolloin informaation yksikkönä on [[nat (yksikkö)|nat]].

===Kombinatoriikka===

Vaikka [[luonnollinen logaritmi]] on binääristä logaritmia tärkeämpi monilla puhtaan matematiikan aloilla kuten [[lukuteoria]]ssa ja [[matemaattinen analyysi|matemaattisessa analyysissä]], binäärisellä logaritmilla on useita sovelluksia [[kombinatoriikka|kombinatoriikassa]]:
*Jokaisen [[binääripuu]]n, jossa on *n* lehteä, korkeus on <math>\log_2 n</math>, ja se on tasan 2, jos *n* on kahden potenssi.
*Jokaisen sellaisen [[joukkoperhe]]en [[Yhdiste (matematiikka)|unionissa]], johon sisältyy *n* eri joukkoa, on vähintään <math>\log_2 n</math> alkiota, ja niitä on tasan <math>\log_2 n</math>, jos joukkoperhe on [[potenssijoukko]].
*Jokaisen sellaisen [[osittaiskuutio]]n isometrinen dimensio, jossa on *n* kärkeä, on vähintään <math>\log_2 n</math>, ja sillä on enintään <math>\frac{1}{2}n\log_2 n</math> kärkeä, tasan näin monta silloin, kun osittaiskuutio on [[hyperkuutiograafi]].


===Laskennallinen monimutkaisuus===

Binäärinen logaritmi esiintyy usein myös [[algoritmi]]en analyysissä, ei vain siksi, koska niissä usein käytetään binäärilukujen aritmetiikkaan, vaan myös koska binäärisiin logaritmeihin päädytään analysoitaessa kahtia haarautuvia algoritmeja. Jos tehtävällä on alun perin *n* ajateltavissa olevaa ratkaisua ja joka kerta, kun algoritmin tietty osa toistetaan, mahdollisuuksien lukumäärä puoliintuu, toistojen lukumäärä yhteen yksikäsitteiseen ratkaisuun päätymiseksi on jälleen log<sub>2</sub>&nbsp;*n*:n kokonaisosa. Tätä ajatusta käytetään useita algoritmeja ja [[tietorakenne|tietorakenteita]] analysoitaessa. Esimerkiksi [[binäärihaku|binäärihaussa]] ratkaistavan tehtävän laajuus puoliintuu jokaisella toistokerralla ja sen vuoksi puolitus on toistettava suunnilleen log<sub>2</sub>*n*, ennen kuin päädytään koon 1 tehtävään, joka ratkeaa helposti vakioajassa. Samaan tapaan sellaisen täydellisesti tasapainotetun [[binääripuuhaku|binääripuuhaun]], jossa on *n* alkiota, korkeus on log<sub>2</sub>&nbsp;*n*&nbsp;+&nbsp;1.

Algoritmien suoritusaika ilmaistaan kuitenkin tavallisesti iso O -merkinnällä, jossa vakiotekijät jätetään pois.
Koska log<sub>2</sub> *n* = (log<sub>*k*</sub>&nbsp;*n*)/(log<sub>*k*</sub>&nbsp;2), missä *k* voi olla mikä tahansa yhtä suurempi luku, algoritmien, jotka voidaan suorittaa ajassa *O*(log<sub>2</sub>&nbsp;*n*), voidaan myös sanoa olevan suoritettavissa esimerkiksi ajassa *O*(log<sub>13</sub>&nbsp;*n*). Logaritmin kantaluku sen tapaisissa lausekkeissa kuin *O*(log&nbsp;*n*) tai *O*(*n*&nbsp;log&nbsp;*n*) ei sen vuoksi ole merkityksellinen. Muissa yhteyksissä logaritmin kantaluku on kuitenkin määritettävä. Esimerkiksi *O*(2<sup>log<sub>2</sub>&nbsp;*n*</sup>) ei ole sama kuin *O*(2<sup>ln&nbsp;*n*</sup>), koska edellinen on yhtä kuin *O*(*n*) ja jälkimmäinen yhtä kuin *O*(*n*<sup>0.6931...</sup>).

Algoritmeja, joiden suoritusaika on *O*(*n*&nbsp;log&nbsp;*n*), sanotaan joskus [[linearitminen|linearitmisiksi]]. Joitakin esimerkkejä algoritmeista, joiden suoritusaika on *O*(log&nbsp;*n*) tai *O*(*n*&nbsp;log&nbsp;*n*) ovat:

*[[pikalajittelu]] keskimääräisessä ajassa ja muut vertailulajittelualgoritmit
*Haku tasa­painotetusta [[binäärihakupuusta]]
*Potenssiin korotus neliöimällä
*Pisin kasvava alijono



===Bioinformatiikka===

[[Bioinformatiikka|Bioinformatiikassa]] [[Mikroruudukko|mikro­ruudukoita]] analysoitaessa geenien sisältämän informaation määriä vertaillaan usein informaatio­määrien suhteen binäärisen logaritmin avulla. Käyttämällä logaritmille kanta­lukua&nbsp;2 esimerkiksi kaksinkertainen informaatio­sisältö vastaa logaritmien erotusta 1, puoliintunut informaatio­sisältö voidaan ilmaista logaritmien erotuksella -1, ja muuttumattomana pysynyt sisältö logaritmien erotusta 0. Tällä tavalla saadut datapisteet visualisoidaan usein [[pistekaavio]]lla, jossa jompikumpi tai molemmat koordinaattiakselit ovat binäärisiä [[logaritminen asteikko|logaritmisia asteikkoja]]. 

===Musiikin teoria===
[[Musiikin teoria]]ssa kahden sävelen välisen havaittavan eron eli [[intervalli]]n määrittelee niiden [[taajuus|taajuuksien]] suhde. Kun tämä suhde on ilmaistavissa [[murtoluku|murto­luvulla]], jonka osoittaja ja nimittäjä ovat pieniä lukuja, sävelet sointuvat hyvin yhteen eli kyseessä on [[konsonanssi]]. Yksin­kertaisin ja tärkein tällainen intervalli on [[oktaavi]], jossa taajuuksien suhde on 2:1. Kaksi säveltä ovat niin monen oktaavin päässä toisistaan kuin niiden taajuuksien suhteen binäärinen logaritmi osoittaa.

[[Viritysjärjestelmä|Viritys­järjestelmiä]] ja muita musiikin teorian piirteitä tutkittaessa tarvitaan usein tarkempia lukuarvoja sävelten korkeuserolle. Tällöin on edullista käyttää intervallille mittaa, joka on tarkempi kuin oktaavi ja joka on logaritmien tavoin additiivinen eikä multi­plika­tiivinen, jollainen taajuuksien suhde on. Toisin sanoen jos sävelet muodostavat nousevan säveljonon, sävelten *x* ja *y* sekä sävelten *y* ja *z* välisten intervallien mitta­lukujen summan tulisi olla sama kuin sävelten *x* ja *y* välisen intervallin mittaluku. Eräs sellainen mitta­yksikkö on [[sentti (musiikki)|sentti]], joka on [[tasaviritys|tasa­vireisen]] [[puoliaskel]]een sadasosa eli 1/1200 oktaavia.  Jos sävelten taajuudet ovat 
*f*<sub>1</sub> ja *f*<sub>2</sub>, niiden välisen intervallin suuruus sentteinä on
:<math>\left|1200\log_2\frac{f_1}{f_2}\right|.</math>
[[Millioktaavi]] määritellään muutoin samalla tavalla, mutta kertoimen 1200 sijasta käytetään kerrointa 1000.

===Urheilukilpailujen ajoitus===
Kilpailupeleissä ja urheilulajeissa, joissa kuhunkin otteluun osallistuu kaksi kilpailijaa tai joukkueita, binäärinen logaritmi ilmoittaa niiden kierrosten lukumäärän, joka pudotuspelissä on käytävä, ennen kuin loppuottelussa selviää koko kilpailun voittaja. Jos esimerkiksi pelaajia on 4, voittajan selvittämiseksi tarvitaan log<sub>2</sub>(4)&nbsp;=&nbsp;2 kierrosta, ja jos joukkueita on 32, kierroksia tarvitaan log<sub>2</sub>(32)&nbsp;=&nbsp;5 ja niin edelleen. Jos pelaajien tai joukkueiden lukumäärä *n* ei ole kahden potenssi, log<sub>2</sub>*n* on pyöristettävä ylöspäin kokonaisluvuksi, sillä tarvitaan ainakin yksi kierros, johon eivät kaikki jäljellä olevat kilpailijat osallistu. Esimerkiksi log<sub>2</sub>(6) on noin 2,585, ylöspäin pyöristettynä 3, mikä osoittaa, että jos kilpailuun osallistuu 6 joukkuetta, joko niistä kaksi ei ole mukana ensimmäisellä kierroksella tai yksi ei osallistu toiselle kierrokselle. Sama lukumäärä kierroksia tarvitaan myös voittajan ratkaisemiseksi [[sveitsiläinen järjestelmä|sveitsiläisessä järjestelmässä]].

===Valokuvaus===
[[Valokuvaus|Valokuvauksessa]] [[valotusarvo]]t mitataan filmiin tai sensoriin osuvan valomäärän binäärisenä logaritmina, mikä perustuu [[Weberin–Fechnerin laki]]in, jonka mukaan ihmisen silmä reagoi valomäärään logaritmisesti. Valotukselle käytetäänkin kaksikantaista logaritmista asteikkoa Täsmällisemmin sanottuna valokuvan valotusarvon on 
:<math>\log_2 \frac{N^2}{t}</math> missä <math>N</math> on linssin [[valotusaukko]]a valotuksen aikana mittaava [[f-luku]] ja <math>t</math> valotusaika sekunteina.

Binäärisiä logaritmeja käytetään myös [[densitometria]]ssa, ilmaisemaan suurimman ja pienimmän valo­määrän suhdetta, jolla valoherkkä materiaali tai digitaalinen sensori on käyttö­kelpoinen.

==Binäärisen logaritmin laskenta==

Nykyaikaisissa [[Laskin|laskimissa]] on yleensä näppäimet [[luonnollinen logaritmi|luonnollisen]] ja [[Briggsin logaritmi]]n, mutta ei binäärisen logaritmin laskemiseksi. Näiden avulla voidaan kuitenkin myös binäärinen logaritmi laskea käyttämällä [[logaritmijärjestelmä|logaritmi­järjestelmien]] välisiä muunnoskaavoja:

:<math>\log_2 n = \frac{\ln n}{\ln 2} = \frac{\log_{10} n}{\log_{10} 2},</math>
tai likimäärin 
:<math>\log_2 n \approx 1.442695\ln n \approx 3.321928\log_{10} n.</math>

===Pyöristys kokonaisluvuksi===
Binäärinen logaritmi voidaan muotoilla funktioksi kokonaisluvuilta kokonaisluvuille [[pyöristys|pyöristämällä]] se ylös tai alas. Nämä kaksi kokonaislukuarvoista binääristä logaritmia liittyvät toisiinsa seuraavan kaavan välityksellä:

:<math> \lfloor \log_2(n) \rfloor = \lceil \log_2(n + 1) \rceil - 1, \text{ if }n \ge 1.</math> 
 Näin laajennettuna funktio liittyy läheisesti etunollien lukumäärään *x*:n etumerkittömässä binääriesityksessä nlz(*x*).
Määritelmää voidaan laajentaa sopimalla, että <math> \lfloor \log_2(0) \rfloor = -1</math>. Saatu funktio on: 
:<math>\lfloor \log_2(n) \rfloor = 31 - \operatorname{nlz}(n).</math>

Kokonaislukuarvoinen binäärinen logaritmi voidaan tulkita syötteen tärkeimmän arvon 1 saaneen bitin järjestysluvuksi, kun numerointi aloitetaan nollasta.  Monet laitteistoalustat tukevat etunollien lukumäärän laskemista tai vastaavia laskutoimituksia, joiden avulla voidaan nopeasti määrittää binäärinen logaritmi. [[Linux-ydin|Linux-ytimessä]] ja joissakin [[libc]]-ohjelmistokirjaston versioissa funktiot <code>fls</code> ja <code>flsl</code> laskevat myös binäärisen logaritmin pyöristettynä ylöspäin kokonaisluvuksi, johon lisätään yksi.

===Rekursiivinen likiarvon laskenta===

Positiivisen reaaliluvun binäärinen logaritmi voidaan laskea kahdessa vaiheessa:
# lasketaan sen kokonaisosa, <math>\lfloor\log_2 x\rfloor</math>, jota sanotaan logaritmin *mantissaksi*
# lasketaan sen kokonaisluvun ylittävä osa, jota sanotaan logaritmin *karakteristikaksi*.

Kokonaisosan laskenta on suoraviivaista. Jokaista lukua *x*&nbsp;>&nbsp;0, kohti on yksi ja vain yksi sellainen kokonaisluku *n*, että 2<sup>*n*</sup>&nbsp;≤&nbsp;*x*&nbsp;<&nbsp;2<sup>*n*+1</sup>, tai yhtäpitävästi 1&nbsp;≤&nbsp;2<sup>&minus;*n*</sup>*x*&nbsp;<&nbsp;2.  Logaritmin kokonaisosa on yksinkertaisesti *n*, ja desimaaliosa on log<sub>2</sub>(2<sup>&minus;*n*</sup>*x*).  Toisin sanoen:

:<math>\log_2 x = n + \log_2 y \quad\text{where } y = 2^{-n}x \text{ and } y \in [1,2)</math>

Tuloksen kokonaisluvun ylittävä osa on  <math>\log_2 y</math>, ja se voidaan laskea [[rekursio|rekursiivisesti]] pelkkien kerto- ja jakolaskujen avulla. Tämä käy päinsä seuraavasti:
# Aloitetaan edellä saadusta reaaliluvusta <math>y \in [1,2)</math>  Jos <math>y=1</math>, lasku on valmis ja kokonaisluvun ylittävä osa on nolla.
# Muussa tapauksessa <math>y</math> korotetaan toistuvasti neliöön, kunnes tuloksena saadaan <math>z \in [2,4)</math>. Olkoon <math>z \in [2,4)</math>.
# Otetaan molemmista puolista logaritmi ja suoritetaan seuraavat algebralliset toimitukset:
#:<math>\begin{align}
\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}\log_2(z/2)
\end{align}</math>
# Nyt <math>z/2</math> on jälleen reaaliluku välillä <math>[1,2)</math>. Palataan kohtaan 1 ja lasketaan <math>z/2</math> binäärinen logaritmi samalla menetelmällä rekursiivisesti.

Tämän tuloksen osoittavat seuraavat kaavat, joissa <math>m_i</math> on tarvittavien neliöön korotusten lukumäärä
algoritmin *i*:nnellä rekursiokerralla:
:<math>\begin{align}
\log_2 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{align}</math>

Siinä erikoistapauksessa, että kokonaisluvun ylittävä osa kohdassa 1 osoittautuu nollaksi, kyseessä on *äärellinen* sarja, joka päättyy joskus. Muussa tapauksessa kyseessä on [[päättymätön sarja]], joka [[suppeneminen|suppenee]], sillä jokainen termi on aidosti pienempi kuin edellinen (sillä jokainen  <math>m_i>0</math>). Käytännössä tämä ääretön sarja on katkaistava jossakin kohdassa, jolloin saadaan sopiva likiarvo. Jos sarja katkaistaan *i*:nnen termin jälkeen, tuloksen virhe on pienempi kuin <math>2^{-(m_1+m_2+\cdots+m_i)}</math>.

Vaihtoehtoinen algoritmi, joka tuottaa jokaisella toistokerralla yhden bitin lisää käyttämällä vaihto- ja vertailuoperaatiota, on myös mahdollinen.

=== Tuki aliohjelmakirjastoissa ===
[[C (ohjelmointikieli)|C]]-ohjelmointikielen standardin mukaiseen matemaattisten funktioiden kirjastoon sisältyy funktio <code>log2</code>, joka laskee annetun luvun binäärisen logaritmin. Oletusarvoisesti funktio laskee logaritmin [[kaksoistarkkuus]]argumentille, mutta sen jotkin versiot sallivat argumentille yksinkertaisen tarkkuuden tai se voi olla myös *long double''.

 

## Lähteet

## Aiheesta muualla
*