Abstract:

According to the process and characteristics of written calculation methods for multiplication of large integers, we determine a data structure suitable for large integers, and optimize the design of memory allocation strategy of data structures, thus greatly improving the operating efficiency of the underlying data. By analyzing the written calculation methods for multiplication of large integers with two different schemes (radix 10x and radix 2x), we determine the maximum value of the radix under the two schemes. On the basis of indepth study of data structure and radix of large integers, we give the C++ definition of large integers. Based on ideas of the Comba algorithm, we propose a new multiplication of large integers——Comba+ algorithm, which is easy to implement in highlevel language. The algorithm is implemented in C++ and has a broader scope of applications. Simulation shows that the algorithm can significantly improve the processing speed. Through comparative analysis on various implementations of multiplication of large integers, we determine the best implementation.

Key words: large integers;multiplication of large integers;data structure;radix;Comba algorithm