Složenost množenja prirodnih brojeva

diplomski rad

• Naslov (engleski): Complexity of multiplication of natural numbers
• Autor: Domagoj Babić
• Mentor: Filip Najman (mentor)
• Član povjerenstva: Filip Najman (predsjednik povjerenstva)
• Član povjerenstva: Vedran Krčadinac (član povjerenstva)
• Član povjerenstva: Mea Bombardelli (č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: 2023-03-14, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom radu su predstavljeni algoritmi za množenje s naglaskom na složenost tih algoritama. Kroz stoljeća se pretpostavljalo da su svi algoritmi za množenje prirodnih brojeva složenosti \(O(n^2)\), kao na primjer: egipatski algoritam, naivni (školski) algoritam i algoritam ruskog seljaka. Karatsuba je svojim otkrićem sredinom 60-tih godina 20. stoljeća otkrio brži algoritam složenosti \(O(n^{1.58})\) što je pokrenulo istraživanja na tom području te su za manje od 10 godina Schoenhage i Strassen otkrili algoritam složenosti \(O(n \cdot \log{n} \cdot \log{(\log{n}}))\). Harvey i van der Hoeven su 2019. godine otkrili algoritam složenosti \(O(n\cdot \log{n})\) koji je trenutno najbrži algoritam i predstavlja trenutni vrhunac napretka u tom području

Sažetak (engleski)

In this thesis we present algorithms for integer multiplication with the focus on their complexity. Through centuries it was believed that the best complexity was \(O(n^2)\), i.e. Egyptian multiplication, naive (schoolbook) multiplication and the Russian peasant multiplication algorithm. Karatsuba in the mid 1960’s discovered an algorithm whose complexity is \(O(n^{1.58})\) which started lots of research in this field, and in less than 10 years Schoenhage and Strassen invented an algorithm whose complexity is \(O(n \cdot \log{n} \cdot \log{(\log{n}}))\). In the year 2019. Harvey and der Hoeven invented an algorithm whose complexity is \(O(n\cdot \log{n})\) which is currently the fastest algorithm for integer multiplication and represents the current pinnacle of progress in the field.

• Ključne riječi: egipatski algoritam; naivni (školski) algoritam; algoritam ruskog seljaka; Karatsuba; Harvey; van der Hoeven
• Ključne riječi (engleski): Egyptian multiplication; naive (schoolbook) multiplication; the Russian peasant multiplication algorithm; Karatsuba; Harvey; van der Hoeven
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:317710
• Studijski program: Naziv: Matematika i informatika; smjerovi: nastavnički; Smjer: nastavnički; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra edukacije matematike i informatike (mag. educ. math. et inf.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2023-03-21 13:53:03