Lehmerjev algoritem za računanje največjega skupnega delitelja

KOLAR, MIRJAM (author), Jurišić, Aleksandar (mentor), Drnovšek, Roman (co-mentor)

V nalogi si na kratko ogledamo pravila v zvezi z največjim skupnim deliteljem ter najmanjšim skupnim večkratnikom dveh celih števil in opišemo Evklidov algoritem. Ogledamo si povezavo med Evklidovim algoritmom in verižnimi ulomki, Wirsingovo metodo za določanje porazdelitvene funkcije in kako je Knuth z uporabo te funkcije izračunal porazdelitev delnih kvocientov v Evklidovem algoritmu. Iz tega sledi še opis ideje Lehmerjevega algoritma, v čem se razlikuje od Evklidovega algoritma ter kako z njim poiščemo največji skupni delitelj dveh velikih števil in multiplikativni inverz po modulu n za naravno število n. Algoritma ter njuni razširitvi tudi implementiramo ter primerjamo, kdaj in za koliko je kateri od njiju hitrejši. Na koncu še na naključno izbranih številih preverimo, kakšni so kvocienti v Evklidovem algoritmu v praksi.

• Language: Slovenian
• Keywords: Lehmerjev algoritem, Evklidov algoritem, verižni ulomki, porazdelitvene funkcije, Wirsingova metoda za določanje porazdelitvene funkcije, kvocienti v Evklidovem algoritmu.
• Work type: Undergraduate thesis
• Organization: FRI - Faculty of Computer and Information Science
• Year: 2015
• PID: 20.500.12556/RUL-30541
• COBISS.SI-ID: 1536211651
• Publication date in RUL: 30.01.2015

Secondary language

• Language: English
• Title: Lehmer's GCD algorithm

Abstract

In this thesis we briefly look at the rules related to the greatest common divisor and the lowest common multiple of two integers and we describe the Euclidean algorithm. We study connections between Euclidean algorithm and continued fractions, Wirsing's method for determining the distribution function and how Knuth calculated the distribution of partial quotients in Euclidean algorithm using this method. Next Lehmer's algorithm is described and how it improves Euclidean algorithm, greatest common divisor and the multiplicative inverse mod n for a natural number n. We implement both Euclidean algorithm and Lehmer's algorithm in order to compare their speed. We also confirm the calculated distributions of partial quotients in Euclidean algorithm through an experiment.

• Keywords: Lehmer's algorithm, Euclidean algorithm, continued fractions, distribution function, Wirsing's method for determining the distribution function, quotients in Euclidean algorithm.