C++ -kirjasto suurien lukujen operaatioihin

Abstract

Tässä työssä toteutetaan C++ -ohjelmointikielellä kirjasto, jolla voidaan laskea perusoperaatioita suuremmille luvuille kuin tavallisesti kokonaislukuja (engl. integer) käyttämällä pystyttäisiin. Toteutettu ohjelma käyttää lukujen käsittelyssä ja tallentamisessa merkkijonoja (engl. string), mikä mahdollistaa suurien lukujen operaatioiden laskemisen merkkijonon maksimipituuden ollessa 2³²-1 eli 4 294 967 295 merkkiä. Vertailuna C++ -kielen suurin mahdollinen kokonaisluku on 20 merkkiä pitkä (18 446 744 073 709 551 615). Toteutetut operaatiot ovat yhteen-, vähennys- ja kertolasku, mutta tämän lisäksi työhön toteutettiin myös mahdollisuus suorittaa Karatsuba-algoritmi eripituisille luvuille ja näin todeta sen toteutuksen olevan linjassa asymptoottisen suoritusajan kanssa. Työssä käsitellään algoritmien ja niiden pseudokoodien teoriaa sekä toteutetaan C++ -ohjelmointikielelle käsiteltävät algoritmit sillä tavalla, että niiden vertaaminen esitettyyn pseudokoodiin on mahdollista ja helpohkoa C++ -ohjelmointikieltä osaavalle henkilölle. Tämä palvelee työssä lyhyesti mainittua ideaa siitä, että työtä olisi mahdollista hyödyntää toteutettaessa vastaavat operaatiot jollekin toiselle ohjelmointikielelle. Algoritmien asymptoottiset suoritusajat suuria lukuja käsittelevissä operaatioissa ovat tärkeässä osassa, joten niitä tarkastellaan sekä teoreettisella että käytännön tasolla. Käytännön tarkastelussa suoritetaan toteutettua C++ -ohjelmaa ja lasketaan sieltä saatavat asymptoottiset suoritusajat verraten niitä teoreettisiin. Käytännön tasolla on myös tärkeää huomioida, että parempi asymptoottinen tehokkuus ei välttämättä tee algoritmista toista nopeampaa, koska suuret vakiotermit saattavat jäädä huomioimatta ja siksi käytännössä tehokkuus riippuu käsiteltävien lukujen suuruudesta.