Sequential and parallel sliding window algorithms for multiplying large integers

Abstract

The cost of some primitive operations such as multiplication and division significantly affects the running time of some applications in science and engineering especially when the size of data is big. In this study, we propose a formula to minimize the cost of the multiplication operation on integer numbers when the size of each integer and the number of integers to be multiplied are large. Based on a window strategy, we derived, theoretically, the best size of window for minimizing the cost of multiplying a sequence of big integers. To the best of our knowledge, no previous studies have proposed this formula. Then we designed three efficient algorithms, one sequential and two parallel. Experimental studies were conducted using three parameters: (1) the size of integer, (2) the size of a sequence, and (3) the number of threads. The results of a comparison with the best known previous algorithms showed that (1) the designed sequential algorithm is faster than the previous algorithms with an improvement greater than 64%, (2) the designed parallel algorithms are faster than the best known parallel algorithm with an improvement greater than 50% on the average, and (3) the designed parallel algorithms have super linear speed up.

Keywords

• Multiplication
• Big integer
• Window strategy
• Parallel algorithm
• Speed up