Analiza algoritama za izvođenje aritmetičkih operacija

master's thesis

• Author: Gabrijela Pirija
• Mentor: Saša Singer (mentor)
• Committee member: Saša Singer (predsjednik povjerenstva)
• Committee member: Robert Manger (član povjerenstva)
• Committee member: Zvonimir Bujanović (član povjerenstva)
• Committee member: Goranka Nogo (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2020-07-20, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: efikasnost algoritama; Karatsubin algoritam; množenje prirodnih brojeva; modularni zapis; Schoenhage
• Keywords (english): algorithm efficiency; Karatsuba algorithm; multiplication of natural numbers; modular notation; Schoenhage
• Language: croatian
• URN:NBN: urn:nbn:hr:217:342812
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2020-11-26 13:58:54