Analiza algoritama za izvođenje aritmetičkih operacija

diplomski rad

• Autor: Gabrijela Pirija
• Mentor: Saša Singer (mentor)
• Član povjerenstva: Saša Singer (predsjednik povjerenstva)
• Član povjerenstva: Robert Manger (član povjerenstva)
• Član povjerenstva: Zvonimir Bujanović (član povjerenstva)
• Član povjerenstva: Goranka Nogo (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2020-07-20, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

Vremenska složenost jedan je od najbitnijih faktora kod ocjenjivanja efikasnosti algoritma. Klasični algoritmi za množenje i dijeljenje brojeva imaju kvadratnu vremensku složenost i dovoljno su dobri kod izvođenja aritmetičkih operacija na relativno malim brojevima. Međutim, za množenje i dijeljenje velikih brojeva, potrebni su nam asimptotski brzi algoritmi za izvođenje tih operacija. Karatsubin algoritam, opisan u ovom radu, jedan je od takvih algoritama. Ima bolju, odnosno manju vremensku složenost od klasičnog algoritma za množenje prirodnih brojeva. Znatno poboljšanje može se primijetiti za velike ulazne brojeve koji imaju puno znamenaka. Zato kažemo da je algoritam asimptotski brz. Složenost algoritma za računanje recipročne vrijednosti prirodnog broja linearno ovisi o složenosti korištenog algoritma za množenje. To znači da, ukoliko u postupku dijeljenja prirodnih brojeva koristimo asimptotski brz algoritam za množenje brojeva, dobivamo asimtotski brz algoritam za dijeljenje brojeva. Navedeni algoritmi koriste pozicijski zapis prirodnog broja u proizvoljnoj bazi \( b \geq 2 \). Složenost algoritama ne ovisi o izboru baze. Alternativni način za prikaz brojeva je modularni zapis, koji dobrim izborom modula omogućuje izvođenje modularne aritmetike u linearnom vremenu. Međutim, ukoliko koristimo modularnu aritmetiku, moramo uračunati vrijeme potrebno algoritmima za konverziju iz modularnog u pozicijski zapis i obrnuto. Schoenhage je pokazao da postoji algoritam za množenje prirodnih brojeva koji koristi modularnu aritmetiku. Algoritam uključuje potrebnu konverziju iz jednog zapisa u drugi te ima bolju složenost od klasičnog algoritma, no nešto lošiju od Karatsubinog algoritma. Možemo zaključiti da pravi izbor algoritma ovisi o potrebama i uvjetima u kojima ćemo ga koristiti, pa je optimalan algoritam često onaj koji je dovoljno dobar.

Sažetak (engleski)

Time complexity is one of the most important factors in the evaluation of an algorithm’s efficiency. Classical algorithms for multiplication and division of numbers use quadratic time for computation. Therefore, they are good enough for execution of arithmetic operations on relatively small numbers. However, asymptotically fast algorithms are needed to multiply or divide relatively big ones. The Karatsuba algorithm, described in this paper, is one of those algorithms. It has better, or smaller time complexity than the classical algorithm for multiplication of natural numbers. We can notice a significant improvement for relatively big numbers with numerous digits. That is why we say that the algorithm is asymptotically fast. The algorithm for calculating the reciprocal value of a number is linearly dependent on the multiplication algorithm it uses. That means if we use an asymptotically fast multiplication algorithm when dividing two numbers, we have an asymptotically fast division algorithm for natural numbers. Given algorithms use the positional notation for representing natural numbers in an arbitrary base \( b \geq 2 \). An algorithm’s complexity does not depend on our choice of the base. An alternative way of representing numbers is the modular notation. When moduli are chosen correctly, the modular arithmetic is executed in linear time. However, when using the modular arithmetic, we must take into account the conversion from modular to positional notation and vice versa. Schoenhage has shown that there is a multiplication algorithm for natural numbers, that uses modular arithmetic. The algorithm includes necessary conversion from one notation to another and has a better complexity than the classical algorithm, but slightly worse one than the Karatsuba algorithm. We can conclude that the right choice of algorithm depends on our requirements and conditions in which it will be used, so the optimal algorithm is often the one that is just good enough.

• Ključne riječi: efikasnost algoritama; Karatsubin algoritam; množenje prirodnih brojeva; modularni zapis; Schoenhage
• Ključne riječi (engleski): algorithm efficiency; Karatsuba algorithm; multiplication of natural numbers; modular notation; Schoenhage
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:342812
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2020-11-26 13:58:54