Fibonaccin lukujen laskenta-algoritmit

Abstract

Fibonaccin lukujono on luvuilla 0 ja 1 alkava rekursiivinen lukujono, jossa jokainen jäsen on kahden edellisen summa. Työssä tarkastellaan Fibonaccin lukujen laskenta-algoritmien tehokkuuksia sekä asymptoottisia tehokkuuksia arvioiden että koodia suorittamalla. Työ sivuaa myös suurien kokonaislukujen aritmetiikkaa, koska lukujonon jäsenet kasvavat eksponentiaalisesti. Tutkielma on toteutettu kirjallisuuskatsauksena pohjautuen pääosin Elsevierin julkaisemiin tieteellisiin lehtiin ja eri kirjastojen dokumentaatioon.

Työ etenee algoritmi kerrallaan tehottomammasta algoritmista tehokkaampaan. Asymptoottisesti tehokkaimmaksi algoritmiksi osoittautui GMP-kirjaston käyttämä algoritmi. Algoritmin perusidea on laskea aina järjestysluvultaan kaksinkertainen lukujonon jäsen erilaisten identiteettien avulla. Työssä huomataan myös kertolaskun olevan suoritusajaltaan algoritmin hallitseva operaatio ja optimaalisen kertolaskualgoritmin käyttäminen osoittautuukin vähintään yhtä tärkeäksi kuin Fibonaccin lukujonon laskenta-algoritmin valinta. Asymptoottisesti tehokkaimmalla kertolaskualgoritmilla GMPn algoritmi saa asymptoottiseksi tehokkuudekseen O(n log ⁡n ⁡log ⁡log⁡ n). Mittaustulosten mukaan kokonaislukutyypin toteutuksesta riippuen lukujonon 20.–50. jäsentä pienempien jäsenten laskeminen on tehokkaampaa asymptoottisesti huonoimmilla rekursiokaavaa hyödyntävillä iteratiivisilla menetelmillä.