View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

        Extending Stein’s GCD algorithm and a comparison to Euclid’s GCD algorithm

        Thumbnail
        View/Open
        Thesis.pdf (459.3Kb)
        Publication date
        2019
        Author
        Barkema, J.R.
        Metadata
        Show full item record
        Summary
        Euclid’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.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/33194
        Collections
        • Theses
        Utrecht university logo