Tietokonepalsta: Kuinka Fibonaccin lukuja lasketaan

Solmun tietokonepalstalla tutkitaan, mitä tekemistä matematiikalla ja tietotekniikalla on keskenään. Ensimmäisenä tulee varmaan mieleen tietokoneiden käyttö laskennassa ja visualisoinnissa, siis tietotekniikan soveltaminen matematiikkaan. Alojen syvempää yhteyttä valottaa se, miten matematiikkaa käytetään tietotekniikassa. Sitä esittelee tämä ensimmäinen osa.

Algoritmi

Tällä kertaa tutkitaan yhden esimerkin avulla algoritmin käsitettä sekä hieman siihen liittyvää matematiikkaa. Algoritmi on lyhyesti sanottuna "resepti", jonka avulla tietokone osaa suorittaa jonkin tehtävän, esimerkiksi järjestää joukon lukuja tai valita tekstikappaleen rivinvaihdot niin, että tulos on jonkin kriteerin mielessä optimaalinen. Algoritmin toteuttaa yleensä tietokoneohjelma tai ohjelman osa, mutta ei millainen tahansa: vaadimme, että ohjelma pysähtyy ja antaa oikean tuloksen. (Tämän määritelmän mukaan esimerkiksi ydinvoimalan valvontaohjelma ei välttämättä toteuta mitään algoritmia, sillä sen ei kuulu pysähtyä eikä tuottaa mitään lopputulosta vaan vastata ärsykkeisiin järkevällä tavalla. Kuitenkin se luultavasti sisältää algoritmeja: esimerkiksi yksi sen aliohjelma saattaisi tutkia, antavatko reaktorista saadut mittaukset aihetta hälytykseen.)

Tämän artikkelin ymmärtämiseksi lukijan täytyy tuntea ohjelmoinnin alkeet ja jokin lausekieli, esimerkiksi Ada, Java (Java on Sunin rekisteröity tavaramerkki) tai C. Emme tässä kirjoita algoritmeja millään tällaisella kielellä, vaan esitämme ne eräänlaisella pseudokielellä, jollaista jokainen perusteet tunteva osaa toivottavasti lukea. Merkinnöistä on syytä huomata, että ilmaisemme lohkorakenteen pelkästään sisennyksellä (Pythonin tapaan) ja sijoituksen symbolilla :=

Algoritmien vertailuperusteita

Saman tehtävän voi yleensä ratkaista usealla erilaisella algoritmilla, mutta mikä tahansa algoritmi ei sovi käytännön ratkaisuksi. Hyvä algoritmi ei tuhlaa aikaa eikä tilaa.

Tärkein algoritmin aikavaatimukseen vaikuttava seikka on tietysti syöte, joka tiivistetään nopeustarkasteluissa yleensä yhteen lukuun. Tavallisesti tarkastellaan syötteen kokoa, mutta joskus jokin muu sen monimutkaisuuden tunnusluku voi olla olennaisempi. Suoritusaika riippuu tietysti myös käytetystä tietokoneesta, ohjelmointikielestä, muista ajossa olevista ohjelmista ja niin edelleen. Koska tällaiset tekijät vaikeuttaisivat analyysiä tarpeettomasti, ne "abstrahoidaan pois" tekemällä yksinkertaistavia oletuksia.

Tärkein oletus on, että algoritmi suoritetaan peräkkäisten alkeisoperaatioiden sarjana, ja että jokainen alkeisoperaatio vie vakioajan. Kertolasku voi olla kymmenen kertaa hitaampi kuin yhteenlasku, mutta tästä ei välitetä - tärkeää on, että alkeisoperaatioiden aikavaatimukselle on jokin yläraja.

Edelleen unohdetaan jopa alkeisoperaatioiden tarkka lukumäärä ja lasketaan asymptoottinen aikavaatimus. Jos syötteen koolla n tarvitaan 3n²+5n-1 alkeisoperaatiota, sanotaan vain, että aikavaatimus on luokkaa n², sillä molemmat n:n funktiot kasvavat suunnilleen yhtä nopeasti. Kirjoitamme tämän kaavana 3n²+5n-1=(n²).

