Show simple item record

dc.rights.licenseCC-BY-NC-ND
dc.contributor.advisorTel, Gerard
dc.contributor.authorBarkema, J.R.
dc.date.accessioned2019-08-05T17:01:27Z
dc.date.available2019-08-05T17:01:27Z
dc.date.issued2019
dc.identifier.urihttps://studenttheses.uu.nl/handle/20.500.12932/33194
dc.description.abstractEuclid’s algorithm and Stein’s binary GCD algorithm are the two most well-known GCD algorithms. It has already been proven that Euclid’s algorithm is O(n^2), but we aim to provide a more intuitive and thorough proof using an in-depth look at the cost of the modulo operation. An extended version of Stein’s algorithm is also provided with proof of correctness. While there exist other extended versions of Stein’s algorithm, this version distinguishes itself through its relative simplicity and elegant use of properties of Bézout’s identity. Finally, a comparison of the performance of both algorithms with their extended versions is provided.
dc.description.sponsorshipUtrecht University
dc.format.extent470425
dc.format.mimetypeapplication/pdf
dc.language.isoen
dc.titleExtending Stein’s GCD algorithm and a comparison to Euclid’s GCD algorithm
dc.type.contentBachelor Thesis
dc.rights.accessrightsOpen Access
dc.subject.keywordsGCD, Euclid, Stein, Bézout, algorithm, modulo
dc.subject.courseuuWiskunde


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record