Naslov diplomskega dela: Izbrani algoritmi za množenje celih števil
Povzetek:
Že davno v zgodovini, pred novim štetjem, so ljudje začeli množiti števila. Razvile so se različne metode množenja, a v današnjih časih je najbolj znan način osnovnošolskega množenja. Ta algoritem je prepočasen, da bi ga uporabljali v računalništvu, saj je uporaba velikih števil z razvojem računalništva in Interneta rasla. Zaradi tega je leta 1960 Karatsuba izumil algoritem, ki je bil hitrejši. Kmalu po njegovi objavi sta se razvila algoritma Toom-Cook-k (ATC-k) in Schönhage-Strassen (ASS). Leta 2019 smo se spoznali z do sedaj teoretično najbolj hitrim algoritmom za množenje števil, ki sta ga objavila znanstvenika Harvey in Hoeven.
V diplomskem delu smo pregledali, kako delujejo zgoraj našteti algoritmi, pri čemer smo se poglobili v algoritma ATC-k in ASS. Na koncu pa smo še na kratko opisali algoritem Harvey-Hoeven (AHH) in predstavili implementacijo algoritma ATC-3.
Mentor: prof. dr. Borut Robič
Komisija za zagovor:
doc. dr. Tomaž Dobravec (predsednik),
prof. dr. Borut Robič (mentor),
doc. dr. Alen Orbanić (član).
Povezava do video kanala, po katerem se bo prenašal zagovor in ga bo možno spremljati, bo dodana najkasneje na dan zagovora (predvidoma 30 minut pred terminom izvedbe zagovora) na spletni strani: https://ucilnica.fri.uni-lj.si/course/view.php?id=35