Binäärinen logaritmi

Binäärinen logaritmi eli kaksikantainen logaritmi (log2 "n") on logaritmi, jonka kantaluku on 2. Se on funktion formula_1 käänteisfunktio ja osoittaa, mihin potenssiin luku 2 on korotettava, jotta saadaan annettu luku. Toisin sanoen:
formula_2
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 "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 Reingoldin 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 latinalaisesta nimityksestä "logarithmus duālis". 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 logaritmia log10 "n". Tämä ISO:n suosittelema binäärisen logaritmin merkintä ei kuitenkaan ole tullut yleiseen käyttöön.
Sovelluksia.
Informaatioteoria.
Numeroiden (bittien) lukumäärä positiivisen kokonaisluvun "n" binääriesityksessä on luvun "n" binäärisen logaritmin kokonaisosa lisättynä yhdellä, toisin sanoen 
formula_3
Informaatioteoriassa informaatiosisällön ja informaatioentropian määritelmät esitetään usein binäärisen logaritmin avulla, mikä vastaa bitin merkitystä informaation perusyksikkönä. Joskus ne kuitenkin määritellään luonnollisen logaritmin avulla, jolloin informaation yksikkönä on nat.
Kombinatoriikka.
Vaikka luonnollinen logaritmi on binääristä logaritmia tärkeämpi monilla puhtaan matematiikan aloilla kuten lukuteoriassa ja matemaattisessa analyysissä, binäärisellä logaritmilla on useita sovelluksia kombinatoriikassa:
Laskennallinen monimutkaisuus.
Binäärinen logaritmi esiintyy usein myös algoritmien 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 log2 "n":n kokonaisosa. Tätä ajatusta käytetään useita algoritmeja ja tietorakenteita analysoitaessa. Esimerkiksi binäärihaussa ratkaistavan tehtävän laajuus puoliintuu jokaisella toistokerralla ja sen vuoksi puolitus on toistettava suunnilleen log2"n", ennen kuin päädytään koon 1 tehtävään, joka ratkeaa helposti vakioajassa. Samaan tapaan sellaisen täydellisesti tasapainotetun binääripuuhaun, jossa on "n" alkiota, korkeus on log2 "n" + 1.
Algoritmien suoritusaika ilmaistaan kuitenkin tavallisesti iso O -merkinnällä, jossa vakiotekijät jätetään pois.
Koska log2 "n" = (log"k" "n")/(log"k" 2), missä "k" voi olla mikä tahansa yhtä suurempi luku, algoritmien, jotka voidaan suorittaa ajassa "O"(log2 "n"), voidaan myös sanoa olevan suoritettavissa esimerkiksi ajassa "O"(log13 "n"). Logaritmin kantaluku sen tapaisissa lausekkeissa kuin "O"(log "n") tai "O"("n" log "n") ei sen vuoksi ole merkityksellinen. Muissa yhteyksissä logaritmin kantaluku on kuitenkin määritettävä. Esimerkiksi "O"(2log2 "n") ei ole sama kuin "O"(2ln "n"), koska edellinen on yhtä kuin "O"("n") ja jälkimmäinen yhtä kuin "O"("n"0.6931...).
Algoritmeja, joiden suoritusaika on "O"("n" log "n"), sanotaan joskus linearitmisiksi. Joitakin esimerkkejä algoritmeista, joiden suoritusaika on "O"(log "n") tai "O"("n" log "n") ovat:
Bioinformatiikka.
Bioinformatiikassa 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 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 pistekaaviolla, jossa jompikumpi tai molemmat koordinaattiakselit ovat binäärisiä logaritmisia asteikkoja. 
Musiikin teoria.
Musiikin teoriassa kahden sävelen välisen havaittavan eron eli intervallin määrittelee niiden taajuuksien suhde. Kun tämä suhde on ilmaistavissa 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.
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, joka on tasa­vireisen puoliaskeleen sadasosa eli 1/1200 oktaavia. Jos sävelten taajuudet ovat 
"f"1 ja "f"2, niiden välisen intervallin suuruus sentteinä on
formula_9
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 log2(4) = 2 kierrosta, ja jos joukkueita on 32, kierroksia tarvitaan log2(32) = 5 ja niin edelleen. Jos pelaajien tai joukkueiden lukumäärä "n" ei ole kahden potenssi, log2"n" on pyöristettävä ylöspäin kokonaisluvuksi, sillä tarvitaan ainakin yksi kierros, johon eivät kaikki jäljellä olevat kilpailijat osallistu. Esimerkiksi log2(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äisessä järjestelmässä.
Valokuvaus.
Valokuvauksessa valotusarvot mitataan filmiin tai sensoriin osuvan valomäärän binäärisenä logaritmina, mikä perustuu Weberin–Fechnerin lakiin, jonka mukaan ihmisen silmä reagoi valomäärään logaritmisesti. Valotukselle käytetäänkin kaksikantaista logaritmista asteikkoa Täsmällisemmin sanottuna valokuvan valotusarvon on 
formula_10 missä formula_11 on linssin valotusaukkoa valotuksen aikana mittaava f-luku ja formula_12 valotusaika sekunteina.
Binäärisiä logaritmeja käytetään myös densitometriassa, 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 laskimissa on yleensä näppäimet luonnollisen ja Briggsin logaritmin, mutta ei binäärisen logaritmin laskemiseksi. Näiden avulla voidaan kuitenkin myös binäärinen logaritmi laskea käyttämällä logaritmi­järjestelmien välisiä muunnoskaavoja:
formula_13
tai likimäärin 
formula_14
Pyöristys kokonaisluvuksi.
Binäärinen logaritmi voidaan muotoilla funktioksi kokonaisluvuilta kokonaisluvuille pyöristämällä se ylös tai alas. Nämä kaksi kokonaislukuarvoista binääristä logaritmia liittyvät toisiinsa seuraavan kaavan välityksellä:
formula_15 
 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ä formula_16. Saatu funktio on: 
formula_17
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-ytimessä ja joissakin libc-ohjelmistokirjaston versioissa funktiot codice_1 ja codice_2 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:
Kokonaisosan laskenta on suoraviivaista. Jokaista lukua "x" &gt; 0, kohti on yksi ja vain yksi sellainen kokonaisluku "n", että 2"n" ≤ "x" &lt; 2"n"+1, tai yhtäpitävästi 1 ≤ 2−"n""x" &lt; 2. Logaritmin kokonaisosa on yksinkertaisesti "n", ja desimaaliosa on log2(2−"n""x"). Toisin sanoen:
formula_19
Tuloksen kokonaisluvun ylittävä osa on formula_20, ja se voidaan laskea rekursiivisesti pelkkien kerto- ja jakolaskujen avulla. Tämä käy päinsä seuraavasti:
Tämän tuloksen osoittavat seuraavat kaavat, joissa formula_30 on tarvittavien neliöön korotusten lukumäärä
algoritmin "i":nnellä rekursiokerralla:
formula_31
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 suppenee, sillä jokainen termi on aidosti pienempi kuin edellinen (sillä jokainen formula_32). 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 formula_33.
Vaihtoehtoinen algoritmi, joka tuottaa jokaisella toistokerralla yhden bitin lisää käyttämällä vaihto- ja vertailuoperaatiota, on myös mahdollinen.
Tuki aliohjelmakirjastoissa.
C-ohjelmointikielen standardin mukaiseen matemaattisten funktioiden kirjastoon sisältyy funktio codice_3, joka laskee annetun luvun binäärisen logaritmin. Oletusarvoisesti funktio laskee logaritmin kaksoistarkkuusargumentille, mutta sen jotkin versiot sallivat argumentille yksinkertaisen tarkkuuden tai se voi olla myös "long double".