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

Abstract

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.