Matemaatikon täytyy tietysti määritellä, mitä "suunnilleen yhtä nopeasti" tarkoittaa. Kun g on funktio luonnollisilta luvuilta ei-negatiivisille reaaliluvuille, merkitsemme (g(n)):llä niiden funktioiden f luokkaa, jotka eroavat g:stä vain vakiokertoimella:

(f(n))

(2ⁿ)

Silloin kun -merkintä esiintyy yhtälön oikealla puolella, sovitaan että =-merkki tarkoittaakin merkkiä . Siis f(n)=(g(n)) tarkoittaa, että f(n) voidaan "puristaa" c₁g(n):n ja c₂g(n):n väliin, kunhan n:n annetaan kasvaa tarpeeksi suureksi. Voidaan myös ajatella, että (g(n)) tarkoittaa jotain edellä määritellyn joukon funktiota, jota ei vain nimetä tarkkaan.

:n määritelmä sisältää kaksi epäyhtälöä. Jos jommastakummasta luovutaan, merkitään O tai :

Algoritmin tilavaatimus tarkoittaa sen tarvitsemien tietokoneen muistipaikkojen lukumäärää. Sitä voidaan myös tutkia asymptoottisesti, mutta se on monesti kiinnostava tarkemminkin - muistin käyttäminen on tyypillisesti melko hidasta, varsinkin jos tilaa kuluu niin paljon että joudutaan turvautumaan levymuistiin.

Harjoitustehtäviä

1. Osoita, että
   1. 5n+8 = (n),
   2. 0,000001n² = (100n²+10000n),
   3. 10 = (1) ja
   4. log₂(n) = (log₁₉₉₈(n)).
   (Yllä 10 ja 1 tarkoittavat oikeastaan vakiofunktioita, jotka kuvaavat n:n aina samalle luvulle.) Käytännössä :n "sisään" kirjoitettava funktio pyritään valitsemaan mahdollisimman yksinkertaiseksi, ja esimerkiksi logaritmin kantalukua ei merkitä.
2. Osoita, että
   1. f(n) = (f(n)),
   2. f(n) = (g(n)) jos ja vain jos g(n) = (f(n)) ja
   3. jos f(n) = (g(n)), g(n) = (h(n)), niin f(n) = (h(n))
   kaikilla funktioilla f, g ja h.
3. Osoita, että
   1. 10000 = O(n),
   2. n = O(n⁵),
   3. log n = O(n) ja
   4. n = O(nlog n).
   (Tässäkään logaritmin kantaluvulla ei ole väliä.)
4. Osoita, että f(n) = O(g(n)) jos ja vain jos g(n) = (f(n)).
5. * Etsi sellaiset funktiot f ja g, että ei päde f(n)=O(g(n)) eikä f(n)=(g(n)).

Esimerkki: Fibonaccin luvut

Tässä artikkelissa tutkitaan esimerkkinä muutamaa algoritmia, joilla lasketaan Fibonaccin lukuja. Ongelma on yksinkertainen: on annettu luku n, ja on laskettava F(n), missä F(n) määritellään palautuskaavalla

F(n+2) = F(n) + F(n+1), kun n 0,

Algoritmien aikavaatimuksia on luonnollista tarkastella n:n funktioina.

Harjoitustehtävä

6. Laske kymmenen ensimmäistä Fibonaccin lukua F(0), ..., F(9).

Naiivi algoritmi

Ensimmäinen algoritmimme naiivi-fibonacci perustuu suoraan määritelmään: jos n on 0 tai 1, palautetaan määritelmästä saatava arvo, muuten lasketaan rekursiivisesti F(n-1) ja F(n-2) ja summataan tulokset.

On tärkeää varmistua, että algoritmin suoritus päättyy. Tämä nähdään induktiolla: Jos n 1, asia on selvä. Muussa tapauksessa nojataan siihen, että suoritus päättyy parametrin arvoilla n-2 ja n-1.

Tämä algoritmi on siinä mielessä elegantti, että se muistuttaa Fibonaccin lukujen määritelmää. Se kuvaa, mitä lasketaan, eikä siitä edes näe aivan helposti, miten laskenta tapahtuu. Kuten kohta huomaamme, algoritmi on toivottoman hidas - tämä on liian korkean tason ohjelmointia tavalliselle lausekielelle. (On ohjelmointikieliä, esimerkiksi Prolog, joilla ohjelmoidaan juuri tällä tavalla.)

