TiraLabra/TiraLabra — pull request #350 by ousou (2014-08-17 18:01:04+00:00)
Title: Palautus 3

Sain tällä viikolla toteutettua valmiiksi ArrayPolynomial-luokan laskutoimitukset sekä alkulukuhajotelmiin liittyviä metodeja joita tarvitaan Rabinin jaottomuusalgoritmin toteutuksessa. Ensi viikolla tarkoituksena on toteuttaa suurimman yhteisen tekijän algoritmi polynomeille sekä Rabinin algoritmin toteutus. Kun nämä on tehty, voin ruveta kehittämään heuristiikkaa jaottomien polynomien löytämiseksi.

Polynomien laskutoimitukset eivät ole tällä hetkellä optimaalisesti toteutettuja. Esimerkiksi ArrayPolynomial-luokan kertolasku voitaisiin toteuttaa O(n*log n) ajassa (fast Fourier Transform-algoritmilla), mutta se on nyt toteutettu naiivisti O(n^2) ajassa (olettaen että molemmat polynomit ovat astetta n). Koska työn tarkoituksena on löytää heuristiikka joka tekee jaottomuustestin mahdollisimman harvalle polynomille, ei tämä polynomien laskutoimitusten epäoptimaalisuus sinällään vaikuta työn lopputulokseen. Toki löydettäisiin nopeammin jaoton polynomi jos laskutoimitukset olisivat nopeammat, mutta yritysten määrään ei laskutoimitusten toteutus vaikuta.