不定长整数乘法的算法研究.pdfVIP

2010年 11月 西安石油大学学报 (自然科学版) N0v．2010 第25卷第6期 JournalofXiallShiyouUniversity(NaturalScienceEdition) V01．25No．6 文章编号：1673-064X(2010)06-0088-03 不定长整数乘法的算法研究 孙书咏 ，马战宝2 (1．西安邮电学院 自动化学院，陕西 西安 710061；2。河南交通职业技术学院，河南 郑州 450005) 摘要：通过对整数乘法的研究给出了基于移位运算和加法运算的不定长整数乘法的算法，根据所提 算法给出了基于双链表整数的乘法算法实现的程序设计，计算结果表明，该算法能够提高乘法运算 的效率 ． 关键词：微处理器；不定长整数；乘法运算；Booth算法 中图分类号：嘲 O1．6 文献标识码 ：A 乘法的本质是求和运算，但是在微处理器中采 Booth算法要求参与运算的数据要以二进制补码形 用叠代求和方法完成乘法计算的效率非常低．为了 式进行存储和表示，而不定长整数在二进制位数不 提高乘法运算的效率，AnderwD．Booth在 1950年提 确定时是无法以补码形式表示的，因此 Booht算法 出了用于二进制整数乘法的Booth算法 ¨．Booth算 并不适用于不定长整数的乘法运算．以下通过对整 法实质上是把乘法运算转变为移位运算和加法运 数乘法进行分析，提出新的整数乘法运算算法． 算，因此从整体上提高了乘法运算的效率．目前改进 1．1 整数乘法 后的Booth算法被广泛地应用于微处理器中的乘法 设整数m与整数 11,相乘 器设计中 ．然而，由于受到 内核中寄存器存储容 Y：m ×n． (1) 量的限制，直接利用乘法器完成乘法运算使得参与 整数 n的二进制形式可表示为 运算的数据长度受到限制，运算结果还会出现难于 n=(bnb b …b3b2b1)f21，bi∈(0，1)为二进 预料的溢出错误 J．而且随着计算机通信和网络的 制位． 飞速发展，诸如视频、图像处理以及为解决计算机安 整数 ／,／的十进制形式可表示为 全问题而出现的公钥密码系统，如RSA、E1Gamal l×2一2+b 2×2一。+ … + F,／： b ×2 一 +b一 一 均需进行超长位数的大数乘法计算，若采用内核乘 b3×22+b2×2 +b1×20 ． (2) 法器无法实现运算要求．另外，大数计算中常用的定 长度整数也会因出现溢出错误导致计算结果的不 由式(1)、(2)得 Y=，孔×(b ×2一+b一1×2一2+bn_ 22一。+… + 可靠． 本文研究不定长大数的乘法运算问题，提出不 b3X2 +b2X2 +b1×2。)， 定长整数及其乘法算法，可以避免出现乘法计算时 即 的溢出错误，从而提高数据计算的精度．