Merkitään algoritmin aikavaatimusta T(n):llä. Jos n 1, T(n) on vakio; muuten T(n) = T(n-2)+T(n-1)+vakio. Ilmeisesti T(n)=(F(n)). Myöhemmin nähdään, että F(n)=(ⁿ), missä  > 1, joten tämän algoritmin aikavaatimus on vähintään eksponentiaalinen! (Itse asiassa T(n)=(F(n)), mutta toisen suunnan todistaminen on hieman työläämpää, eikä se ole kovin kiinnostavaa - jos aikavaatimus on eksponentiaalinen, algoritmi on käytännössä aivan liian hidas.)

Harjoitustehtäviä

7. Kokeile algoritmin naiivi-fibonacci toimintaa paperilla. Kuinka suurilla n sen saa laskettua järkevässä ajassa?
8. Toteuta algoritmi naiivi-fibonacci jollain tuntemallasi lausekielellä. Kuinka suurilla n jaksat odottaa ohjelman suorituksen loppumista?
9. * Mikä on tämän algoritmin asymptoottinen tilavaatimus? (Montako lukua joudut pitämään yhtä aikaa paperilla, kun kokeilet algoritmin toimintaa?)

Silmukka

Rekursiivisen algoritmin vika on, että se "unohtaa" tietoa. Kokeilepa laskea vaikka F(10): todennäköisesti kirjoitat paperille peräkkäisiä Fibonaccin lukuja, niin että et joudu laskemaan samoja lukuja uudestaan. Itse asiassa riittää muistaa kaksi edellistä lukua: aloitetaan F(0):sta ja F(1):stä, lasketaan F(2), sitten F(1):n ja F(2):n avulla F(3) jne.

Olkoon aluksi a=F(0)=0 ja b=F(1)=1. Silmukan k:nnen kierroksen jälkeen haluamme muuttujien arvoiksi a=F(k) ja b=F(k+1). Muuttujan a uusi arvo on suoraan b:n vanha arvo, ja b:n uusi arvo on a:n ja b:n vanhojen arvojen summa.

Alkutoimenpiteisiin kuluu vakion verran aikaa, samoin silmukan yhdellä kierroksella. Kierroksia on n-1, joten algoritmin aikavaatimus on

vakio + (n-1)vakio = (n).

Harjoitustehtäviä

10. Kokeile algoritmin silmukka-fibonacci toimintaa paperilla. Vastaako tämä sitä, miten lasket Fibonaccin lukuja käsin?
11. Toteuta algoritmi silmukka-fibonacci jollain lausekielellä. Onko tämä algoritmi havaittavasti nopeampi kuin naiivi-fibonacci?

Matriisien laskutoimituksiin perustuva algoritmi

Nyt pääsemme lopulta käyttämään apuna matematiikkaa. Seuraavan algoritmin ymmärtäminen vaatii lineaarialgebran perustietoja sen verran, että matriisien kertolasku on tuttu asia.

Edellisessä algoritmissa on kaksi muuttujaa, joita päivitetään joka kierroksella. Jos muuttujat ajatellaan 2-vektorin alkioiksi, päivitys on lineaarimuunnos: jos ohjelmointikielessämme voisi käyttää matriisioperaatioita, päivityksen voisi kirjoittaa sijoituksena

.

.

Jos matriisin M voisi korottaa potenssiin n-1 nopeammin kuin kertomalla se itsellään n-2 kertaa, olisi ongelmaamme löydetty nopeampi ratkaisu. Tietysti matriisit pitää esittää jonakin tietorakenteena, ja niiden kertolasku pitää toteuttaa, mutta tämä on 2*2-matriisien tapauksessa helppoa, emmekä keskity tähän seikkaan enempää vaan käytämme pseudokielessämme vapaasti matriisimuuttujia. (Suurten matriisien esittäminen ja kertolasku ei sen sijaan ole triviaalia.) Merkitsemme matriisien kertolaskua tavalliseen tapaan kirjoittamalla kerrottavat vierekkäin.

Potenssilasku

