Algoritmi za brzo množenje i dijeljenje velikih prirodnih brojeva

Efikasna realizacija osnovnih aritmetičkih operacija na velikim brojevima se, obično, izvodi tako da brojeve prikažemo kao niz znamenki u nekoj odabranoj bazi, tako da se osnovne operacije na znamenkama egzaktno i brzo izvode u aritmetici računala. Algoritmi za zbrajanje i oduzimanje brojeva koji oponašaju algoritme za "ručno" računanje, linearno ovise o duljini brojeva i optimalni su. S druge strane, algoritmi koji oponašaju "ručno" množenje i dijeljenje su kvadratne složenosti. U ovom radu smo pokazali da postoje bolji algoritmi za množenje i dijeljenje velikih brojeva. Najprije smo detaljno opisali algoritam klasičnog ("ručnog") množenja, za kojeg smo dokazali da ima kvadratnu složenost. Prvo poboljšanje tog algoritma smo dobili metodom "podijeli pa vladaj" -- podijelili smo brojeve na 2 i više dijelova. Uz korištenje polinomne interpolacije i evaluacije, dobili smo algoritam čija složenost ne ovisi više kvadratno o duljini brojeva. Taj algoritam se zove Karatsubin algoritam, u čast A. Karatsube, koji je prvi došao do tog algoritma. Također, napravili smo i implementaciju klasičnog i Karatsubinog algoritma u programskom jeziku Java te smo na primjeru pokazali da je Karasubin algoritam efikasniji od klasičnog algoritma. Još bolji algoritam je Schönhage--Strassenov algoritam, koji koristi brzu Fourierovu transformaciju za množenje polinoma. Jedno poglavlje smo posvetili opisu tog algoritma te pokazali da je njegova složenost \(O(n \log n \log \log n)\). To je, trenutno, najbrži poznati algoritam za množenje brojeva. Na kraju smo opisali i opći algoritam za brzo dijeljenje, preko brzog množenja, koji je baziran na Newtonovoj metodi s progresivnim povećanjem točnosti. Dokazali smo da složenost algoritma za brzo dijeljenje linearno ovisi o izabranom algoritmu za množenje.Efficient realization of basic arithmetic operations on big natural numbers is usually performed by representing big numbers as arrays of digits in a chosen base, so that arithmetic operations on digits are performed exactly and quickly in computer arithmetics. Addition and subtraction algorithms, which simulate ”manual” addition and subtraction, have linear complexity, depending on number length. Also, these algorithms are optimal. On the other hand, ”manual” multiplication and division algorithms have quadratic complexity, and they are not optimal. At the beginning of this thesis, we described the classic multiplication algorithm and proved that the complexity of this algorithm is quadratic. We got the first improvement in complexity by designing an algorithm with the ”divide and conquer” strategy. By splitting numbers in 2 or more pieces, and with usage of polynomial interpolation and evaluation, we got an algorithm whose complexity is less than quadratic. This algorithm is called Karatsuba’s algorithm, in honor of A. Karatsuba, who invented this algorithm. We have also implemented the classic and Karatsuba’s algorithm in Java programming language, and showed an example of improvement in speed by using Karatsuba’s algorithm, instead of the classic algorithm. An even better multiplication algorithm is the Schönhage–Strassen algorithm, which uses the Fast Fourier Transform for polynomial multiplication. We have one chapter dedicated to describing this algorithm which has the complexity \(O(n \log n \log \log n)\). This is the fastest multiplication algorithm, so far. At the end, we have described a general division algorithm, based on fast multiplication, which uses Newton’s method with progressive accuracy improvement. We have proved that the complexity of this algorithm depends linearly on the complexity of the chosen multiplication algorith