计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (16): 87-89.

• 学术探讨 • 上一篇    下一篇

基于DNA粘附子模型的并行乘法算法

杨学庆,柳重堪   

  1. 北京航空航天大学 理学院 数学•信息与行为教育部重点实验室,北京 100083
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-06-01 发布日期:2007-06-01
  • 通讯作者: 杨学庆

DNA algorithm of parallel multiplication based on sticker model

YANG Xue-qing,LIU Zhong-kan   

  1. LMIB & Department of Mathematics,Beihang University,Beijing 100083,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-06-01 Published:2007-06-01
  • Contact: YANG Xue-qing

摘要: 提出了一种基于DNA计算的粘附子模型的并行乘法算法,该算法首先将两个二进制数相乘转变成根据被乘数对乘数进行一系列的移位相加。将被乘数与乘数编码在同一条存储链上,通过组合、分离、设置、清除等四种运算计算出积的值。由于表示输出的DNA链的结构与表示输入的DNA链的结构相同,因此表示输出的DNA链无需做任何改变,就能在后面的运算中重复使用。该算法不仅能用于整数乘法中,还可以很方便地推广到包含小数的乘法运算及多个因数参与的乘法运算中。该算法的突出优点是充分发挥了DNA计算内在的并行计算性,如果参与乘法运算的因数的个数相等,则计算多组乘法运算与计算一组乘法运算所需的时间相同,并且多组乘法运算能从同一个试管内开始。

Abstract: A parallel multiplication algorithm based on sticker model of DNA computing is proposed in this article.The multiplication of two numbers is converted into a series of replacement additions of the multiplier according to the multiplicand.The multiplicand and multiplier are encoded in the same DNA strand,and the product is computed by operations of combination,separation,set,and clear.Because the structure of the output strands is exactly similar to that of the input strand,the result can be further reused without any changes.The algorithm can not only be utilized in multiplication of integers,but also easily extended in multiplication of decimals.The salient advantage of the algorithm is that the time for computing a lot of groups of multiplication is same as that for computing a group of multiplication on condition that the number of the factor is same as the number of the latter.The algorithm makes the best of the potential parallelism of DNA computing.