摘要
本文根据大整数笔算乘法的过程及其特点确定了一种适合大整数的数据结构,并对实现数据结构的内存分配策略进行了优化设计,从而大大提高了底层数据操作效率。通过对采用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
出处
《计算机工程与科学》
CSCD
北大核心
2013年第3期183-190,共8页
Computer Engineering & Science
基金
国家自然科学基金资助项目(61070090)
广东省教育部产学研结合资助项目(2009B090300267)
关键词
大整数
大整数乘法
数据结构
基
Comba算法
large integers
multiplication of large integers
data structure
radix
Comba algorithm