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

《不定长整数乘法的算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2010年11月西安石油大学学报(自然科学版)N0v．2010第25卷第6期JournalofXialShiyouUniversity(NaturalScienceEdition)V01．25No．6文章编号：1673-064X(2010)06-0088-03不定长整数乘法的算法研究孙书咏，马战宝2(1．西安邮电学院自动化学院，陕西西安710061；2。河南交通职业技术学院，河南郑州450005)摘要：通过对整数乘法的研究给出了基于移位运算和加法运算的不定长整数乘法的算法，根据所提算法给出了基于双链表整数的

2、乘法算法实现的程序设计，计算结果表明，该算法能够提高乘法运算的效率．关键词：微处理器；不定长整数；乘法运算；Booth算法中图分类号：嘲O1．6文献标识码：A乘法的本质是求和运算，但是在微处理器中采Booth算法要求参与运算的数据要以二进制补码形用叠代求和方法完成乘法计算的效率非常低．为了式进行存储和表示，而不定长整数在二进制位数不提高乘法运算的效率，AnderwD．Booth在1950年提确定时是无法以补码形式表示的，因此Booth算法出了用于二进制整数乘法的Booth算法¨．Booth算并不适用于不定长

3、整数的乘法运算．以下通过对整法实质上是把乘法运算转变为移位运算和加法运数乘法进行分析，提出新的整数乘法运算算法．算，因此从整体上提高了乘法运算的效率．目前改进1．1整数乘法后的Booth算法被广泛地应用于微处理器中的乘法设整数m与整数11,相乘器设计中．然而，由于受到内核中寄存器存储容Y：m×n．(1)量的限制，直接利用乘法器完成乘法运算使得参与整数n的二进制形式可表示为运算的数据长度受到限制，运算结果还会出现难于n=(bnbb⋯b3b2b1)f21，bi∈(0，1)为二进预料的溢出错误J．而且随着计算机通

4、信和网络的制位．飞速发展，诸如视频、图像处理以及为解决计算机安整数／／,的十进制形式可表示为全问题而出现的公钥密码系统，如RSA、E1GamalF／,：b×2一+b一l×2一2+b一2×2一。+⋯+均需进行超长位数的大数乘法计算，若采用内核乘b3×22+b2×2+b1×20法器无法实现运算要求．另外，大数计算中常用的定．(2)由式(1)、(2)得长度整数也会因出现溢出错误导致计算结果的不Y=，孔×(b×2一+b一1×2一2+bn_22一。+⋯+可靠．本文研究不定长大数的乘法运算问题，提出不b3X2+b2X2

5、+b1×2。)，定长整数及其乘法算法，可以避免出现乘法计算时即的溢出错误，从而提高数据计算的精度．Y=∑m×b×2H，其中b∈(0，1)．(3)1不定长整数乘法1．2乘法算法研究式(3)表明整数相乘可转化为求整数与数2‘的Booth算法从整体上提高了乘法运算的效率．但乘法和求和算法，由于m×2可通过m的二进制左移收稿日期：2010-O4-28作者简介：孙书咏(1970)，男，讲师，硕士，主要从事计算机技术应用研究．E—mail：shuyongsun@126．com孙书咏等：不定长整数乘法的算法研究一89一一

6、次实现，因此，mx2即转化为若干位的左移运datatypedatavar；／／数据元素算，这样两数的乘法运算可转变为加法运算和计算structdataunitnext；／／后继指针效率很高的移位运算．structdataunitpry；／／前继指针例：求Y=195X37．}mydata；其中，37=(100101)f21，由式(3)可得根据算法研究中的描述内容，在建立了链表大v=195×1×26一+195×1×26—4+195×1×整数的加、减、移位等函数的基础上，建立大整数乘2一．法的实现函数代码如下：Y

7、=195X32+195×4+195．mydatamuhiLoop(mydatamytbl，mydata其中，195×32采用195二进数左移5位实现；195×mytimes)4通过195二进制位左移2位实现．通过分析，对任{意正整数，若n≠0，m≠0，由式(3)，Y=m×n可得mydataP，：I：mulpresuh；mulpresult=createY=m×2×It．(当n为偶数时)；(4)—zerotbl()；／／创建保存结二果的链表，并初始化；，，=m×2×+m(当n为奇数时)．while(!tbli

8、szero(mytimes)){二P=find(5)—tail(mytimes)；／／定位到最后一个元素并进行奇偶判断根据式(3)、(4)和(5)整数乘法算法为：if(P一>datavar&1){1)令乘积，若n=0或m=0，执行第5步，否if((mulpresuh=add—sum(mulpresuh，则执行第2步；mytb~))==0)／／加法运算2)如果是奇数，执行第3步，否则执行第4步；exit(0)；／／