大整数乘法运算的实现及优化  

Implementation and optimization of multiplication of large integers

作　　者：杨灿[1] 桑波[1] 

机构地区：[1]华南理工大学计算机科学与工程学院,广东广州510640

出　　处：《计算机工程与科学》2013年第3期183-190,共8页Computer Engineering & Science

基　　金：国家自然科学基金资助项目(61070090);广东省教育部产学研结合资助项目(2009B090300267)

摘　　要：本文根据大整数笔算乘法的过程及其特点确定了一种适合大整数的数据结构,并对实现数据结构的内存分配策略进行了优化设计,从而大大提高了底层数据操作效率。通过对采用10x基与2x基两种不同方案的大整数笔算乘法进行分析,确定出两种方案下基的最大值。在深入研究大整数的数据结构与基的基础上,给出大整数的C++定义。基于Comba算法思想,提出了一种易于高级语言实现的大整数乘法优化算法——Comba+算法,该算法使用C++实现,适用面更广,测试表明,该算法能显著提高运算速度。通过对大整数乘法多种实现方案的对比分析,确定出最佳实现方案。According to the process and characteristics of written calculation methods for multiplica- tion 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 10^x and radix 2^x）, 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 multiplica- tion of large integers- Comba＋ algorithm, which is easy to implement in high-level language. The al- gorithm is implemented in C＋ ＋ and has a broader scope of applications. Simulation shows that the al- gorithm can significantly improve the processing speed. Through comparative analysis on various imple- mentations of multiplication of large integers, we determine the best imolementa^inn

关 键 词：大整数 大整数乘法 数据结构 基 Comba算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]