Binäärinen logaritmi

Binäärisen logaritmifunktion y = log₂ x kuvaaja

Binäärinen logaritmi eli kaksikantainen logaritmi (log₂ 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

Leonhard Euler oli vuonna 1739 ensimmäinen, joka sovelsi binääristä logaritmia musiikin teoriaan.

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 log₂ 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 log₁₀ 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

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

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

16 pelaajan turnausta esittävä kaavio, jolla on binääripuun rakenne. Puun korkeus (kierrosten määrä turnauksessa) on sama kuin pelaajien lukumäärän binäärinen logaritmi, jos pelaajien lukumäärä on kahden potenssi, muussa tapauksessa suurempi.

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:

• Jokaisen binääripuun, jossa on n lehteä, korkeus on $\log _{2}n$, ja se on tasan 2, jos n on kahden potenssi.
• Jokaisen sellaisen joukkoperheen unionissa, johon sisältyy n eri joukkoa, on vähintään $\log _{2}n$ alkiota, ja niitä on tasan $\log _{2}n$, jos joukkoperhe on potenssijoukko.
• Jokaisen sellaisen osittaiskuution isometrinen dimensio, jossa on n kärkeä, on vähintään $\log _{2}n$, ja sillä on enintään ${\frac {1}{2}}n\log _{2}n$ kärkeä, tasan näin monta silloin, kun osittaiskuutio on hyperkuutiograafi.

Laskennallinen monimutkaisuus

Binäärihaku järjestetyssä taulukossa on algoritmi, jonka ajallinen monimutkaisuus on laskettavissa binäärisillä logaritmeilla.

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 log₂ 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 log₂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 log₂ n + 1.

Algoritmien suoritusaika ilmaistaan kuitenkin tavallisesti iso O -merkinnällä, jossa vakiotekijät jätetään pois. Koska log₂ n = (log_k n)/(log_k 2), missä k voi olla mikä tahansa yhtä suurempi luku, algoritmien, jotka voidaan suorittaa ajassa O(log₂ n), voidaan myös sanoa olevan suoritettavissa esimerkiksi ajassa O(log₁₃ 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(2^log₂ n) ei ole sama kuin O(2^ln 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:

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

Bioinformatiikka

Mikroruudukko, joka kuvaa suunnilleen 8700 geenin sisällön. Näiden geenien suhteelliset informaatiomäärät voidaan ilmoittaa binääristen logaritmien avulla.

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₁ ja f₂, niiden välisen intervallin suuruus sentteinä on

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

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₂(4) = 2 kierrosta, ja jos joukkueita on 32, kierroksia tarvitaan log₂(32) = 5 ja niin edelleen. Jos pelaajien tai joukkueiden lukumäärä n ei ole kahden potenssi, log₂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₂(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

$\log _{2}{\frac {N^{2}}{t}}$ missä $N$ on linssin valotusaukkoa valotuksen aikana mittaava f-luku ja $t$ 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

TI SR-50, tieteellinen laskin vuodelta 1974. Toisella rivillä ovat ln- ja log-näppäintä; log₂-näppäintä ei ole.

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:

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

tai likimäärin

$\log _{2}n\approx 1.442695\ln n\approx 3.321928\log _{10}n.$

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ä:

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

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ä $\lfloor \log _{2}(0)\rfloor =-1$. Saatu funktio on:

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

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 fls ja flsl 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:

1. lasketaan sen kokonaisosa, $\lfloor \log _{2}x\rfloor$, jota sanotaan logaritmin mantissaksi
2. lasketaan sen kokonaisluvun ylittävä osa, jota sanotaan logaritmin karakteristikaksi.

Kokonaisosan laskenta on suoraviivaista. Jokaista lukua x > 0, kohti on yksi ja vain yksi sellainen kokonaisluku n, että 2ⁿ ≤ x < 2ⁿ⁺¹, tai yhtäpitävästi 1 ≤ 2⁻ⁿx < 2. Logaritmin kokonaisosa on yksinkertaisesti n, ja desimaaliosa on log₂(2⁻ⁿx). Toisin sanoen:

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

Tuloksen kokonaisluvun ylittävä osa on $\log _{2}y$, ja se voidaan laskea rekursiivisesti pelkkien kerto- ja jakolaskujen avulla. Tämä käy päinsä seuraavasti:

1. Aloitetaan edellä saadusta reaaliluvusta $y\in [1,2)$ Jos $y=1$, lasku on valmis ja kokonaisluvun ylittävä osa on nolla.
2. Muussa tapauksessa $y$ korotetaan toistuvasti neliöön, kunnes tuloksena saadaan $z\in [2,4)$. Olkoon $z\in [2,4)$.
3. Otetaan molemmista puolista logaritmi ja suoritetaan seuraavat algebralliset toimitukset:

   ${\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}\log _{2}(z/2)\end{aligned}}$

4. Nyt $z/2$ on jälleen reaaliluku välillä $[1,2)$. Palataan kohtaan 1 ja lasketaan $z/2$ binäärinen logaritmi samalla menetelmällä rekursiivisesti.

Tämän tuloksen osoittavat seuraavat kaavat, joissa $m_{i}$ on tarvittavien neliöön korotusten lukumäärä algoritmin i:nnellä rekursiokerralla:

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

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 $m_{i}>0$). 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 $2^{-(m_{1}+m_{2}+\cdots +m_{i})}$.

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 log2, 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.

Aiheesta muualla

• Binary Logarithm Wolfram Math World. Viitattu 2.3.2015.