Izbrani algoritmi za množenje celih števil

NAĐ, KATARINA (author), Robič, Borut (mentor)

Ž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.

• Language: Slovenian
• Keywords: množenje celih števil, algoritem, Toom-Cook, Schönhage-Strassen, Harvey-Hoeven
• Work type: Bachelor thesis/paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2021
• PID: 20.500.12556/RUL-127408
• COBISS.SI-ID: 65983747
• Publication date in RUL: 04.06.2021

Secondary language

• Language: English
• Title: Selected algorithms for integer multiplication

Abstract

A long time ago in the ancient history, before our time, people began to multiply numbers. Various methods of multiplication have been developed, but nowadays the most well-known method is the one that is taught in primary school. This algorithm, however, is too slow to be used in computer science, as the use of large numbers has grown together with the development of computer science and Internet. Due to this problem, in 1960 Karatsuba invented an algorithm that was faster. Shortly after its publication, the Toom-Cook-k (ATC-k) and Schönhage-Strassen (ASS) algorithms were developed. In 2019, we were introduced to the theoretically fastest number multiplication algorithm ever, published by scientists Harvey and Hoeven. In the dissertation, we reviewed how the algorithms listed above work, delving into ATC-k and ASS. Furthermore the ending briefly describes algorithm Harvey-Hoeven (AHH) and presents the implementation of ATC-3.

• Keywords: integer multiplication, algorithm, Toom-Cook, Schönhage-Strassen, Harvey-Hoeven