Tässä aliluvussa yritämme löytää nopean tavan laskea matriisien potensseja. Tavoite on laskea M^n-1, mutta koska potenssilaskualgoritmi voi olla hyödyllinen muutenkin, muotoilemme tehtävän siistimmin: on laskettava A^k, missä A on matriisi ja k 0 kokonaisluku.

Voisiko matriisipotenssin laskea nopeammin kuin k-1 kertolaskulla? Kokeile: Laske M², M⁴ ja M⁸. Montako matriisikertolaskua tarvitsit? Entä montako tavallisten lukujen kertolaskua tarvitset laskiessasi lukua 7⁸?

Seuraavassa esityksessä ei oikeastaan ole mitään merkitystä sillä, että potenssiin korotettavat oliot ovat matriiseita - algoritmi toimii myös luvuille. (Oikeastaan tarkastelu pätee minkä tahansa ryhmän alkioille - olennaista on kertolaskun assosiatiivisuus, s.o. laki (AB)C=A(BC). Ilman tätä ominaisuutta potenssimerkintäkään ei ole järkevä.)

Luultavasti huomasit, että M⁸:n laskemiseen tarvitaan vain kolme kertolaskua:

Yritetään induktiivista lähestymistapaa: Kuvitellaan, että A^j osataan laskea, kun j<k, ja mietitään A^k:n laskemista. Jos k on parillinen, voidaan soveltaa edellisen kappaleen ideaa: lasketaan A^k/2 ja kerrotaan se itsellään. Jos taas k on pariton, niin varmasti k-1 on parillinen, ja A^k = A A^k-1. Saadaan algoritmi rekursiivinen-potenssi.

Aikavaatimuksen laskemiseksi kirjoitetaan k binäärilukuna. Jokaisella kerralla aliohjelman kutsuessa itseään k:n binääriesityksen lopusta joko katoaa nolla (jos k on parillinen, se jaetaan kahdella) tai muuttuu ykkönen nollaksi (jos k on pariton, siitä vähennetään 1). Kutsuja on siis yhteensä

(k:n binääriesityksen numeroiden määrä-1) + (k:n binääriesityksen ykkösten määrä-1) + 1 = (log k).

Algoritmin tilavaatimus on myös (log k) rekursiivisten kutsujen takia. Tilan kulutus on "piilossa", mutta jokainen rekursiivinen kutsu jättää muistiin tiedon siitä, mitkä ovat muuttujien arvot kutsuvassa aliohjelmassa. Tässä tapauksessa rekursio voidaan muuntaa silmukaksi, joka tekee aivan samat laskutoimitukset mutta aloittaa suoraan pienimmistä A:n potensseista ja kokoaa niistä A^k:n. Ei ole aivan ilmiselvää, miten tämä tehdään, ja ohjelmoinnin harrastajan kannattaakin jäädä miettimään asiaa hetkeksi ennen kuin jatkaa lukemista.

Seuraavassa ratkaisussa käytämme apuna invariantin käsitettä. Nimensä mukaisesti invariantti on jokin muuttumaton asia - tässä tarkoitamme sillä erästä lauseketta, jonka arvo on sama ennen silmukan kutakin "kierrosta" ja sen jälkeen. Käytämme apumuuttujaa X, jonka arvona on aluksi identiteettimatriisi, ja pyrimme säilyttämään invarianttina lausekkeen X A^k. Tavoitteemme on muuttaa jokaisella kierroksella X:n, A:n ja k:n arvoa niin, että k:n arvo pienenee aina ja invariantti pysyy samana. Lopulta k=0, ja silloin X on haluttu vastaus. Jos merkitsemme A_i:llä, X_i:llä ja k_i:llä muuttujien arvoja silmukan i:nnen kierroksen lopussa, invarianssiehdosta seuraa yhtäsuuruuksien ketju

Lähdetään siis muodostamaan algoritmia. Jotta se toimii samalla tavalla kuin rekursiivinen-potenssi, valitsemme silmukan kierroksella suoritettavat operaatiot k:n parillisuuden mukaan, ja joko jaamme k:n kahdella tai vähennämme siitä ykkösen. Jos k on parillinen, invarianssiehto voidaan nyt kirjoittaa muotoon

