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

        The Karatsuba Algorithm for Integer Multiplication: a Parallel Implementation Using BSP

        Thumbnail
        View/Open
        Master thesis.pdf (1.359Mb)
        Author
        Willenborg, L.S.M.
        Metadata
        Show full item record
        Summary
        In the last decades of the 20th century algorithms for multiplying large integers have been improved considerably. Today's state-of-the-art algorithms are based on the Fermat Number Transform and the Fast Fourier Transform. Another algorithm for multiplying integers is the Karatsuba method. Although less efficient, it still outperforms the transform-based algorithms for numbers of size n < 100,000 decimal digits. In this thesis a BSP-based parallel implementation of the Karatsuba algorithm is presented. An algorithm based on BSP (Bulk Synchronous Parallel) consists of a number of so-called supersteps and is commonly used in parallel implementations. The parallel BSP-program was run at the Cartesius parallel computer at the SurfSARA computer center in Amsterdam. Numbers up to a size of n =1,000,000,000 words (10,000,000,000 decimal digits) were multiplied, with good results for parallel speedup and parallel efficiency. By combining the Karatsuba method with a convolution-based multiplication, a parallel implementation for convolution-based multiplications can be achieved, which makes efficient multiplication of ultra long integers in parallel mode possible.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/33011
        Collections
        • Theses
        Utrecht university logo