Siinä olikin jo kaikki! Kun invariantti oli valittu hyvin, algoritmia kirjoittaessa meille ei jäänyt juurikaan vaihtoehtoja. Ensi katsomalta iteratiivinen-potenssi voi olla vaikea ymmärtää; avain on invariantti X A^k.

Harjoitustehtäviä

12. Kirjoita aliohjelma matriisipotenssi-fibonacci, joka laskee Fibonaccin lukuja käyttämällä apuna aliohjelmaa iteratiivinen-potenssi. Joudut antamaan matriisimuuttujille alkuarvoja tavallisten skalaarimuuttujien avulla; kirjoita yksinkertaisesti tyyliin
    
    äläkä murehdi siitä, miltä tämä näyttäisi todellisessa ohjelmointikielessä.
13. Toteuta äskeinen algoritmi jollain lausekielellä. Pidä matriiseja joko tietorakenteissa tai neljässä muuttujassa, mutta tee yleiskäyttöiset aliohjelmat 2*2-matriisien kerto- ja potenssilaskua varten. Vinkki: 2*1-matriisia ei tarvitse toteuttaa erikseen, vaan voit käyttää 2*2-matriisia, jonka toinen pystyvektori sisältää vain nollia. Testaa aliohjelmiasi helpoilla matriisilaskuilla ja kokeile myös pääohjelman toimintaa. Huomaatko nopeuseroa algoritmiin silmukka-fibonacci?
14. * Jos sinulla on käytössäsi sellaisen kielen tulkki tai kääntäjä, jossa voi laskea mielivaltaisen suurilla kokonaisluvuilla, tai jos osaat toteuttaa vastaavat toiminnot itse, kirjoita algoritmit silmukka-fibonacci ja matriisipotenssi-fibonacci niin että ne toimivat mielivaltaisilla n. Kuinka suurilla n huomaat nopeuseron? Miksi asymptoottisen aikavaatimuksen laskeminen muuttuukin vaikeammaksi tässä tapauksessa?
15. Kuvitellaan, että ohjelmointikielessämme kokonaisluvuille on vain kolme laskutoimitusta: kahden luvun yhteenlasku, luvun kertominen kahdella ja parillisen luvun jakaminen kahdella. Lisäksi voidaan testata, onko luku parillinen vai ei. Kirjoita logaritmisessa ajassa toimiva ohjelma, joka kertoo kaksi kokonaislukua keskenään.
16. Osoita, että matriisin
    
    potenssit ovat muotoa
    
    Kirjoita algoritmi uudestaan sellaiseen muotoon, että se ei pidä muistissa koko matriisia vaan vain luvut p ja q.
17. * (Lineaarialgebran tuntijoille) Mitkä ovat matriisin M ominaisarvot ja -vektorit? Miten niitä voi hyödyntää matriisipotenssin laskemisessa vielä nopeammin?

Differenssiyhtälö

Vielä nopeamman algoritmin löytämiseksi jatkamme Fibonaccin lukujonon ominaisuuksen tutkimista. Jonon määrittelevät differenssiyhtälö

Tehdään nyt rohkea arvaus, että Fibonaccin luvut saadaan jonkin luvun r potensseina: F(n)=rⁿ. Jos näin on, r:lle saadaan differenssiyhtälöstä ehto

= (1 + )/2

= (1 - )/2

Olemme silti havainneet tärkeän asian: n:n funktiot ⁿ ja ⁿ toteuttavat differenssiyhtälön. Nyt voimme nimittäin konstruoida niiden avulla lisää ratkaisuja. Ensinnäkin, jos G(n) on differenssiyhtälön ratkaisu, niin on myös C G(n) jokaisella vakiolla C. Toiseksi kahden ratkaisun summa on myös ratkaisu. Nämä tiedot yhdistämällä saamme parametroidun ratkaisun

C₁ ⁿ + C₂ ⁿ.

Jos nyt saadaan määrättyä sellaiset vakiot C₁ ja C₂, että alkuehdot F(0)=0, F(1)=1 toteutuvat, on löydetty lauseke F(n):lle. Saadaan yhtälöpari

C1 + C2	=	0,
C1 + C2	=	1,

C₁ = 1/

C₂ = -1/

Koska ||<1, toisen termin vaikutus johtamassamme lausekkeessa pienenee nopeasti n:n kasvaessa. Kun n 0,

|C₂ⁿ| < 1/2,

C₁ⁿ

Nyt olemme siis löytäneet hyvin yksinkertaisen algoritmin potenssilasku-fibonacci, joka toimii vakioajassa kaikilla n; sen aikavaatimus on siis (1).

Tällä algoritmilla on kuitenkin se rajoitus, että sen suorittamiseksi täytyy laskea reaaliluvuilla. Useimmat ohjelmointikielet ja tietokoneet tukevat ns. liukulukuja, joilla voi tehdä reaalilukujen laskutoimituksia likimääräisesti. Algoritmimme voi hyödyntää liukulukulaskentaa melko hyvin, koska siinä joka tapauksessa tehdään lopuksi pyöristys: voimme toivoa, että laskennassa tapahtuvat virheet ovat niin pieniä, että ne eivät vaikuta lopputulokseen. Tällaisia asioita ei ole kuitenkaan aivan helppo todistaa.

Harjoitustehtäviä

18. Toteuta algoritmi potenssilasku-fibonacci jollain lausekielellä. Tutki, miten suurilla n:n arvoilla saat vielä oikeita kokonaislukuja vastaukseksi.
19. *
    1. Ratkaise differentiaaliyhtälöt
       1. f''(x) + f'(x) - f(x) = 0,
       2. f''(x) + f'(x) - f(x) = 1,
       3. f''(x) + f'(x) - f(x) = x,
       4. f''(x) + 2f'(x)+ f(x) = 0 ja
       5. f''(x) + f'(x) + f(x) = 0.

       Etsi sekä yleiset ratkaisut että ratkaisut alkuehdoilla f(0)=1, f'(0)=2.

    2. Ratkaise differenssiyhtälöt
       1. F(n+2) + F(n+1) - F(n) = 0,
       2. F(n+2) + F(n+1) - F(n) = 1,
       3. F(n+2) + F(n+1) - F(n) = n,
       4. F(n+2) + 2F(n+1)+ F(n) = 0 ja
       5. F(n+2) + F(n+1) + F(n) = 0.

       Etsi sekä yleiset ratkaisut että ratkaisut alkuehdoilla F(0)=1, F(1)=2.

Loppusanat

Olemme nähneet, että tietokoneohjelmaa voi nopeuttaa paljon suunnittelemalla sen hyvin. Aina ei tietenkään saavuteta näin dramaattista tulosta: aikavaatimus parani toivottomasta eksponentiaalisesta varsin hyvään logaritmiseen, tai eräillä ehdoilla vakioksi. Toivottavasti lukija on huomannut, että matematiikka ei ole tietojenkäsittelijälle lainkaan turha tieteenala.

Kirjallisuutta

Abelson, Harold; Sussman, Gerald Jay: Structure and Interpretation of Computer Programs, MIT Press 1996.

Tämä kirja esittelee ohjelmoinnin alkeita monipuolisesti Scheme-kielellä ja etenee varsin pitkälle. Suosittelen innokkaalle harrastajalle: jos olet tottunut tavallisiin lausekieliin, Scheme voi olla vaikea omaksua, mutta silloinhan se avartaa maailmankuvaasi.

Cormen, Thomas; Leiserson, Charles; Rivest, Ronald: Introduction to Algorithms, MIT Press 1990.

Jos ymmärrät ohjelmoinnin ja tietorakenteiden alkeet (esimerkiksi linkitetyt listat) ja matematiikkaa sen verran, että selviät induktiotodistuksista, suosittelen. Tämä on laaja yleisteos, josta on iloa myöhemminkin.

Kaldewaij, Anne: Programming: The Derivation of Algorithms, Prentice-Hall 1990.

Varsin erilainen lähtökohta algoritmien suunnitteluun on niiden johtaminen vaatimuksista, mistä nähtiin pieni vilaus algoritmin iteratiivinen-potenssi yhteydessä. Tätä kirjaa voi suositella logiikan harrastajalle, joka tuntee ohjelmointia enemmän kuin aivan alkeiden verran, tai ohjelmoijalle, joka on kiinnostunut logiikasta.

Jouni Seppänen
Jouni.Seppanen@iki.fi